Codeforces Round #776 (Div. 3)

　Eまで五完。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round #776 (Div. 3) F飛ばしたらGが解けず終了。えー。
A cの位置が奇数番目にあるか？
B rか、余りがa-1で最大のものを使う
C ソート
D 後ろから見る
E 間の日数が最小なものを挟むどちらかを最後か、間の日数が最大のところへ移動させる。最小が三つ以上あれば移動しても得しない。

— titia (@titia_til) March 8, 2022

　Fは未読。

G. Counting Shortcuts

　自力AC。最初の提出はmodの取り忘れでシステムテストで落ちたが、まあ。

　個数を調べるのはDPでやるしかない。最短距離の経路の個数を調べるならDPで求められる。

　問題は、最短経路+1のものをどう求めるか、だが、これも同じような感じでDPするしかなかった。

　スタートから同じ距離のもの同士を結ぶところで+1用のテーブルに遷移させ、後は同じようにやる。

　コンテスト中も似たようなことを考えていたのだけど、最短距離+1の経路になるかどうかを判定するところで、スタートとゴールから距離を調べる系かと思って混乱してしまった。