日立製作所 社会システム事業部 プログラミングコンテスト2020

　Cが解けなかった上、Aで1ペナ出してしまい、レートを大きく下げてしまった……。それでも黄色に留まれたのは失敗に優しいと言われるAtCoderのレートシステムのおかげ。

コンテストへのリンク

C - ThREE

　コンテスト中、「木が二部グラフである」ことを利用することはすぐに思いついた。両方の色がN/3より大きいときの考察は上手くできていた。

　だが、片方の色がN/3より小さいときの方法を思いつかなかった。余り1か余り2のものを少ない方へ割り振らなくてはいけない気がして、少ない方に3の倍数を割り振る発想が起きなかった。

　そのせいで、もっと細かい連結成分をみたりしなくてはいけないのでは？　と迷走。

　割り振るべきものは、「3の倍数、余り1、余り2」の三種類、色は二種類ある、ということを落ち着いて見直すべきだった。

D - Manga Market

　解説AC。

・ソートしてDP

・（待ち時間が）指数的に増加することに気付くと計算量を減らせる

　の二つを組み合わせた問題。

　どちらもそれほど発想し難いものではないけど、落ち着かないと厳しそう。

　特に前者については、

・とりあえず立式

　が重要。

E - Odd Sum Rectangles

　解説AC。

　公式解説動画を見ても、どうすればこの構築を思いつくのかが分からなかった。

　けど、正当性を証明することはできるので、こういう構築方法があると頭に入れておくのが良いのかな。

F - Preserve Diameter

　解説AC。解説を読んでからACするまで一週間以上かかっている気がするんですが、さすがに非効率過ぎない……？

　公式解説動画を（何度か）見れば、どういう計算をすれば良いかは理解できると思う。この問題は、発想するのは難しいけれど、解説を理解するのはそれほどではない、という印象。
　あとは確かに木DPをするだけなのだけど、その実装が難しくて戸惑った。

　解説pdfやkmjpさんの解説記事に書いてある通りなんだけど、それでも難しいと思う。

　自分の実装はこんな感じです。

・まず、木の中心を見つける。(cとする。今回は中心が一点のときを書く)

・cからDFSする。親や、cからの距離を求めておく。直径をDとする。

・葉から木DPを行う。

　DP[x][p][m]($0\leqq p\leqq 2,0\leqq m\leqq 2$)を、頂点x（の部分木）まで見て、cからの距離が+D/2の葉がp個、cからの距離が-D/2の葉がm個のものの場合の数、とする。

　ただし、p=2, m=2は+D/2の葉が2個以上、-D/2の葉が2個以上、の意味。

　なので、最初に葉を見るとき、cからの距離がD/2か、そうでないかで初期状態を変える。あとは、一つ親のノードへ移るとき、この3*3の行列の遷移がどうなるかを考えれば良い。

（遷移もかなり難しいけど、辺に「+1, 0, -1」を割り振るとどうなるか？　と、子が二つ以上あるときどうなるか？　をちゃんと考えれば分かった）