E - Black or White 解法 答えを定式化する 番目のチョコレートを食べ終わった直後に、 黒が残っている確率： 黒白どちらも残っている確率： とします。このとき黒だけが残っている確率は です。 番目に食べるチョコレートが黒であるパターンは、 番目のチョ…

D - Modulo Operations 解法 単調減少列を考える まず気付くべき点は、「ある値 で余りを取ったあと、それより大きい値 で余りを取っても値は変化しない」ということです。 で余りを取った時点で黒板に書かれた値 は 以下になっていて、その より大きい値で…

D - We Like AGC 解法 問題文の条件を満たすためには、具体的にどのような部分文字列が含まれていてはダメでしょうか。NGパターンを列挙してみましょう。 3文字のNGパターン もちろん AGC はNGです。また、隣り合う2文字を入れ替えて AGC となる GAC と ACG …

No.803 Very Limited Xor Subset - yukicoder 解法 AtCoderに「Limited Xor Subset」という問題があります。この問題の想定解法は今回のyukicoderの問題とは全く違うものですが、この問題に対するこちらの別解がとても参考になります。私もコンテスト本番は…

C - Differ by 1 Bit 解法 コンテスト本番で私が考察・実装した方針を書いていきます。公式解説とは実装の方針が異なっていて、公式解説のほうが恐らく楽な実装だとは思いますが、ACを得るまでの1つの過程として参考になればと思います。 YES/NO判定 まずは…

B - Reversi 解法 まず、1つ性質を確認しておきます。それは「石の色を塗り替える操作について、両端と同じ色を間にも含むような区間に対する操作は考えなくても良い」ということです。具体的には以下の図の上側に示すような操作です。このような操作は下側…

I - Ramen 解説を見て通したけど、実装にけっこう手こずったので記録。 解法 距離の2乗をコストに持つDP、といえばCHTです（？）。CHT（Convex-Hull Trick）が使えるように、価格 の計算式を と変形します。 が についての一次式群から最小値を求める形式に…

F - RPG 解法 「全ての頂点に対し、頂点 からのパスと、頂点 へ向かうパスが存在する」「閉路がない」という制約から、無駄な辺/頂点はないということが分かります。具体的には全ての パスを考えた時、全ての辺/頂点についてそれを通る パスが存在し、さらに…

早稲田大学プログラミングコンテスト2019 - AtCoder 解法 まず気付くべき点は、行の区切り位置と列の区切り位置を独立に考えられることです。行・列ともに、それぞれの区切り位置を境として黒いマスの個数が反転します。 そのためまずは行（列も同様）ごとの…

D - Choose Your Characters 解法 条件を満たしている区間はさらに伸ばしても必ず条件を満たすので、しゃくとり法が使えます。上手くしゃくとり法ができるように工夫をしましょう。 しゃくとり法では自キャラのほうを区間に入れたり出したりするので、それに…

C - Permutation City 解法 木にする まずはグラフの形を簡単にします。距離に関する条件が「1または2である」ということ、そして「条件を満たす順列は必ず存在する」と書かれていることから、 連結性を保ったままいくつかの辺を削除しても、変化後のグラフ…

D - XOR World 解法 「 について○○を計算した合計を求めよ」という問題で使える実装テクニックとして、代わりに「 について○○を計算した合計」から「 のうち○○を計算した合計」を引いたものを求めると考えると、変数が減る上に同じ処理を2回すれば良いだけに…

Problem - D - Codeforces 問題概要 コンテスト参加者が使う 台のPCがある。 番目のPCの初期電池残量は で、消費速度は毎ステップ である。 初めに充電器の充電速度として非負整数 を決め、以下の処理を ステップ行う。 各ステップごとに、どのPCを充電する…

D - Decayed Bridges 解法 グラフの連結性を考えるのに便利な道具として Union-Find木 があります。Union-Find木では「辺を追加して頂点同士を連結にする」という操作が可能ですが、対して今回の問題は「辺を削除して頂点同士を分断する」という操作になって…