Kotlin Heroes: Episode 7

　Fまで六完で、T-シャツには一問足りず。もっと早く解けないと厳しい。

　とはいえ、残り30分でGかHのどちらか解ければOK、という状況はそれほど悪くなかったともいえる。いかしたかった。

コンテストへのリンク

コンテスト後のツイート

G. Biome Map

　文章が分かりにくいけど、行列Aで(temperature, humidity)に対応するBiomeの番号が与えられている。「その差の絶対値の和が1になるBiome」のみが隣り合うことができるということなので、つまり、Aで隣りあっているものだけが出力すべき行列でも隣りあえるということ。ただし、出力すべき行列の行や列の長さは、Biomeの個数以下でなくてはならない。

　Aの中で上下左右に移動していって、全てのBiomeを尽くせば良い、ということなので、オイラーツアーをすれば良いと分かる。

　ただ、単純にオイラーツアーを一列に並べたのでは、行や列の長さの条件に反する。

　二行にして折り返して並べるのもダメ。縦に隣りあう部分が条件に違反してしまう。（コンテスト中は、これで良い気がしていました）

　なので、斜めに並べると良い。オイラーツアーの長さはBiomeの個数*2-1個なので、この構築でちょうどBiomeの個数*Biomeの個数の正方形ができあがる。

　実装で詰まったのは、

・Kotlinで再帰を書き慣れていなかった

・木でない一般グラフでも再帰一回でオイラーツアーが取れると気付かなかった（一回全域木を取らないといけない気がした）

　の二点。

　「斜めに並べる」という本質が見えてなかったのでコンテスト中にACするのは難しかっただろうけど、実装で詰まったりせず、オイラーツアーまですんなり書けていたら、思いつけたかもしれない。　

AtCoder Beginner Contest 207

　ABCEの四完でした。D難しい。

コンテストへのリンク

コンテスト後のツイート

D - Congruence Points

　すぬけさんの解説動画を見てAC。Pythonで$O(N^3)$でも65msでした。

　いやでも確かに難しいのだけど、Sの一点目から二点目へのベクトルが、Tのどの二点のなすベクトルと対応しているか？　で二乗をかけるという方針は思いつかないといけないですね。

　そこまでできていれば、回転を複素数で計算という部分はできたかもしれない。本番中にも複素数を使うことは頭をよぎったはずなので。

　コンテスト中は、（他の人も結構ハマってましたが）角度を決め打って云々、という嘘解法にハマってました。

F - Tree Patrolling

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

　二乗の木DPの問題は最近も解いていたのだから、自力でできなくちゃいけなかった。

　が、解説を聞いた後なのに、遷移を書くのに苦労したり、modを取り忘れたり、コーナーケースに引っ掛かったりとWAを量産してしまった。

　二乗の木DPで、子同士をマージするときの遷移は大体いつも似た感じいなるのね。FFTを使える形になるらしい。以前の二乗の木DPの問題でも、「遷移を書くのが面倒だったからFFTを使った」とか書いているツイートを見かけたけど、なぜそういうことができるか理解できた。

　それに気付けたのは収穫。

AtCoder Grand Contest 054

 　Cまでの三完で101位でした。Highest更新できて嬉しい！

　ただ、難問が解けたわけではないんですよね。早解き回では時々良い成績が取れるんですが、早解きが得意というわけでもないので、なんというか、運任せのようになってしまう。今回は、BもCも結構最初から正しい解法を考えていたけれど、偶然に近いものね……。

　もっと難しい問題を解く力を付けないと。

コンテストへのリンク

コンテスト後のツイート

B - Greedy Division

　初手で実験を書いたのが結果的には正解だったと思う。

　実験というのは、Wの配列に対して、どんな順列がありうるか……というのを順列全探索で求めるコードです。

　それを眺めていたら、「あれ、和がSUM/2に一致していれば、高橋君や青木君の取り方をどんな順番にしても、正しい順列が一つ求まるのでは？」と気付き（気付けば証明もしやすかった）、後はナップザック問題みたいな感じでした。

　計算量が四乗になるのがちょっと不安だったけれど、定数倍が小さそうなので大丈夫だろう、と提出したら無事AC。

C - Roughly Sorted

　これは、「2 1 4 3 6 5」でK=1の場合などを考えました。この例で、1や3はいくらでも後ろに動かせるけど、2が4の後ろにいくと途端にダメになるんですね。

　それを見て、「自分より前に登場している自分より大きい数の個数」がKに一致しているものしか動かせないんだな、と気付けました。

（DかEはできれば解説ACしたい）

Codeforces Round #728 (Div. 1)

　A一完のひどい出来。

コンテストへのリンク

コンテスト後のツイート

B. Tree Array

　制約から、三乗の解法を考える。

　全てのi, j (i < j)について、j が iより先に使われる確率を考えれば良い。（主客転倒って言うのかな？）

　そうすると、iとjを結ぶpathにいくつか余計なものがくっついているような図を考えることになる。（木の直径を図示するときのやり方と同じ）

　なので、iとj上のpath上の点から始まったとき、jの方に先にたどりつく確率を調べればOK。

　……と、ここまではできたが、この確率が2ベキの和になると早合点してしまった。それでサンプルが合ったこともあり、修正できず終了。

　実際は、iから距離p、jから距離qの点からスタートしたなら、p回iの方へ進む前に、q回jの方へ進む確率を計算すれば良いので、p*qのマスで端から端への最短で向かう経路数を考えるのと似たようになる。これはDPで求めることができる。

　これを前計算すればOK。

　多分、もう少し時間が残っていて、落ち着いて考えていたらちゃんとACできたと思う。先にCを考えたりしたせいもあり、Bの正しい方針に至ったときに時間が残っていなかったのが敗因か。

　

AtCoder Beginner Contest 206（Sponsored by Panasonic）

 　Eまで五完でした。

コンテストへのリンク

コンテスト後のツイート

F - Interval Game 2

　すぬけさんの解説を聞いてAC。

　NIMみたいなことをするのでは？　Grundy数を使うのでは？　とは多少は考えたものの生かすことができなかった。

　ある一つを選択したら、左右に残った二つの区間のGrundy数のxorがそのGrundy数になる、というのはちょっと思ったのだけど……。

　それに加えて、どういう遷移があるかを考えなくてはいけなかった。

　Grundy数を考えたいのだからどのような遷移があるかを考えるのは当たり前で、「いくつかの区間が選択可能」なときのGrundy数は、それぞれを選択したときのGrundy数のmexとなる。

　Grundy数の定義通りなのだけど、遷移を意識していないと書きにくい気がする。Grundy数と区間DPって相性が良いんだね。

Codeforces Round #726 (Div. 2)

 　Cの誤読でハマったものの、なんとか全完。Div. 2のCくらいだと、この後に解ける問題があるはず！　と、ちょっとハマったら飛ばす決断ができるんだよね。これが、ARCとかこどふぉDiv. 1だとなかなかそういう決断はできない。

コンテストへのリンク

コンテスト後のツイート

　ツイートに付け加えることは特になさそう。

　Dの正当性は、Kiriさんのツイートで理解しました。なるほどー。

AtCoder Beginner Contest 205

　Eが解けずに終了。ただ、Eは知識問題に近かったので、まあ仕方ないか。次に類題を見たときは解けるようにしたい。

コンテストへのリンク

コンテスト後のツイート

E - White and Black Balls

　解説AC。

　経路数の問題なのは分かるが、それをどうやって求めればいいか、というところで詰まった。解説の図を見てなるほど、となった。

　この求め方は見たことがあったと思うが、身に着けておかなくてはいかない知識とは思っていなかった気がする。

　次出題されたときは解きたい。

Codeforces LATOKEN Round 1 (Div. 1 + Div. 2)

　Cまで三完。D、Eを考えていたが解けずに終了。ここまではっきり失敗したのは久しぶりな気がする。

コンテストへのリンク

コンテスト後のツイート

D. Lost Tree

　「木は二部グラフ」というキーワードすらほとんど浮かんでいない。

　クエリの回数がn/2というところから、二部グラフは考えるべきなんですよね……。

　そのキーワードを思い付くことが重要で、その後は、一回目のクエリで二部グラフのどちらに属しているか判断できる、と気付くところがポイントですね。

　二部グラフを使おうと思いついていたとして、そこで詰まっていた可能性はありそう。

E. Lost Array

　全ての要素についてクエリで聞いた回数が奇数回になれば良い、というのは分かった。では、それが実現できる最小の回数は？　というところで詰まった。

　なんか条件（1の個数や3の個数を調べて……みたいな）がないかと考えていたけど、上手くいかず終了。

　実際は、もっと愚直に構成できるか試してみるべきだった。

　ただ、毎回それをやっていると、$k=n-1$のときにTLEしてしまう。このときは、n回聞けば良いと分かるので、場合分けしてやればACできた。

　公式解説は（理解できていないが）もっと賢い方法でやっているようだけど、上記の方法はコンテスト中に考えたことをまとめただけなので、コンテスト中に通すことは可能だったはず。

　計算量を気にする前に、愚直なやり方で間に合わないかを試してみるべきだった。

第二回日本最強プログラマー学生選手権

　ABCDFで終了。Eはコンテスト後、自力で解けたもののかなり苦戦した。

コンテストへのリンク

コンテスト後のツイート

G - Spanning Tree

　行列木定理を知らないとどうしようもない。

　これを知れたのは良かった。（証明は理解できてないけど）

　行列式の計算もはじめて書いたと思う。なるほど、掃き出し法を使うことで三乗に収めるんですね。

　ケイリーの公式といい、この行列木定理といい、知らないと思いつくのが難しい（が、競技プログラミングに出題される）定理が木の分野にはありますね。

H - Shipping

　最近、SRMで類題を見たので、解説ACしました。

　公式解説の「ハッシュを使った解法」は凄いですね。サイクルの部分はSRMのものと同じですが、木の部分もこうやって処理できるとは。

　SRMのときはサイクルのところしか読まなかったので、木の部分はどうするんだろう、と考えていたのですが、LCAを使うしかないのかな……と思っていたところでした。しかしこれもLCAを使わずにハッシュで解けるんですね。

　とはいえ、このハッシュの使い方はこのFと同じか。

　いくつかの状態があって、そのうちの一つでも存在するかどうか調べたい……というときはこのハッシュ（Zobrist Hash）を検討しても良いのかもしれない。

Codeforces Round #725 (Div. 3)

　Eが解き終わらず終了したが、コンテスト後提出したらWA。その後、約一時間かかってようやくpretest全完。

コンテストへのリンク

コンテスト後のツイート

　ツイートに加えて書くことはなさそう。

　Gは最初、フローに見えて悩んでいたのは良くなかったね……。正当性がやや不安だったけど、どうやら正しそうで良かった。

AtCoder Beginner Contest 204

 　Eまで五完。Fはキーワード的には分かっていたのだが……。

コンテストへのリンク

コンテスト後のツイート

E - Rush Hour 2

　ダイクストラ法。

　$\sqrt{D}$よりtimeが小さいときは、$\sqrt{D}$を調査、そうでなければ普通にtimeのときにかかる時間を計算。

　$\sqrt{D}$あたりが極値になりそうなことは、最初は微分しようとしたが面倒くさくなって、

　$x+\frac{d}{x+1}=x+1+\frac{d}{x+2}$

　を計算した。

　これは、$x$が1ずれても同じ値になるところを調べているということ。こういう$x$で極値になるはずなので。

F - Hanjo 2

　解説AC。

　うーん、行に関する部分集合たちについてDPをして、行列累乗だろうとは思ったし、横2マス見れば現在の状況が扱えることもコンテスト中に考えたはずなのだけど。

　しかし、解説をみても、「列iまでみて全ての行ではみだしている場合」と「列i+1までみてはみだしが一つもない場合」は同一のものなのに、DPするとき両方を状態として持たなくてはいけないことにピンと来なかったし、自分にはちょっと分かりにくいDPだったのかもしれない。

　遷移の行列を作るところは再帰で書いたけど、これもどう書けば良いか結構迷ってしまった。

Codeforces Round #724 (Div. 2)

　全完35位！　Div. 2全完は初めてなので嬉しいです！

　こういう、ちょっとギャグっぽい問題が多い回だと、良い順位を取れることがあるみたい。

コンテストへのリンク

コンテスト後のツイート

　ツイートで書いた解法に加えて書くことないので、ツイートの補足的なものを少しだけ。

E. Omkar and Forest

　問題を見て、最初は全然分からなくて、諦めようかな……と思い横になって直線状の図を考えていたら、「0でないマスの値は決定される」と気付きました。

F. Omkar and Akmar

　nが6や7の場合まで図で描いていたら、ABABAB……と一周するしかないことから後手必勝と分かりました。

　その後の計算も戸惑ったけれど、数字が書かれるマス二つの間の空のマスは一つなので、「数字が書かれる1マス」と「数字が書かれるマスと空のマスのペア」を考えれば二項係数が使えそう、ということから立式できました。

　終了間際でギリギリだったけど間に合って良かった。

NOMURA プログラミングコンテスト 2021(AtCoder Regular Contest 121)

 　Cまで三完。Cで苦戦してしまったが、レートはそこまで落とさずに済んだ。

コンテストへのリンク

コンテスト後のツイート

C - Odd Even Sort

　三文字以下なら、交互に操作し続けることでソートになる、というのは気付かなければいけないけれども、後は大きい数字を右に移動させていくだけで良い。そうすると、自然に規定回数以下に収まる。

　後は実装問題なので何を反省すべきかね……。

　とりあえず、WAやTLEがでたときにすぐにcheckerを書いて（結局、何回かペナを出した後で書いた）いれば、ペナルティ量産は防げたと思う。

D - 1 or 2 

　解説AC。

　ツイッターなどでヒントを見ていたのでどこまで自力かは分からないけど、常に二つ選ぶなら、ソートして大きい方と小さい方から取っていくのが最適、というのは気付いた。

　あとは、一個だけで取るものをどう選ぶかだけど、ソートしたものの中である区間になっているはず。その区間全探索を普通にやると三乗だけど、何か差分計算とかで高速化するのかなぁ……とか考えながら解説を見たら、思った以上にシンプルでした。

　なお、解法ツイートを見ると、（高速化は分からないけれど）正負などで場合分けして一個取る場所の範囲を絞れば通るみたいですね。

E - Directed Tree

　解説AC。

　……といっても、公式解説を読んだだけではなかなか理解できず苦労してしまった。

　木の問題で、木DPをするのでは？（制約を見ると、二乗の木DPかも？）　使ってはいけない数字が指定されるので、包除原理を使うかも？　といったあたりは考えた。が、そこで詰まってしまった。

　キーワードはこの問題と共通ですね。そして、今回の問題はこの問題よりDPを立式するのは簡単なはず。とはいえ、なかなか立式するのは難しい気がする。

　結論からいうと、解説の通り、

・$DP[i][j]$を$i$を根とする部分木に$j$箇所条件に違反するように書き込む方法の個数

　とするのだけれど、この「部分木」というのは、その部分木の祖先がどうなっているのか、とかとは全く関係ない、本当にただの部分木です。その部分木に関する入力が与えられたら、その答えを求めるものです。

　……いや、素直に解説を読めばそう（だし、二乗の木DPを使う問題ではそういう風に置くものなのかも）なんですが、私は、祖先のノードが何個あるから禁止すべき個数は……などと考えてしまいました。

　それだと遷移が上手くいかなくて、ただの部分木に関する問題のDPテーブルが求まっていたら遷移が上手くいく、というのは不思議です。

　あと、この問題の難しさは、包除原理を使うなら、$DP[i][j]$の$j$は必要なさそうなのに、$j$を明示的にしなくてはいけない、という部分だと思います。最終的に、$j%2$によって足すが引くかを決めるので、$DP[i][2]$で良いのでは、と思ってしまいそう。

　ただ、$DP[i][j]$の$j$があっても二乗に収まる、というのが二乗の木DPなので、二乗の木DPを使おうという気持ちで臨むとDPの立式もしやすいのかもしれない。

　どうDPテーブルを置くかが難しい問題な気がしたけど、二乗の木DPに慣れていれば分かるのかも？　とも思えてきました。

　練習すれば、DPの置き方も含めて典型と思えるようになるのかな……。

（FはACした後書くつもり。）

Educational Codeforces Round 110 (Rated for Div. 2)

　数分遅刻してDまで四完。今回のえでゅふぉC～Eは教育的な出題だったと思う。Cは尺取り法の、Dはセグ木の、Eはダブリングの、本質的な理解を問うている感じがします。

　普段のえでゅふぉは、educationalという名前の割に教育的とは思えない問題が多い気がするけど、今回は良かった。

コンテストへのリンク

コンテスト後のツイート

C. Unstable String

　尺取り法で良いのだが、左端を動かすときの条件がやや書きにくい。

　dequeを使うと尺取り法を書きやすい、というのを目にしていたのを思い出し、この問題で試してみたのだけど、「左端の条件の書きにくさ」はこの方法では緩和されず、時間がかかってしまった。

　でも、普通に（whileとかで）書くよりはちょっと楽だったかも？

D. Playoff Tournament

　図の通り、セグメント木みたいなことをするのだけど、普段多くの人が書いているセグメント木とは添え字の順番が違うことに注意。

　そこを補正するため、普段の順番と今回の順番で、添え字の対応表を作れば良い。

　私は、対応表を作るときのfor文の範囲を間違えて、対応表に-1を残してしまったためTLEが出てしまった。原因特定に苦労した。

E. Gold Transfer

　コンテスト中は、$C_i>C_{p_i}$を見落としていたのでどうしようもなかったが、この条件をちゃんと理解すれば、一番祖先から貪欲にとっていけば良い。

　なら、ダブリングするのかな、というのは思いつく。

　ということは、金がなくなっていない祖先のノードを見つけて、そこから自分の方へ降りていけば良いのだけど、降りるときどうすれば良いの？　というところで詰まった。

　LayCurseさんのツイートで理解。

　落ち着いて計算量解析をすれば分かりますね。

　なお、実装したけどPyPyだとTLEだったのでKotlinでACしました。ただ、今見ると何人かPyPyで通していますね。

AtCoder Regular Contest 119

　ABCEの四完。現在の主戦場であるはずのARCでレートを上げられて嬉しかった。

コンテストへのリンク

コンテスト後のツイート

D - Grid Repainting 3

　解説AC。惜しいところまでは自力で考えられたのだけど結局解説を見ないとACできなかったので、コンテスト中に飛ばしたのは正解でした。

　自分で考えたのは、

・Rのマスを頂点とし、縦横で繋がっている頂点を辺とするグラフを考える。

・辺が一本だけ出ている頂点があれば、X方向かY方向かどちらに消せばいいか決定できる。

・ということは、最小全域木を取れば良さそう。

・全域木を取って、辺が一本だけ出ている頂点についてはX方向かY方向かで色を塗っていく。そして、最後に残った頂点たちは、「全てX方向に塗る」か「全てY方向に塗る」が最善。

　という感じ。この考察自体はあっています。

　ただ、このグラフで全域木を取るのが容易ではない。上手い実装が思いつかなかった。

　なので、自分にとっては、公式解説の「考察１」が胆でした。

　(x, y)をグラフの頂点とみなすのではなく、各行や各列を頂点とみなし、頂点「x行」と頂点「y列」を結ぶ辺(x, y)と考える。

　そうしても、全域木を取って云々という他のステップについては同様にできます。

　この考察自体は珍しいものではないけれど、一旦、別のグラフで考察した後、グラフ自体の変更を考える、というのは思いつきにくい気がします。

E - Pancakes

　ツイートした通り、Codeforcesで出た問題の類題でした。「区間の交わり方は3通り」は頭に叩き込んでおこう。

（FはACしたら更新する予定）

Codingame「Spring Challenge 2021」

　Codingame「Spring Challenge 2021」に参加しました。前回はGold Leagueまで行けたので、今回はLegend League入りを目標にしました。

　結果は、195位/ 6867人で、なんとかLegend Leagueに入れました！

　目標達成できたので嬉しいのですが、今回はLegendの人数が多かったこともあり、やや微妙な気持ちもあります。

　ルールはいなにわさんの日本語訳が分かりやすいです。（コンテスト中も参考にしました）

　また、色々な方の参加記がshirakiaさんによってまとめられています。非常にありがたい。

コンテスト後のツイート

　（ツイートした通りですが）私がやったことは、適当に評価値を作って、「Possible moveの中で評価値が一番高いのを選ぶ」というだけです。

　本当は、

・評価値を作る→探索する（たとえば二手後の評価値を調べる、など）→やっぱり時間制限が厳しいから他の言語に書き換え

　のようにする予定だったのが、最初のステップで終わってしまった感じです。それはちょっと悲しいですね。

　ただ、元々今回は、「評価値を頑張りたい」という気持ちが強かったです。

　前回のCodingameに参加した経験で、終了後に他の方の参加記を読むと、探索以前に、ゲームへの考察が不足しており、評価関数にまだまだ改善すべき点があったことが分かりました。今回はその点では後悔したくない、と思っていました。

　それに、良い評価関数を作ることは、後で探索を行う場合でも枝狩りに役立ったり、無駄にはならないはず、と。

　その点に関して言うと、他の方の参加記を読んでもそこまで考察不足だった、と感じる点はなかったので良かった。

　あと、koyumeishiさんの記事を参考にローカルでの実行環境を作れたのは良かったです。前回はローカルでの実行環境を作れなかったので……。100回とか300回実行して、勝率が高い方を選ぶ、というのができ、このおかげで評価関数を調整できました。

　この、ローカルで実行しながら色々パラメーターを調整している間に暇な時間があったんですよね。その間に探索を実装したら良かったのですが……。サボってしまった。

　次回は考察した上で、探索も実装したいですね！（NNを勉強するのは無理そうですが、普通の探索は）

評価値について

　ツイートしたことをもう少し詳しく書きます。

・最初の五日は（どこにseedするか以外）他の人の真似をしています。

・250*score、100*sun

　最終的に1 point = 3 sunになるので3:1を目安にしました。ただ、sunが多いことが（特に序盤は）重要なのでこの値に。

　なお、score pointが重要になるのは後半なので、9日目までは0、10～19日目は上記の値、20日目以降はこの二倍にしています。

・木のsize別値を[5,115,245,420]として、(23-day)*本数*size別の値

　後者の式は、日が経つほどにscore（COMPLETE）の重要性が増すことからこうしました（日に関する一次関数で良いのかには議論があるだろうけど）。

　その後、ローカル対戦により調整したのが、この木の評価値です。たくさん自己対戦を行い、一番勝率が高そうなものを選んだというだけで、あまり根拠はありません。

・翌日～六日後に影がかかってsunがもらえない場合に-(7-day)*10*size

　六日後まで見て、（現状のままだと）陰に入ってsun pointが得られない場合にマイナスポイントをしました。

・自分の木同士が長さ3の線分範囲にある場合10*そういう木の本数分マイナス

　上位陣の対戦を見て、桂馬に木を配置しているのを見て、評価値に組み込みました。自分の木同士で陰になるのは避けた方が良いので。

・Richnessを補正（+Richness*1）

　木を植える場所はRichnessが高いところになるようにしました。ただ、陰に入るか、という方が重要なようだったので、気持ち程度の補正です。

AtCoder Heuristic Contest 003

 　リジャッジの可能性があるようですが、現在順位333位、パフォ1581で、レート1185→1307でした。

コンテストへのリンク

コンテスト後のツイート

　全然良い方法が分からず、分からないまま終わってしまった。

　ツイートの通りなのですが、

・各距離を推定した後、ダイクストラはしたい。が、PyPyだと間に合わない（コードテストでは間に合うのですが、実際に提出するとTLEする）。なので、Kotlinに書き換えた。

・距離は平均値を採用。たとえば、道1、道2で和が20と返ってきたら、それらの道は10にする。さらにその後、道2、道3で和が12と返ってきたら、道3は6に、道2はは10と6の平均の8にする……という感じです。

・今までに使っていない道は、初期値は5000、一回提出した後は、推定した距離たちの平均を使った。

　これで（pretest）で89点。なんとか90には乗せたくて、次のことをしました。

・上に書いた距離の推定だと、道2：8、道3：6で本当は話が12なのに、和が14になってしまう。その部分を若干補正（道2、道３とも若干減らす）しました。

　これでギリギリ90には乗ってくれました。

　本当は、各クエリごとに一次方程式が返ってくる感じなので、それら全てから距離を推定したいんですよね。だけど、その良い方法は思いつかぬまま終わってしまいました。

マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）

 　Dまで四完。直後にGCJがあるため、あまり疲れないように取り組もうと思っていた。さらに、問題を開くと、やや眠くて頭が働いていないことが判明。そのため、GCJへのウォーミングアップのつもりでゆっくり問題に向かうことにした。

　そのおかげ（？）か、このコンテストの順位はイマイチだったがGCJ Round2は通過できたので、作戦は成功。

コンテストへのリンク

D - Game in Momotetsu World

　コンテスト中にACできたものの、かなり苦労した。

　「ゴールからDP」という方針自体は結構早い段階で考えたのだけど、どういうDPをすれば良いか分からなくなってしまった。

・$DP[i][j]=(i, j)$からスタートしたときの自分$-$相手の最大値

　とすれば上手くいく。

　こういう「自分は利得を最大化し、相手は利得を最小化する」をミニマックス法というらしい。

E - Xor Distances

　「木DP」「各bitごとに見る」といったキーワードが思い浮かぶが、実際に解くのはなかなか難しい。コンテスト中に大体の方針は立ったつもりでいたが、実際の解法とはややギャップがあった。

　とはいえ、その二つのキーワードを思い付いたら、後は詰めていくだけ、という気もする。木DPの問題はいつも結構時間がかかってしまうのだけど、まあ慣れるしかないのかなぁ。

F - Insertion Sort

　すぬけさんの解説放送を聞いてAC。

　難しい。

・まず、一度も移動させない人たちを決める

　というのが重要だけど、それを思い付くことすらなかなか難しいと思う。

　その後は、

・平面にプロットして平面走査を考える

・DPをセグメント木を用いて高速化（セグメント木を使える形に変形するところも結構難しい）

　という流れ。

　こっちも難しくて、解説放送で方針を理解した後なのに大分実装に苦戦してしまった。

　後半パートは確かに典型なんだけど、この典型をささっと処理するのは容易ではないと思う。

　Codeforcesで何度か解いているはずだけど、毎回そこそこの時間がかかってしまっている。