Thanks Kosen 2020

　ツイッターで見かけたので参加。
　今見たら、Gも解けるべき問題でした。ただし、実装は大変ですね。

コンテストへのリンク
コンテスト後のツイート

E - インターン

　端での挙動を考える。

　一番端のゲートから出てきたとき、その次に向かうゲートはその隣のゲート以外ない。一番端とその間の座標からスタートし、最初に一番端のゲートに入った場合も、めぐりめぐって、隣のゲートから元の位置に戻ってくる。

　ということは、端のゲートとその隣のゲートは連続して通ることが分かる。なので、ゲートを二つずつペアにして考えれば良い。

F - 卒業RTA

　科目群と全体とで二回DPすれば良いということは分かるけど、実際に実装しようとするとなかなか大変。

　コンテスト中苦労したけど、どの辺りがポイントだったかは覚えてません……。

G - 答辞

　今やったら自力でACできました。

　累積和と二分探索を使えば、「各indexが左端のとき、右端はどこより先か」、「各indexが右端のとき、左端はどこより先か」が分かる。そう整理すると、このブログで何度か引用しているアルメリアさんのこの記事に帰着できる……と思って見に行ったら、この問題も例題として扱っていましたね。

　何度か似た問題を解いたおかげとはいえ、自力でこの方法だと気付けたのは嬉しい。ただ、実装にはかなり時間がかかってしまうんですよね……。このタイプを早く解くのは厳しい。