Educational Codeforces Round 112 (Rated for Div. 2)

 　pretestはDまで四完でした。

コンテストへのリンク

コンテスト後のツイート

E. Boring Segments

　解法ツイートを見てAC。

・コストの絶対値を小さくしたい→コストでソートして最小コストを決め打ったときに最大コストがいくらあれば良いかを調べたい→尺取り

・その際、どこからどこまで行けるか？　を遅延セグメント木を用いて管理すれば、ゴールまでたどりつけるかを判定できる。

　解法を見ればシンプルなのだけど、コストでソートする発想が浮かばなかった。

　最初、道の左端でソートして上手くいく気がしてしまい、それでダメだと分かった後も発想を転換できなかった。

　コストの最小値を決めて最大値を二分探索して判定問題、とは考えたのだから、尺取りも思い浮かんで良かったはずなのに……。（今回は尺取りだとできるけど、二分探索では上手くできなそうですね）

　ただ、コストのMAX-MINを最小化したいのだから、コストでソートして尺取り、というのは結構自然。それさえ思いつけば、遅延セグ木を使うやり方にたどりつくのは困難ではなさそう。

Codeforces Round #735 (Div. 2)

　Cが分からなかった。

コンテストへのリンク

コンテスト後のツイート

C. Mikasa

　koboshiさんの解説が分かりやすかった。

・とりあえず立式をすると、x xor n >m　を満たす最小のxを求めれば良いと分かる。

・上の桁から確定させていく。

　の２ステップ。

　コンテスト中、どちらも考えたはずなのに、解法にたどりつけなかった。

　多分、立式した式を明示的に書かなかったのが良くなかった。

　ちゃんと紙に書き、どういう風に求めれば良いか、具体例（たとえばサンプルの最後のもの）を桁ごとに書けば分かったんじゃないだろうか。

　手間を惜しんではダメ。

AtCoder Beginner Contest 210

 　ABCEの四完。Dは結構思いつきにくい気がする。Fは難し過ぎませんか？

コンテストへのリンク

コンテスト後のツイート

D - National Railway

　解説AC。

　難しい！　DPは全く思い浮かばなかった。マンハッタン距離だから、45度回転ばかり考えてたのが敗因か。

F - Coprime Solitaire

　色々解説を読んだけど、主にkyopro_friendsさんの公式解説でAC。

　2-SATに帰着する問題。

　2-SATに帰着できるということは、コンテスト中は思いつかなかったけれど、言われれば確かに、という感じ。少し慣れている人なら思いつけそう。

　だけど、その後の処理は難しすぎませんか？

　累積和を使えば二乗から線形に計算量を落とせる、と。これは思いつける気がしない。

　結構すんなり解けている人もいるようなのだけど、典型テクニックなのだろうか……。

　さらに、データの持ち方が悪いとTLEしたり、再帰を使ったSCCだとTLE+MLEしたりと大変でした。（ので、SCCは借りてACしました）

　非再帰のSCCは実装しないとまずいですね。

AtCoder Regular Contest 124

　Cまで三完。

コンテストへのリンク

コンテスト後のツイート

D - Yet Another Sorting Problem

　解説は見たものの、さっとは理解できなかったため、参考にして実験してAC。

　グラフの問題だと思ったし、連結成分に注目するのかな？　とは疑ったものの、確信が持てず捨ててしまった。

　連結成分ごとにサイクルになる、ということに気付いてなかったのは問題。気付けば当たり前だけど、ここが考察の第一歩だったと思う。

　その後の考察はどうすれば良かったか難しい……。

　確かに、「左側/右側だけのサイクル」は「左右両方の側に要素があるサイクル」よりコストがかかるのは分かる。

　具体的には、後者は、連結成分のノード数-1回操作すれば良いが、前者はノード数+1回操作しなくてはいけない。

　ただ、サイクルごとに完結するのではないのが難しい。

　「左側だけのサイクル」と「右側だけのサイクル」が両方あった場合、前者の操作途中で後者の処理をすることにより、後者をノード数-1で済ませられる……というのが本質だった。

　逆に、「左側だけのサイクル」が複数あっても、それぞれの操作が干渉しないため、操作回数を減らすことはできない。

　なので、max(「左側だけのサイクル」の個数, 「右側だけのサイクル」の個数)だけ、操作回数が増えるものがある、ということになる。

　コンテスト中は、「左側だけの連結成分」と「右側だけの連結成分」（コンテスト中は連結成分がサイクルになると気付いてなかったのでこう書いています）が干渉することがある、ということは、連結成分ごとに見る方針は間違っているのでは？　と思ってしまい、考察を進めることができなかった。

　解法を見ても、試行錯誤するしかないかなぁ、という気もするので何を反省すべきか難しい。

　思いつけてない何かがあったというわけではなく、どれが正しい方針か分からなかったという感じだし。

　愚直solverを書いていたら多少違ったかもしれないけれど、決定打にはならなそうだし、どう実装すれば良いかもちょっと迷ってしまう。さっと書けるなら書いていたと思うので。

　うーん。

　書くなら、順列同士で、一回の操作で行けるもの同士にedgeをつけて、ソートされたものからBFSする感じか。これでN+Mが9あたりまでは判定できるなら、実装する価値はあったかも。

（EやFはACしたら追記）

AtCoder Beginner Contest 211

　Eまで五完でした。

コンテストへのリンク

コンテスト後のツイート

E - Red Polyomino

　この問題を思い出したので、この解法で解いた。

　ただ、DPしているけど、別に計算量は良くないね。

　解いているとき、Kの制約をあまり見ていなかったのだけど、たとえばN=8, K=32ならTLEするので、この解法で解く意味はあまりなかったよう。

　ただ、コンテスト中、全探索もちょっと考えたものの実装がよく分からず避けた、という面もあるので、うーん。

F - Rectilinear Polygons

　コンテスト中に考えていた方法で自力でACできました。

　つい二次元累積和（imos法）を考えたくなるけれど、この問題では座標圧縮もきかないため間に合わない。　

　そこで、平面走査を思い付くのが重要。

　x座標が小さい順に見よう、と思えば後はポリゴンの処理が悩むところ。

　そこは、縦の線分を順番に見て行ったとき、前の線分と重なる方向か、同じ方向か、で場合分けすると上手くいきます。

　Eまでに時間がかかったのと、平面走査を思い付くまで時間がかかったため解き終わらなかったけど、これは解けなくてはいけない問題でした。

　今度からABC八問体制になるそうで、そうすると全完はかなり厳しくなりそう。今回はチャンスだったと思うので、もったいなかった。

TopCoder Single Round Match 810

 　EasyはHackされたけどMedが通って助かった。

コンテスト結果

コンテスト後のツイート

Div1 Easy WatchedSnail

　二人ずつペアにして考えることが重要だった。

　三人以上重なってもワープできると思い込んでいたのでHackされたのも当然。図を描いたとき、一瞬、二人までしかダメじゃない？　とは思ったんだけど、なぜか大丈夫な気がしてしまった。

Div1 Med IcelandRingRoad

　AtCoderのこの問題の部分問題になっている。

　この問題はACしたことなかったけど、問題を読んだことあったため、この公式解説を読む、というムーブが取れ、救われた。

　ハッシュを使った乱択解なのでやや怪しく見えるのか、tourist氏にチャレンジされたり、neal_wu氏に褒められたりした。SRMでチャットしたの多分初めて！　ちょっと興奮した。

　これを機に、AtCoderの方の問題もACしました。

yukicoder contest 304

　Bが分からなかった。

コンテストへのリンク

No.1623 三角形の制作

　解説AC。

　まず、$n \le 2 \times 10^5$なのに、$r_i, g_i, b_i \le 3 \times 10^3$というのがどういう意味なのか気付く必要がある。

　言ってしまえば、実質$n \le 3 \times 10^3$なんですよね。そこに気付くのが重要。コンテスト中この制約は見ていたはずなのだけど、頭が回っていなかったのか理解できていなかった。

　（緑色、青色）のペアを全列挙できるということに気付いたら、累積和を使うという発想はまあ自然ですね。

yukicoder contest 304

　Bまで二完。Cの考察が全然間違っていた……。

コンテストへのリンク

No.1605 Matrix Shape

　解説AC。

　自分の考察はおかしかったけど、「有向グラフが与えられる。このグラフのオイラー路(全ての辺をちょうど  回ずつ通るパス)の始点と終点の組み合わせとして考えられるものは何通りあるか？」（公式解説より）という問題になるところは良いと思う。

　（なお、私は「終点と終点の前の頂点」の組を考えていた。行列の積をちゃんと考えましょう）

　その後の処理も勉強になった。

　オイラー路が存在するグラフは、連結で、かつ、次のいずれかの条件を満たす

・全ての頂点の相対入次数が 0

・相対入次数が -1, 1である頂点が1つずつ存在し、他の頂点の相対入次数が全て0

（解説より）

　無向グラフのオイラー路判定が、全ての頂点の次数が偶数か、または奇数の頂点が二個、となることは知っていたけど、有向グラフでは相対入次数を考えれば良いことには気付けなかった。

　そして、後者の場合、始点・終点は一意に定まる。まあ、次数を見ればそれはそうですね。

　しかし、なぜか私は、始点が一意に決まっても、終点が一通りにならないグラフがあると勘違いしていた。

　こう書いて見ると、普段はしないような勘違いをしていた気がする。頭が働いてなかったか。

No.1606 Stuffed Animals Keeper

　部分和問題と似た問題になることは分かったが、その後のDPでやや苦戦。

　二乗が通る制約なのでそういうDPをすれば良い、と気付けば解けた。

No.1607 Kth Maximum Card

　これは自力で解けた。

　ただ、01BFSと思って書いたものがそうなっていなかったためWAを出してしまった。

　01BFSの復習になりました。

Codeforces Round #734 (Div. 3)

　Fが通せず終了。惜しいところまでいっていた気がしたけど、実際は全く惜しくなかった。

コンテストへのリンク

コンテスト後のツイート

F. Equidistant Vertices

　木のいくつかの頂点が同じ距離にある、ということは、別のある頂点（今回は中心と呼ぶ）があって、そこから等距離にあるとき、ということはコンテスト中に気付いていた。

　なので、中心を全探索すれば良いのだが、それだと重複するものや、特定の頂点たちがもっと短い距離で結ばれている場合も数えてしまう。

　それらをどのように除くか、というのが問題。

　結論からいうと、「最初の1歩が全部違う場所に行く」（LayCurseさんのツイートより）場合を数えれば良い。これは全く思いつけていなかった。

　確かに、これで、上に書いたようなダメな場合は除けている。

　あとは、x歩進むとき、最初の1歩の候補がk個以上ある場合について、DPで数え上げれば良い。

　（このDPの処理も、DP使う、と分かっていたから簡単に書けたけど、自力で思いつくのは楽じゃなかったかも）

エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）

 　Dまで四完でした。

コンテストへのリンク

コンテスト後のツイート

E - Count Descendants

　深さごとにnodeを管理して二分探索、ということは思いつけていた。

　ただ、オイラーツアーを利用する発想がなかったため、LCAを用いて祖先がどこに当たるかを調べよう、という煩雑な方法を取ってしまった。

　一応、この方法でコンテスト後にACはできたので、ひどい方針だったという程ではないが、オイラーツアー（DFS順）の利用は見逃していることが多い気がする。

F - Integer Convex Hull

　公式から飛べる公式解説、ユーザ解説、解説動画を見てなんとかAC。

　典型090でAndrew's monotone chainを実装したことがあったため、公式解説の方法で実装した。（内部の点の個数の求め方はユーザ解説を読んで理解）

　ただ、確かにmonotone chainの方法を元にDPしているのだけど、ただ凸包を作るのではなく、前の点を全て試して凸になるか調べている、というのを理解するのに手間取った。

・start地点を全探索

・i→jと進む辺が凸包に使えるか全探索

・iの直前の点kを全探索（k→i→jと進んだとき、凸包になっているものを選択）

　するので四乗なのですね。

　そして、DPテーブルには、i→jが上側/下側凸包になる場合の、「総数」を入れる。つまり、全てのk（iの直前の点）に対して、k→i→jが凸包になりうるときの個数の総和を求める。ここで累積和的な考え方を使っていることも理解に手間取った。

　一応理解しACには辿り着けたけど、いや難しい……。

AtCoder Beginner Contest 209

 　Dまで四完で、時間もかかってしまった。

コンテストへのリンク

コンテスト後のツイート

C - Not Equal

　包除原理とかDPを疑ったため時間がかかった。

　$C_i$が小さい順番に考えると分かりやすい、と気付けば難しくないが、他の解法も考えてしまいやすいのが難しい気がした。

D - Collision

　LCAを使って解いてしまったが、使わなくても解けるというのは目から鱗。

E - Shiritori

　グラフを作って後退解析ということは、（典型90問をやっていたこともあり）すぐ思いついた。

　だが、その後の実装が難しい。

　まず、開始位置が辺なのが問題を分かりにくくしている。勝ち負けの条件を逆にしてしまいやすい。

　そして、メモ化再帰で実装しようとすると上手くいかず、後ろ向きにトポロジカルソートかSCCをしてその順番に見れば上手くのでは？　と考えたが、それでも上手くいかない。

　すぬけさんの解説動画を見たが、各頂点について出次数を持っておいて、一つずつ減らしていく……というのは思いつきにくい。

　さらに、一度見た頂点をもう一度見ないようにしないといけない、という辺りでも苦労した。多重辺が存在しうるため、二回見た方がいい気がしてしまうが、冷静に考えると見てはダメ。

　最初に方針を立てるだけなら簡単だが、その方針を詰めるのも実装するのもかなり厳しい問題だった。

F - Deforestation

　すぬけさんの解説動画を見てAC。

　各木のコストの使用回数が1～3回になるため、コストが大きいやつを一回にして、その分をコストが小さいやつに回す（三回にする）……というようなことを考えて詰まった。

　その方向性に見えてしまうと、隣同士に着目すれば良い、というのにはなかなか気付きにくい気がする。

　その後の挿入DPも、解説を聞けばすんなり理解できるけど、自力で思いつけたかどうか。ただ、これは典型処理なので、前半の考察ができたなら解けなきゃまずい。

AtCoder Beginner Contest 208

　Dまで四完。Eが面倒くさそうだったのでFを考えていた。惜しいところまでいった気がしたけど、全くできていなかった。

コンテストへのリンク

コンテスト後のツイート

E - Digit Products

　桁DPっぽいのは分かるし、各桁の数字の積が取りうる値が少なそうなので、計算量が間に合いそうなことも分かる。

　だが、そこからの実装はなかなか難しい。

　自分の実装だと、

・i桁目までNと一致しているか？　というflag（これは、桁DPでよく使うやつ）

　に加えて、

・実際に数字が始まっているか？　というflag（たとえば、"00015"だったら、1が出たときこのflagをTrueにする）

　が必要になった。

　桁DPは、慣れればもうちょっと機械的にできるようになりそうなんだけど、そこまで解く頻度が多くないので、なかなか習熟していかない。

F - Cumulative Sum

　解説AC。

　ラグランジュ補間に関する問題だった。

　ラグランジュ補間はこのあたりで勉強したのに全く思いつかなかったのは良くない。でも、解説放送を見て、以前より大分理解が進んだと思うので、そこは良かった。

Codeforces Round #729 (Div. 2)

　Cまで三完。薄橙に戻れず悲しい。

コンテストへのリンク

コンテスト後のツイート

D. Priority Queue

　一応、自力AC。

　各数字に関して寄与を求める、というところまでは良くて、その後の立式で詰まった。

　ただ、各「+ x」というクエリについて、一遍に（累積和的な何かで）上手くするという方向で考えていたのはまずかった。

　各「+ x」というクエリについて、二乗の計算時間をかけて良いのだからDPすれば良いのか、と思えたのは終了10分前くらいだった気がする。

　そこまで分かってからも実装には苦労した。が、おおまかにはコンテスト中にやろうとしていた実装で合っていた気がする。

　「+ x」というクエリのxに関する和を求めたいとき、DP[i]でxがi番目に小さいようなものの場合の数として、「+ x」の後に、

・「-」というクエリが来たときは、半分の確率で一つ減らす。（つまり、DP[i-1], DP[i]にDP[i]を加算）

・「+ y」（x<y）というクエリが来たときは、半分の確率で一つ足す。

・それ以外の場合、全ての要素を二倍にする。

　という感じで。

　なお、「+ x」の前のクエリについては、似ているけどちょっと違う処理をしなければいけなかった。上手く書けばまとめられるのかな……。

　さらに、同じ数字のときの処理も難しい。コンテスト後の提出ではそこでWAを出して苦労したので、コンテスト中に通すのは厳しかったかもしれない。

　こういう、ちゃんと詰めるのって苦手なんだけど、どうすれば向上するのかな。

yukicoder contest 302

　Eまで五完。

　最近のyukicoderは、途中で寝ちゃったりして、二時間フルに考えていないことばかりだったけど、今回はまあまあちゃんとやった。

コンテストへのリンク

コンテスト後のツイート

No.1583 Building Blocks

　Eとほぼ同じ人数に解かれているのを見て自力でやろうとした。が、「ソートしてDP」だろう、と実装したらWAで解説を見てしまった。

　ソートの仕方が悪いかも、ちゃんと立式したら分かるのでは？　とは思ったのだけど、実際その通りでした。これは、解説を見ずに解けなきゃいけなかった。実装も軽いしね。

東京海上日動 プログラミングコンテスト2021（AtCoder Regular Contest 122)

　ABCEの四完で約半年ぶりにHighestを更新したものの、後でEが嘘だったことが発覚。まぁ、そんなものか。

コンテストへのリンク

コンテスト後のツイート

D - XOR Game

　ちょっと考えて、トライ木を使うのでは？　と思ったところで手が止まってしまったのは良くない。トライ木の理解が不足していたのが敗因だと思うので、ちゃんと復習しておかないと。

　……と思ったが、トライ木を使わなくても再帰を使えばACできると目にし、そちらの方法でAC。（トライ木の復習はしていません）

　Aの全ての要素を二つずつペアにし、それらのxorの最大値を取る……という問題を考えたとき、それができるだけ小さくなるようなペアの取り方を考える問題だ、ということはすぐに気付けた。

　問題は、どう実装するか。

　上位bitから見て行って、立っているbitが偶数個なら、立っているもの同士、立っていないもの同士をペアにすれば良い。それは再帰で書ける。

　立っているbitが奇数個だったときは、bitが立っているもの（それらの集合をBとする）と立っていないもの（Cとする）とのxorを取らなければならない（ので、答えのそのbitは必ず立つことになる）。そのようなペアのうち、最小のものを探せば良い。

　……ということは分かるが、この実装が悩ましい。これをTrie木を使って処理するというのが公式解説の方法だった。

　だがこれも上位bitから見ていく方法でできる。

　奇数個立っていたbitの次のbitを考える。

　BとCの両方でそのbitが立っているものがある、もしくは、両方でそのbitが立っていないものがある、のなら、立っているもの同士、もしくは立っていないもの同士のペアを取った方が良い。そのいずれかの最小値が答えになる（ので、再帰が回る）。

　そういうものがなければ、答えにおいて今考えたbitも立っていることが分かる。そして、その次のbitを見ることになる。

E - Increasing LCMs

　前から素因数の要素数が少ない順に追加していけば良いと思いACしたけれど、嘘でした。

　本当の解法である「後ろから決定していく」というのも一応考えていたので、WAが出ていたら方針転換できた可能性はある。

　けれど、提出したときは結構自信を持っていた（証明できた気がしていた）ので、動揺したと思う。残り二十分ほど、そんな状態で方針転換してACまでいけたか、というと……。実際のところは分かりませんね。

（Fもいずれ解きたい）