お題箱より。 E - MUL 解法 私自身、この問題は解説を読んで衝撃を受けた記憶があります。知らないと自力で思いつくのは相当難しいので、テクニックとして覚えてしまいましょう。 先人の知恵 競プロでは俗称「燃やす埋める問題」と言われている問題カテゴリ…

E - Common Subsequence 公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。 解法 記法について 数列 を単に 、数列 を単に と書くことにします。 与えられた数列は1-indexedで扱い、「0要素目」として空の要素…

F - Minimum Bounding Box 解法 各座標軸ごとに、動きのイメージをつかむ 時刻を文字 で表し、 に依存する変数を のように表します。 まず、 座標を分けて考えてみます。 座標だけに注目すると、それぞれの点は以下の3つにグループ分けできます。 グループ1…

お題箱より。 F - Donation 私も公式解説を見て通したので、公式解説の流れで書いていきます。 解法 時間を逆回しにしてみる 考察を進めていく順番ですが、まず「時間を逆回しにする」ことを考えてしまったほうが良いように思います。普通にゲームを進めると…

E - Sum Equals Xor 解法 ※ と のXOR演算を、 という記号で表すことにします。 まず注目すべきは という条件です。これは知識として覚えておくと得な性質なのですが、XOR演算は繰り上がりのない足し算と思うことができます。 このことを確かめるために、 の…

お題箱より。 E - Tozan and Gezan 解法 プレイヤーを以下のように表記します。 Aさん: を操作する。先攻。ターン数を最大化したい。 Bさん: を操作する。後攻。ターン数を最小化したい。 また、 と表記することにします。 もしゲーム開始時点で全ての につ…

お題箱より。 K - 種類数 β 解法 この問題はグラフとして捉えると見通しが良くなります。それぞれの整数を頂点とし、ペア を頂点 と頂点 を結ぶ辺として考えます。整数を選ぶことを頂点に色を塗ることに喩えると、各辺ごとに「両端の頂点のうちどちらかを選…

E - Complete Compress 公式解説とちょっと違う方法で通したので書いておきます。 解法 木DPを考える コマを集める頂点を全て試すことにします。集める頂点を と表記し、 を根とする木DPを考えます。 それぞれの頂点 について、それ以下にある部分木に含まれ…

F - Absolute Minima 解法 最適な の条件 定数項 については単に答えに足すだけなので、 についてだけ考えます。 更新クエリをいくつか処理した後の式 を最小にするような の値は、 の中央値になります。これは以前の記事に説明を書いているのでそちらも参考…

E - Cell Distance 解法 この問題は結構考察ステップが多いです。順番に考えていきましょう。 数え上げの順番を変える まず考えることは「数え上げの順番を変える」ことです。抽象的な書き方ですが、これが具体的にどういうことか説明します。 問題文では以…

お題箱より。 E - すぬけ君の地下鉄旅行 / Snuke's Subway Trip 解法 グラフの最短路問題として解けそうではありますが、異なる運営会社間での乗り換えを考慮する必要があります。つまり「どの駅にいるか」だけでなく、「その駅でどの会社の路線に乗っている…

お題箱より。 H - 根室の巫女 解法 Morris-Pratt法について まず、公式解説（？）にも書いてあるMorris-Pratt法（MP）について触れておきます。私も実戦で使ったことはないのですが…ある長さ の文字列 があったときに、全ての に対して以下の値を求めた数列 …

F - XOR Matching 解法 結論を書いてしまうと、以下のような数列がもし作れれば答えになります。 アイデアとしては、まず を挟んで 以外の数字を鏡写しに並べます。こうすることで 以外のどの数字を選んでも、2つの位置の間（両端を含む）にあるものは「 1個…

B - LRUD Game 解法 まず気付くべき点は、縦と横は独立に考えられることです。これは今回のゲームのルールが 盤外に落ちる条件が「縦座標が の範囲から外れること」または「横座標が の範囲から外れること」であること 縦座標と横座標が互いに影響し合わない…

D - DivRem Number 解法 この問題は「割り算して切り捨て」と「余り」の関連性に気付くととても考えやすくなります。実際、割り算して切り捨てたときに捨てられる部分は割った余りそのものです。 具体的に数式で表すと、 を で割った余りを とすると が成立…

5月4日のAGCで、ついに橙になることができました！！！ 初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。 ということで記事を書き…

L - をあ ぷろぶれむ 解法 初手は二分探索 この問題のように、 与えられた数列などから、列挙しきれない個数の要素（入力 個に対して 個など）を計算する。それらをソートしたときの 番目の値を求めよ。 という形式の問題では、二分探索が有効なことが多いで…

F - Banned X 気合いで数える問題。ARC-FやAGC-Dあたりの数え上げをやりまくったおかげで解けたかな…と思います。 解法 まず、全要素の合計が 未満かどうかで場合分けをします。 合計が 未満である場合 要素の合計が 未満である場合はどのように数を並べても…

D - Three Colors 解法 三角形の成立条件は、3辺すべてについて「その辺の長さが、他の2辺の長さの合計より小さい」ことです。ただこれをそのまま扱おうとすると3辺全部の長さを管理しながらDPなどをする必要があり、難しそうです。 逆に三角形が成立しない…

D - Shopping この記事を書いている時点で、AGC-Dの中で配点が最も高い問題。私自身AGC-Dを全問通しましたが、ダントツで一番難しい問題だと感じました。解説ACをするのにも非常に苦労しました… この回は解説放送のアーカイブがなくて、解説記事も全然書かれ…

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

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

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

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である」ということ、そして「条件を満たす順列は必ず存在する」と書かれていることから、 連結性を保ったままいくつかの辺を削除しても、変化後のグラフ…