問題 atcoder.jp 解法 大きい方からN/2個がどんな並びでも取れそうと思い、その証明を得た。 やってること自体は本解説と同じな気がするが、こっちの方が断然わかりやすいはず。 次の図が全てである。 値を取らない場合 x方向+1, 取る場合 y方向+1 値を取る…

はじめに 関数論理型プログラミング実験というものがあり、OCamlを書くことになった。そこで、とりあえず色々メモしておいて、後で誰かの役に立てればええか〜と。大した内容は書かない(書きたくもない)ので、あんまり期待はしないでね。それでは、、、 文法…

お気持ち 僕はAtCoderが青でまだ全然強くないのですが、最近思ったこと(自戒でもあること)があるのでここに書いておきます。 皆さんは、精進をどうしているでしょうか。 アルゴリズムの勉強、早解きの練習、高難易度を通す練習、バチャなどなどそれぞれある…

CPU実験のシミュレータ係ってなんぞや！？

問題 atcoder.jp 解法 最終的に選んだものは、小さい方から取っていくのが最適だと証明可能. ということで、最小の値 X を固定したらそこから貪欲に取れば良い. 「X 未満の値は取れない ⇔ X未満の値を跨ぐような区間を選べない」 ゆえに X 未満の値がある場…

問題 atcoder.jp 解法 dpをする. i 番目のコインが有り余ってたら i + 1 番目のコインとして見なすことで、i 番目のコインを 0 ~ max(a[ i ] + 下からの傘増し, 9) しかないと思っても良い. 各ステップ i で下から傘増しされるコインの種類数はそんなに多く…

問題 codeforces.com 解法 1-indexedで扱う. N は 配列のサイズである.B_i = A_i - i と定義する. A_i + A_j = i + j は B_i = -B_j と書き換えられる.L F(a)の最大値を達成するのはどんな時かを考えると,B_i = x となる i が floor(N/2) 個あり、B_i = -x …

s00h.hatenablog.com に移植しました

https://atcoder.jp/contests/typical90/tasks/typical90_o 数弱が悲鳴を上げてしまった... 場合の数をちゃんと勉強しましょうの問題です。 高校数学典型その1 ある数字 n を選んだら (n + 1) ~ (n + k - 1) までは使えないので、n ~ (n + k - 1) をまとめて…

問題 atcoder.jp 解き方 木構造で何かしらの最大を求める問題は木dpっぽさを感じたので、この方針で突っ込んだ。 自分の子が持つべき情報は、何冊もらった時にどれだけのやる気を得ることができるかのテーブル。 この情報があれば、普通のdpの遷移と同じよう…

問題 atcoder.jp 解法 「同じ硬貨を使わない」というのを「同じ桁が同時に非零にならない」と読み替える。つまりY - X = Z (Y : 支払い、Z : お釣り) だと考えた時に、a0 < a1 < ... < a(n-1) かつ a(i+1) % ai = 0が成り立ってるので、各硬貨の使用枚数の上…

問題 atcoder.jp 解き方 偶奇のみに注目すればよく、mod 2 で考える。 与えられた漸化式によって出来る bit 列は、初めの長さ m のビット列さえ決まれば一意に定まるので、m bit分のパターンに注目すれば良さそう。 0と1しか取らないので、各位置をスタート…

問題概要 atcoder.jp 始めの1つの値を決めた後、毎秒いま持ってる全ての値に対して、それより真に小さい値を手持ちに加える。最終的に与えられた配列A内の2^N個の数と一致させることができるか。 解法 現在持ってる値の配列をcurと呼ぶことにする。 配列A内…

問題概要 Problem - E - Codeforces A, G, C, TからなるN*Mのテーブルに対して、最小回数の操作を施して、どの2*2のマス内に各文字が一回ずつ登場するようなテーブルに直せ。 解法とその証明 文字をa,b,c,dで代表させることにする。この時、 abab cdcd abab …