ABC206の感想
AtCoder Beginner Contest 206（Sponsored by Panasonic）に参加したので、その感想を書いていきます。問題はこちらから。
結果はこんな感じでした。
ABC（15:03+0WA）
順位：3241 / 9102
パフォーマンス：825
あまり良くない結果でした。３完という結果なのですが、反省すべきはD問題が解けなかったということよりかは、C問題までが遅かったということですね。なんかC問題をスマートに解くことができませんでした。灰色の問題は迷うことなく解法まで突き進みたいものです。
D問題はお手上げでした。想定解と全然違うことをしてました。でも、とっても面白い問題だったと思います。解けなかったのにそう思うのですから、恐らくそうなんだと思います。
感想いきます。
A問題
税込み価格で判断します。A問題にしては難しくないですかね。これって、小数点誤差は出るのでしょうか。
とりあえず、整数で計算して最後に100で割りました。
あと、何よりも大変だったのが出力ですね。
この金額が定価の206円より安いなら Yay! 、定価と等しいなら so-so 、定価より高いなら :( と出力して下さい。
遊び心を感じました。こういうの嫌いじゃないです。
B問題
貯金します。
一瞬だけ計算問題かな、と思いましたが、愚直の計算量を考えてみるとO(√N)ですね。ということで、一日ずつシミュレートしていけば答えが求まります。
これでAC。よし。
C問題
考察にそこそこ時間がかかりました。必要な要素として、各数字の出現関数があることは1分ぐらいで気づきました。ただ、「i番目時点における出現回数」をつかうということに気づくまで微妙に時間がかかりました。
なんか、こうすれば解けそうっていう直感というかはすぐに出てくるんですけど、詰めるのに時間がかかるんですよね。
まあ、これは実装力不足といいますか、精進不足といいますか。サボってるからですね。
10分ほど悩んだところで、上記の方針に気づいて無事AC。ちょっとだけ焦りました。
D問題
回文の判定です。
すぐには方針が浮かんでこず、10分ほどお絵描きをしてました。その結果、一つ目の方針として
回文になっていない箇所に出現する数字ー１
が出てきました。結局、回文というよりかは全部の数字を同じにしちゃえばいいじゃん！という方針ですね。
とりあえず、これを実装してみました。なんか違う場合ありそうだなーと思いながらもサンプルが通ったので提出。WAです。12AC19WAだったかな。
この方針で適切じゃないのは、
1 2 3 4 5 6 7 8
ですかね。これって上の方法だと7回となりますが、4回で回文が作れます。よくよく考えてみると、どんなに悪いケースでも半分の数字を変えれば確実に回文は作れますね。
ということで、上の方針と、回文になっていない箇所の半分のうち小さいほうを出力しました。
まだまだWAです。19AC12WA。さっきと入れ替わりました。
ここからが長かったです。40分ぐらいずっとお絵描きしてました。何とか、上記で適さないケースを見つけようと頑張りました。その結果出てきたのが
1 2 3 4 1 2 3 4
です。これは、方針１だと3回。2だと4回ですが、実際には２回で行けます。1を4に変えて、2を3にすれば、全部の数字を同じにする必要はなくなります。
これを実装するために
set<pair<int,int>>
を使いました。1-4と2-3がペアになっています。ここで、first<secondとすれば、3-2,4-1は消えますので、最終的にsetのサイズを出力すればＯＫです。
この３方針を信じて提出。結果はWA。19AC12WA。
ＷＡ数が減ってません。これには驚きです。ここで、ああ、場合分けしていくのはたぶん方針が違うなとうっすら思い始めました。が残り時間が10分ほど。
ここで時間切れです。残念。
想定はUnionFindみたいです。全然結びつきませんでした。
E問題
余りにもD問題が解けないので、ちょっとだけ覗きました。除いただけです。
F問題
見てないです。
あとがき
結果としては良くありませんでしたが、個人的にはとても楽しめた回でした。難易度傾斜も
灰灰灰緑青黄
と、なかなかに素敵な感じになっています。ちゃんと実力が反映される回で、ちゃんと実力がないことを示してしまったわけですが、まあこんなもんでしょう。「もっとできたなー」とか、「ミスったなー」感はありません。こんなもんです。
それでも悔しくないといえば噓になりますので、ちゃんと復習はしておきます。次にUnionFind出たときは必ず倒します。
また、今回は解答を書いていこうかなと思います。前回は見事にサボってしまったのですが、今週はまだ日曜日があります。明日中にはできる限り進めておきたいな、と思いつつ感想はこの辺でおしまいにします。
ここまでお付き合いいただきありがとうございました。
この記事が気に入ったらサポートをしてみませんか？