結果
E問題までの5完で157位。パフォーマンス2118でレーティングは1854 → 1883 (+29)。F問題が難しい(というか重実装だった)影響でEまで早く解けていればそこそこな順位になった。始まる前から疲れていて不安だったがなんとかなってくれて良かった。
A問題
そうですね。
B問題
根号取ったものが整数になるか判定するところでやや悩み、結局普通に2乗が超えるまでループで回してみて一致する整数があるか判定した。計算量は確かめてないけど小さめだったからなんとかなるだろうという勘。解説PDFを見るにそれで良かったようだ。
C問題
が2019より大きいかどうかで場合分け。小さい場合にループ中で普通に掛け算してから剰余計算してしまったが
が大きいとまずいので制約に救われた。手癖で全ての整数型を
ll(int64_t)で確保するという脳死ムーブが強すぎるのでメモリ量で痛い目を見たい。
D問題
適切にぐちゃぐちゃやっていけばなんやかんや式が立ちそうだなとは思ったが全然上手くやれなくて呆れながら解いていた。山1の右半分へ流れる量を変数においてヒュッとやるのが最終的にはわかりやすかったか。
E問題
わりと何も考えず再帰関数の中でダメな条件を順番に弾いていくとなんとかなった。これが早く解けたのが順位的には大きかったけどよくわからないままに通ったという感じでやや釈然としない。
どうでもいいことだけど、エッジを辿る場面では次のノードをnextと命名することが多いんだけど普通にstd::nextが存在するのでやめたほうが良さそうだなとAtCoderのシンタックスハイライトを見ていて思った。
F問題
パッと見で最小共通祖先を使うんじゃないかなという感じで、考えていくとなかなか惜しいところまではいく。しかし各色について各ノードまでに辺が何本あるかを保持するとになるのでいやー難しいと思っているうちに時間が経ってしまった。このあたり疲労感が強くて椅子に座っていられず寝転がって(つまり紙とペンを使わず)考えていたもの響いたか。
必要な情報をメモしておいてDFSしながら答えていけばなんとかなるかもしれないとは思ったけど実装が非常にやばいことになりそうで手を付けるか迷っているうちに残り20分くらいになる。そこから書き出したが時間切れで終了。
解説PDFを見て結構方針としては合ってそうだった。ほぼ想定した書き方をしてACする。AtCoderで150行近く書くのやば。
日頃変数はmainスコープの中で書き始めるので再帰関数を外に書こうとすると変数をグローバルに置き直す作業が必要になったりするのがちょっと嫌。なので最近は単純なDFSならstd::stackを使って書いているんだけど、色情報を一つ持って更新しながらやっていくには再帰関数で書く方法しか思い浮かばかなかった。main関数の中にラムダで書いてみたけど、これもどうだろうか。
最小共通祖先はこれで検索して一番最初に出てきたページをほぼそのまま写経した。原理は全然わかってない。ライブラリを整備する元気もあまり出ず。マクロとかスニペットとか自動サンプルチェックとか、そういうのも入れた方が良いんだろうなとは思いつつ、しかし最近はむしろusing ll = int64_t;すら消したいよなという気分にすらなっていて……。
