脳log[20250525]

2025年05月25日 (日) [AtCoder] 今日は AtCoder Regular Contest 198 (Div. 2)。■A 問題 I hate 1。こういうのをギャグというのだろうか。AtCoder で一発ネタを見ることってない。たとえば２を追加するとすべての奇数が追加できなくなる。一方で、２の倍数は余りが０なので追加することができる。なので S の要素は素数の倍数が良さそう？ ほぼ半数を要素にできる２の倍数以上にすぐれた選択肢ってある？ 問題の難しさを認識することさえできなくて過度に単純化した結果 WA を出すというのが ARC あるあるだしなあ、でも 300 点問題だしなあと数分逡巡してから(反例となる素数の組み合わせも見つからなかったので)提出して AC だった。■B 問題 I hate 1。問題を読んで具体例を確かめていくと、0110 と 0[1]2[1]0 しか作れないとわかる。２の両隣の１はオプション。0 はいくつ連続で並べてもいいので、11 と [1]2[1] を 0 で区切るイメージ。まずは消費の仕方が限られている２を消費したい。２を消費するのに十分な０の数は２と同数。これは数列が環状に循環しているから。次に１を消費したい。２の両隣の１はオプションだから、２の倍の数までは何も考えずに消費できる。余りは 11 として２の島と同様に同数の０で区切る必要がある。余りの１が奇数個の場合が面倒。２の隣の１をひとつ持って来られるなら良し。持って来られない(２がゼロ個)なら即座に No。実装ミス(A = A-B-B を A -= B-B とした)と勘違い(ひとつのことを実装しているあいだにもうひとつのことが曖昧になっていくせい)で２ペナ。■本日の ARC は終了です。時間をオーバーして C 問題の実装を終わらせたけど、シャッフルした順列をソート済みに並べ替えようとすると最後の２要素が一致しない。操作対象が２要素だけだと自由度がなくていけない。１要素を加えた３要素を手で操作してなんとかできないかやってみたけどどうにも完成させられなかった。えっ？ 全体の和が一致していても不可能なケースがある？(ないよね) N=2 だけでなく N=3 も場合分けが必要？