ABC355-A、ケーキの盗み食い問題の解法を色々紹介していく。
おはこんばんにちは！ウルズニャーです！
私のAtcoderプロフィールはこちらから。
ABC-A問題は、競技プログラミングに慣れた人からすると簡単な問題ですが、簡潔な実装や賢い実装等、学ぶ所がたくさんあります。
今回、そういった意味ですごく良い問題に出会ったので、解法紹介記事を書いて行きます。
今回はあっさり読める分量で記事を書いて行こうと思いますのでよろしくお願いします。
問題
問題概要
ケーキ盗み食いの容疑者が三名（人１、人２、人３）居り、『この人は犯人じゃない』という情報が2件与えられる。
犯人が分かるなら犯人を答えよ、分からないならその事を報告せよ。
考察すべき事
2件の情報が同じ情報である場合、容疑者から除外されるのは1人である。よって犯人は分からない。
2件の情報が異なる情報である場合、3人中2人が犯人でなくなるのだから、残りの1人が明らかに犯人である。
解法の紹介
for文解法(私の本番中の解法)
まずは、犯人が定まるかどうか、3人分調べ上げる方法。
先に犯人が決まらないケースを弾く事で、単純なforとifで出来るようにしています。
この後紹介する天才的な解法を考えるのも良いですが、こういう愚直解をパパっと書く方が早かったりもします。
if文全列挙
実はこの問題。入力はたったの9通りしかありません。
なら全パターン場合分けしようぜ！というのがこの解法です。
正直コピペを上手く使えば、十分早くこの解法も実装出来ると思います。
ただ凡ミスしやすいので注意ですね。
if文列挙(改善版)
基本的な考え方は前回と一緒ですが、AとBが逆でも変わらない性質を利用し、大小関係に応じて入れ替えてから処理を行っています。
こうする事で、場合分けを減らす事が可能です。
大小関係で入れ替えるのは割と場合分け問題の定番テクニックだったりします。
setを用いる
お次はsetを使った解法です。
一番問題文で言っている通りを、忠実に再現した解法だと思います。
『A問は解けるけどB問が解けない！』という方へは、こういった問題でsetという構造について知っておくと、A問からB問へのステップアップがしやすいのでは？と思っています。
天才解法
さて、最後に天才解法を紹介して終わります。
私も自力では思いつきませんでした。
これを1秒で思い浮かぶ人が20秒ACとかするんでしょうね。
『犯人が特定出来るなら、1,2,3の合計である6から引き算』だって。
うん。頭いいね。
まとめ
最後の天才解法がすぐに思い浮かべば良いですが、実際そう上手くは行かないです。
なので、そういった解法はお勉強として知りつつ、愚直な実装を早くして行きたいですね。
実はこういった解法が複数ある問題は割とたくさんあるので、簡単な問題の解説も見逃さずに行きたいですね。
最後までお読み頂きありがとうございました！