133競技プログラミング結果E問題までの5完で157位。F問題が難しい(というか重実装だった)影響でEまで早く解けていればそこそこな順位になった。始まる前から疲れていて不安だったがなんとかなってくれて良かった。根号取ったものが整数になるか判定するところでやや悩み、結局普通に2乗が超えるまでループで回してみて一致する整数があるか判定した。計算量は確かめてないけど小さめだったからなんとかなるだろうという勘。解説PDFを見るにそれで良かったようだ。提出C問題が2019より大きいかどうかで場合分け。大きいとまずいので制約に救われた。手癖で全ての整数型をll(int64_t)で確保するという脳死ムーブが強すぎるのでメモリ量で痛い目を見たい。適切にぐちゃぐちゃやっていけばなんやかんや式が立ちそうだなとは思ったが全然上手くやれなくて呆れながら解いていた。山1の右半分へ流れる量を変数においてヒュッとやるのが最終的にはわかりやすかったか。提出E問題わりと何も考えず再帰関数の中でダメな条件を順番に弾いていくとなんとかなった。これが早く解けたのが順位的には大きかったけどよくわからないままに通ったという感じでやや釈然としない。いいことだけど、エッジを辿る場面では次のノードをnextと命名することが多いんだけど普通にstd::nextが存在するのでやめたほうが良さそうだなとAtCoderのシンタックスハイライトを見ていて思った。提出F問題パッと見で最小共通祖先を使うんじゃないかなという感じで、考えていくとなかなか惜しいところまではいく。なるのでいやー難しいと思っているうちに時間が経ってしまった。このあたり疲労感が強くて椅子に座っていられず寝転がって(つまり紙とペンを使わず)考えていたもの響いたか。必要な情報をメモしておいてDFSしながら答えていけばなんとかなるかもしれないとは思ったけど実装が非常にやばいことになりそうで手を付けるか迷っているうちに残り20分くらいになる。そこから書き出したが時間切れで終了。解説PDFを見て結構方針としては合ってそうだった。想定した書き方をしてACする。AtCoderで150行近く書くのやば。日頃変数はmainスコープの中で書き始めるので再帰関数を外に書こうとすると変数をグローバルに置き直す作業が必要になったりするのがちょっと嫌。最近は単純なDFSならstd::stackを使って書いているんだけど、色情報を一つ持って更新しながらやっていくには再帰関数で書く方法しか思い浮かばかなかった。main関数の中にラムダで書いてみたけど、これもどうだろうか。最小共通祖先はこれで検索して一番最初に出てきたページをほぼそのまま写経した。原理は全然わかってない。ライブラリを整備する元気もあまり出ず。int64_t;すら消したいよなという気分にすらなっていて......。41分50秒(0WA)で全完、82位だった。頂点の木が与えられる。月別アーカイブはてなブログをはじめよう!tokuminiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。