keyword 整数 素数 Java 問題概要 長さN(素数Q( 解法 文字列をa[0]a[1]..a[N-1]とする。b[i] = a[i]a[i+1]..a[N-1] (10進の数値として解釈)とすると、b[i]=b[j] (mod Q)ならb[i]-b[j]=a[i]a[i+1]..a[j-2]a[j-1]0..0 (10進の数値として解釈)はQの倍数。ここで…

keyword ライツアウト 掃き出し法 Java 問題概要 W*H(W,H 解法 マンハッタン距離云々は本質に全く関係ない。連立一次方程式をmod 2の世界で解くだけ。計算量はO( (W*H)^3 )。計算量は係数に1/6だか1/3だかがつくけど割と厳しい。でも問題なく通った。 感想 …

解法 各操作に対して逆の処理はすぐ分かるので、やるだけとしか言いようがない。

解法 ただの最小全域木。誤差死することすらまずない親切設計な問題。

keyword 反復深化 シミュレーション Java 問題概要 5*5の盤面でライフゲームの初期値が与えられる。ただし、ある一つのマスには謎の物体Xがいて、Xは周囲のマスに対しては生きている様に振る舞い、しかし自分の存在するマスは回りの状態によらず死んだままと…

keyword Greedy Java 問題概要 W*H(W,H 解法 各数列はソートしても大丈夫だと分かる。 あとは、図の様に右上から左下に向かってGreedyに置いていく。計算量O(W*H)。

keyword 反転数 BIT C++ 問題概要 長さN(a[j]>a[k]を満たす組がいくつあるか求める問題。 解法 反転数に似た概念の問題。解き方も普通の反転数を求めるときとかなり似通っている。まず前処理として座標圧縮っぽい方法で数列aを[1..N]のpermutationにする。数…

keyword 木 C++ 問題概要 ノード数V( 解法 基本的にどの辺も2度通る。例外的に始点から終点までの辺は1回だけで良い。なので終点までの辺の長さが最も長くなるように終点を選べば良い。

解法 基数変換するだけ。ローマ数字じゃないときは入力に0があることに注意。

解法 3!通り全部試すだけ。泥臭く書いた。

解法 1文字づつやるだけ。