Problem - D - Codeforces 問題 大きさ n の整数配列が与えられる。 その後 q 回、クエリxが投げられる。 各クエリごとに、区間の gcd が x となるような候補がいくつあるか答えよ。 解法 nが大きいためとなるような区間の全探索をすることはできない。 解法…

Problem - C - Codeforces 問題 大きさnの整数配列pが与えられる。 この配列の内、重複しない大きさmの区間をk個選択した時の合計値を最大化させたい。 解法 動的計画法 dp[ i ][ j ] := j番目のindexに位置し、i個の区間を選択済時の最大値 例えば、j番目の…

Problem - C - Codeforces 問題 大きさnの整数配列aが与えられる。 aを3つに分割したとき、分割したセグメントの和が全て等しくなるような 分割方法はいくつあるか。 という問題。 解法 全体の和 を とおく。 前提として、が3の倍数でなければ解は一つも存在…

Problem - B - Codeforces 問題 入力として、が与えられる。 はそれぞれ部屋の縦、横の長さであり、部屋の面積を 以上にしたい。 を満たすように、 の長さを拡張した時の 最小の面積を求めよ。 落とし穴が多く、roomでは解けた人が一人もいなかった。 解法 …

Problem - C - Codeforces 問題 n個の連続した整数があり、m回大きさwの区間の要素を1増やす事ができる。 最も小さい要素を最大化させたい。 解法 二分探索で最も小さい花の高さをmid以上にできるか判定し最大値を探索する。 大きさnの配列を舐めながら、高…

問題 Worst Sportswriter | Aizu Online Judge 解法 aがbに勝ったという情報に対して、順位が a < b となることが保証されている。 入力が順序集合を表すと解釈できるため aがbに勝つならば、 aからbに有向辺を張りグラフを構築し、トポロジカルソートを行え…

問題 Problem - E - Codeforces 解法 与えられる文字列長をnと置く。 2重ループを回し全ての部分文字列を調べれば解が求まるが、nのとる値の範囲が 1<=n<=10^5と大きいため、 では間に合わない。 考察すると、各文字は最終的な解に対し独立してスコアが決ま…