4完。
トラブル
悲報
— Toy (@mdstoy) 2021年7月10日
お家のルーター落ちてしまう
ABC間に合わん
— Toy (@mdstoy) 2021年7月10日
ルーターを再起動しながら、慌ててスマホで問題を開き、再起動が完了するまで実装をため込み。致命傷には至らず・・・。
各問題
A - Counting
max(0, B - A + 1)
答えがないときの処理がポイント。
B - Can you buy them all?
愚直にシミュ。
C - Not Equal
数弱には辛い問題・・・。
Cをソートして、C_i < iとなるiが存在したらそこがネックとなり答えは0です。
そうでない場合、c_i - (i - 1)をかけ合わせたものが答えです。なお、なんでそうなるのかはよくわかってません。
D - Collision
Cより簡単なんですが！？
まず前処理で、任意の頂点を根としてそこから各頂点の深さをdfsで求めます。
あとはクエリ毎に頂点の深さの偶奇を調べ、同じなら"Town"、異なるなら"Road"となります。木は二部グラフであることを利用しています。
E - Shiritori
ゲーム系の典型である、後ろから見る方法で確定できそうな気がしましたが、半分くらいACを取るのが限界でした。
あと順位表見て心が折れた
いやでもこういう解けそうな問題でもうひと踏ん張りしないとだめですね。
F - Deforestation
何もわかりません。
まとめ
ルーターが落ちるというアクシデントはありましたが、Dが得意な木のdfsだったので命拾いした感じです。
