baitop https://blog.hatena.ne.jp/baitop/ バイトの競プロメモ https://baitop.hatenadiary.jp/ 順列 ARC_パズル 貪欲 解けなかったので、こういう流れで解きたかったという妄想を書きます C - K Derangement 分かりやすさのために、以降i=0~N-1で0~N-1の順列を並び替える問題として考えます 解説 問題文で問われているのは辞書順最小なので、先頭からなるべく小さい数を入れていきたいです。 上のグラフは横軸がiの値、縦軸がAiの値で、赤線が理想の配置です i=0~K-1の時は Aiにi+K以上の値しか使えないため、Ai = i+kとするのが理想で i=K~2K-1の時はAiにi-Kも使えるようになるので、Ai = i-Kとするのが理想です i = 2K ~ N-1以上の時は、Aiとして使える値も2… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fbaitop.hatenadiary.jp%2Fentry%2F2022%2F07%2F17%2F183001" title="AtCoder Regular Contest 144 C - K Derangement - バイトの競プロメモ" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn-ak.f.st-hatena.com/images/fotolife/b/baitop/20220717/20220717171354.png Hatena Blog https://hatena.blog 2022-07-17 18:30:01 rich https://baitop.hatenadiary.jp/entry/2022/07/17/183001 1.0 100%