タイトルの通りです。4問時代であるABC125までが全部埋め終えられましたので、振り返りも兼ねてリストアップ。
当たり前ですが解き方に関してはネタバレがあります。ご注意ください。 埋め込み形式で貼り付けてますので、問題だけ見たい人はそちらから行くといいでしょう。
枚のトランプを昇順に並べ替えるために、任意の一枚を抜き取って任意の場所に入れるというソートをしていく最小回数を求める問題。
問題の解釈はいろいろ考えられつつも行きつく解法は超超典型問題。とても好きでした。
頂点の高橋君が、指定された
と連結でなくしたい。できる操作は頂点をなくすか辺をなくすこと。
これはフローの典型として教科書的な問題として人におすすめしたいなーって思える問題です。まず作成したらこちらでverifyしていいでしょう。
インタラクティブだー！…これくらいしかなかったんじゃなかったかな？125までやる人なら手出ししてもいい感じがする！
解法自体は知識ゲーです。木の直径の求め方はもうテンプレとしてありますので。
おすすめというよりは橙パフォなのに解けたのが嬉しかったなというもの。 約数を求める問題にはありがちなんですが、数字の大きさに対してその約数の個数と言うのは結構少ないんです。
上記が素晴らしいまとめをしてくれているのですが（さすがアルゴ式～～～～）
までなら
個程度で
程度なら余裕だし、
までなら
未満で
も余裕だし、
までなら
未満なので、定数倍が小さくなるならこちらも
がいけなくもない量です。
それ以上はちょっと約数を求める行為自体にかかるのでちょっと厳しいですが。
最大値の！ 最小値は！ 二分探索！
説明！！（省略）（いい典型ですね）
食塩水の方も「境界さえ定まっていればそれは判定できる」といったもので典型的な二分探索になります。
浮動小数点を要求する二分探索もそこそこありますよね。私は試したことがないのですが、答えに相対誤差を要求してくる場合は、二分探索の中央部分の計算をではなく
にして、ループの脱出も相対誤差で解決するようにすると誤差で殺されることもなくなりそうなので便利そうですね。
木DPの典型良問です。是非とも慣れてみてください。
当時ではなく現在のD問題（緑～水diff）で出てきてもおかしくないテクニックを全て組み合わせると解ける問題です。とても良問だと思います。
これは数学ゲーです。この感覚を覚えているだけでもだいぶ変わる問題は多そうです。
今でもARCのCあたり…だと少し簡単かな？適切な累積和をちゃんと保存していく良い問題です。両側で解いていくっていうのも重要。
魔物を倒すのに爆発を起こしまくる。爆発の中心部の魔物はダメージを喰らい、それ以外は
くらう。なお常に
良問！良問です！！！単に適切な魔物を選ぶんじゃどんどん効率が悪くなってしまいますので、いっそのこと「魔法を発動する回数」を固定してしまうと二分探索に落とし込めます！！
マジで天才だからやってほしい
ソートを信じろ
基数ソートは正義だ
おすすめしづらい高難易度ですが好きでしたので
これもめっちゃ難しいんでご注意。上二つと比べて実装難も加わってるから尚更。
上記の食塩水や射撃王の問題もそうなのですが、境界線が明確になっていれば簡単な問題は二分探索です。
全ての値を0,1にするタイプの二分探索なので、典型と言えば典型なのですがかなり難しい問題だと思います。
たーけたけたけたけたけたけたたたたーのしいたけからはじめましょーう
Cらしからぬ普通にムズい問題です。制約が異常に小さいことにピックアップできればどの竹をA,B,C,使わないの4通りのどれに使うかで場合分けにたどり着くことができますがを実装するのは普通に重いと思います……。
でも良い問題だと思います。
種類、
種類、
種類のケーキがあってそれぞれに美味しさがあるので、それぞれ
通りのケーキの選び方で上位
番目の美味しさを出せ
特別難しい点はないんですが、面白い問題だと思います。解説を読むとなんと4通りも解き方があります。特に解法2がすき。
以上、振り返りでした。 しかし私二分探索好きですね。
