コンテストページです → https://codeforces.com/gym/272327
結果
ノーペナ全完 1 位です。
これは 「† 注意力 † コンテスト」である旨を事前に伺っていましたから、正確さに全振りをしました。 もちろん 5 問とも瞬殺レベルの難易度なのですが、速さ度外視で、全部証明 ＆ 小さいケースのテストを怠りませんでした。
ところで
これの直前にこちらのコンテストがありました。
【告知】
— くそなぞなぞ Beginner Contest (@BeginnerContest) March 14, 2020
くそなぞなぞ Beginner Contest 001 を開催します！
・開始時刻: 2020/03/15(日) 21:00
・コンテスト時間: 30分
・問題数: 6
・writer: @dem08656775, @ricky_quikem
配点は 100-200-300-400-500-600 です。
皆様、是非ご参加ください！https://t.co/D2m4LJCjtH
くそなぞなぞ Beginner Contest のあとで † 注意力 † コンテストに参加する日曜日の夜、なんですか？
A - Pizza, Pizza, Pizza!!! (00:03:21)
基本的にはピースの数だけナイフを入れる必要があるのですが、偶数個に切るときには 2 箇所一気に切れますから、割る 2 です。切らない場合がコーナーケースです。
B - Two Substrings (00:13:11)
AB, BA の出現位置を全列挙です。両方とも 2 つ以上あれば YES です。そうでない場合は積集合を全探索しても間に合います。私の実装ですとコーナーケースはないのですが、考察パートはかなりややこしいです。
C - Wonder Room (00:23:07)
短辺を全探索です。 a と b のどちらが短辺側であるのか 2 通りを両方ためします。入りきっていなければ大きくします。 こちらも私の実装ですとコーナーケースはありません。スワップをためし忘れるなどでしょうか。
D - Cloning Toys (00:36:31)
普通に難問です。 雰囲気で実装をして落ちるにはこわいですから、構築をしました。 操作を逆から見ていきましょう。可能な操作は
- x が 3 以上のとき、x から 2 を引きます。
- x が 2 以上で y が 1 以上のとき、それぞれから 1 ずつ引きます。
これを繰り返して (x, y) = (0, 1) にできればよいです。
まず、x + y が奇数である必要があります。 さらに、x のほうがたくさん引きますから、y - 1 <= x です。 y は最終的に 1 ですから、 1 <= y です。
逆操作の構築です。まず、y-1 と x の差は必ず偶数ですから、これらが等しくなるまで x から 2 を引き続けます。 ただし、y=1, 0 < x のときがコーナーケースで、この操作を行うことができません。 最後に、y と x から、1 ずつ引くを繰り返して、AC です。
E - Treasure Hunt (00:50:41)
まず問題文読解パートが難関で、突然出てくる "cat" に、私は戸惑いました。 結局よく分かっていないのですが、問題だけはわかりましたから、良しとしましょう。（はい！？）
一番多い文字に揃えるとよいです。編集距離を貪欲に減少させていきましょう。 手数が余る場合は、a → b の代わりに a → c → b と回り道をして稼ぎましょう。 ただし、 全部同じ文字で n = 1 のときがコーナーケースで、このときには編集距離を増やすしかありません。
正直なお話、これは初見で気づけたかはわからないのですが、† 注意力界の典型問題 †（それはなんですか？）ですから、息を吸うように回避です。
