https://atcoder.jp/contests/abc468/tasks/abc468_d回文の中心が文字のときと文字と文字の間のときがあります。それぞれで中心から対象の位置の文字を見ていきます。 // Pre-Palindrome #![allow(non_snake_case)] //////////////////// library //////////…
https://rosalind.info/problems/fibd/この問題も行列を使いますが、大きさが最初から決まっていません。そういうときはndarrayを使います。 Cargo.tomlに [dependencies] ndarray = "0.13.0"と書いて、 use ndarray::prelude::*; fn make_matrix(m: usize) …
https://rosalind.info/problems/subs/次の文字列を探すには、スライスにfindを実行させればよいです。ただし、罠があります。返ってくるpositionはスライス後のものなので、スライスより前の長さを足さないといけないです。
https://atcoder.jp/contests/abc467/tasks/abc467_eに何回1を加えるかを決めると、までが次々と決まります。に1を加える回数をとすると、入力例1で加える回数は、となります。 ただし、は[0, 10)の値が取れて、は[0, 6)ではですが、[6, 10)ではとなります。…
https://rosalind.info/problems/gc/FASTAを読むのはこんな感じです。 fn read_fasta(file: std::fs::File) -> Vec<(String, String)> { let reader = BufReader::new(file).lines().map(|r| r.unwrap()); let lines: Vec<String> = reader.collect(); let heads: Vec<usize></usize></string>…
https://rosalind.info/problems/fib/漸化式の問題は行列を使いたくなります。Rosalindは勝手にライブラリを使えるので使いましょう。 大きさが小さくて決まっていれば、nalgebraというライブラリを使うとよいそうです。 Cargo.tomlに [dependencies] nalgeb…
https://atcoder.jp/contests/abc467/tasks/abc467_d2点の中点を通る線分の垂直線をそれぞれ引きます。それが交わればそこが共通の中心です。 垂直線が平行でなければ交点があります。平行なら、同じ直線上なら共通の中心になりうる点が無限にあることになり…
RosalindをRustで解きなおしていきます。 ただし、答えは書けないので、Rustで注意する点を書いていきます。https://rosalind.info/problems/dna/テキストファイルはこんなに読みます。 use std::env; use std::fs::File; use std::io::{self, BufRead, BufR…
https://atcoder.jp/contests/abc466/tasks/abc466_d行と列と別にどこにコマがあるか管理すればよいです。 // Placing Rooks #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mut line = String::new();</t:>…
https://atcoder.jp/contests/abc465/tasks/abc465_d入力例1の最初のケースでは、11 → 3 → 9となりますが、共に3で割ると3だからこうなりますね。では、8と9なら、8 → 2 → 0 → 1 → 3 → 9で5回かかります。 こう見ると3進法で考えるとよさそうですね。11は3進…
https://atcoder.jp/contests/abc464/tasks/abc464_e2次元のセグメント木を作っておいて、のセルに何番目に置いたかをsetします。そのあと、各セルと右下隅で作る長方形の領域で最大の値を得ると、それに対応する文字になります。入力例1なら、 002 310とな…
https://atcoder.jp/contests/abc464/tasks/abc464_d一つ前と今だけで嬉しさの増減が決まるので、状態を天気、値を嬉しさとするDPをすればよいです。 // Celester #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -</t:>…
https://atcoder.jp/contests/abc463/tasks/abc463_f千秋楽の前で一番多い勝利数を、それより一つ少ない勝利数を、それ未満をと表すとします。 入力例1の2つ目の対戦はというパターンです。3番目の選手は自分が勝って、かつ勝の人が出ない確率を求めればよい…
https://atcoder.jp/contests/abc463/tasks/abc463_eワープがなければふつうにダイクストラですが、ワープがあると各都市から各都市にエッジを張るようなものなので、の計算量になって間に合いません。 ワープを2回続けると、とすると、時間かかって、と直接…
https://atcoder.jp/contests/abc463/tasks/abc463_d距離を直接求めるのは難しいですが、距離を指定して何枚布を選べるかを調べるのは簡単なので、二分探索します。 // Maximize the Gap #![allow(non_snake_case)] //////////////////// library //////////…
https://atcoder.jp/contests/abc462/tasks/abc462_f状態を何個目のABCがいくつ新たに作れてABCのどこまで作れているか、値を変えた文字の個数の最小値としてDPを行います。だから、Kの3倍の状態があることになります。しかし、ABCが出てきたらいったんその…
https://atcoder.jp/contests/abc462/tasks/abc462_e、として、斜め45度にまず進んで残りは、まっすぐ進むとのときはそのままでいいですが、で進むときはコの字に進んででどちらかをどちらが小さいかで決めます。 // Alternating Costs #
https://atcoder.jp/contests/abc462/tasks/abc462_dPriorityQueueに開始時刻の順に入れて、終了時刻-Dを過ぎたら取り出します。その時刻にPriorityQueueにいる人の数でその時刻開始の組合せ数が決まります。 // Accomplice #![allow(non_snake_case)] /////…
https://atcoder.jp/contests/abc461/tasks/abc461_e入力例1で考えると、1行目を黒く塗って+3、3行目を黒く塗って+3、2列目を白く塗るのですが、黒が2つあるので-2、最後に1行目を黒く塗るのですが、1回目のクエリで1行目を塗ってあるので、その間に列を1回…
https://atcoder.jp/contests/abc461/tasks/abc461_d何行目から何行目かを固定して、何列目から何列目まででKになるパターンを数えます。全部0以上なので、尺取り法的に数えられて、計算量はでなんとか間に合います。 ただし、K=0のときうまくいかないので、…
https://atcoder.jp/contests/abc460/tasks/abc460_eの桁数をとすると、なので、だから、はの倍数です。 i128を使うと簡単ですね。 // x + y ≡ x + y #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -> T { let mu</t:>…
https://atcoder.jp/contests/abc460/tasks/abc460_d1回目以降に黒になったマスは白と黒が交互に現れるので、最初に黒になるターンをメモしておきます。 // Repeatedly Repainting #![allow(non_snake_case)] //////////////////// library ////////////////…
https://atcoder.jp/contests/abc459/tasks/abc459_d各文字がいくつ使われているか調べて、一番多い文字を等間隔に置いて、その間に多い順に置いていけばよいです。 こういう問題はOptionを使うとよいですね。 // Chalkboard Median #
https://atcoder.jp/contests/abc456/tasks/abc456_g久しぶりに解説を見てみたら、母関数を使う方法が書いてありました。 Sをxで分割して、それぞれの領域の長さをとして、日のうち連続する休日が日までの場合の数をとすると、求める場合の数は、となります…
https://atcoder.jp/contests/abc458/tasks/abc458_d半分に分けて、奇数個だから左側が一つ多くなるように保ちます。 // Chalkboard Median #![allow(non_snake_case)] use std::collections::BinaryHeap; //////////////////// library ///////////////////…
https://atcoder.jp/contests/abc457/tasks/abc457_d値の下限を決めて、そこに達するまで何回操作するかを調べます。そして、二分探索でその下限を決めます。ただし、細かいところがややこしいですね。 // Raise Minimum #![allow(non_snake_case)] ////////…
https://atcoder.jp/contests/abc454/tasks/abc454_c有向グラフを1から辿るだけですが、Rでグラフをふつうに作る全然時間が足りません。そこでノードの隣のノードの配列をリストにします。こうすると時間内に収まります。 v <- scan("stdin", integer()) N <…
https://atcoder.jp/contests/abc456/tasks/abc456_cDP的に、前の文字と隣に同じ文字無しに何文字続いているかを記憶していきます。 最後はやっぱり出力のところですね。 D <- 998244353 v <- scan("stdin", character()) S <- v[1] char_to_int <- function…
https://atcoder.jp/contests/abc456/tasks/abc456_f1日飛ばしでもいいという問題です。これが毎日コストをかけるということなら、ウィンドウ幅を一定にしてスライドしていけばいいのですが、1日飛ばしだとうまくいきません。コストを払うときと払わないとき…
https://atcoder.jp/contests/abc456/tasks/abc456_e都市と曜日の組み合わせをノードにして有向グラフにして、ループがあるかを判定します。 // Endless Holidays #![allow(non_snake_case)] //////////////////// library //////////////////// fn read<T: std::str::FromStr>() -</t:>…
