ABC191の感想

AtCoder Beginner Contest191に参加しました。

問題はこちらから

Tasks - AtCoder Beginner Contest 191

結果はこんな感じでした。

abce4完(0wa)
順位：640 / 8807
パフォーマンス：1734

良くできたかなと思います。c問題の問題文がなかなか頭に入ってこずに焦りましたが、お絵描きをすることで何とか突破できたのが大きいのかな。あとは、順位表を見てEの方が簡単そう、ということで、Dを飛ばせたのも良い判断だった思います。また、今回のEがそうでしたが、この問題は昔のあれと同じじゃないかな？という見立てを立てられるようになってきました。すべてが同じというわけではないですが、過去問と対応させて問題を考えられている実感があります。これが成長というやつでしょうか。ただ、難しい問題を解いたからパフォーマンスが上がったというよりかは、早解きのために良い結果であることは肝に銘じておきます。確かに安定性の面で成長してますが、まだまだ難しい問題には手が出ません。

感想いきます。

A問題

消える魔球を打ちます。ボールを打てる範囲で消えてるかどうかを判定するだけですね。境界条件もシンプルですんなり解けました。前回はa問題でだいぶ苦戦しているので、まず一安心。

B問題

xを除いた数を出力します。それだけです。

C問題

これがだいぶ苦戦しました。グリッド上で塗られたマス目が作る図形が 何角形であるかを求めます。

まず、問題の理解が難しかったです。サンプルが四角形しかないため、

・・・・・
・・＃・・
・＃＃＃・
・・・・・

これが三角形なのか、八角形なのか悩みました。でも、人によって判断が揺らぐような図形は問題にはならないでしょ。と思い、これは八角形として考えました。

10分ぐらいまったくアイデアがでなくて、ずっとお絵描きしてました。

そして1つ目の案として、#の上下左右の・の数が角と対応する。という考えに至りました。結論から言うと間違っています。これだと上記図では対応しますが、サンプルの四角形では合いません。

角ができるのはどういうときなんだろう？という問題を解くために角の気持ちになって考えようと思いました。

・　・　・
　☆　☆　
・　・　＃

上記図の右上の部分です。マス目の四隅を☆としてこの☆の視点で考えると、☆の周囲の4マスの＃の偶奇で角が判定できる。ということがわかりました。結局これでacです。よかった。

D問題

いったん飛ばしました。

円内の整数座標を数えます。円の方程式を変形して

y = ±√(r^2-(i - a)^2) + b

となります。+の時は円の上半分、ーの時は円の下半分なので、＋の時の値からーの時の値を引けばその間の個数が出るかなと考えました。が、上手くいかず、、、結局時間切れでした。でもこの解法では浮動小数点の誤差でダメだっただろうなとは思います。まだまだだ、、

E問題

こちらの方がDよりも正解者が多かったため先に解きました。街 i から出発して同じ町に帰るときの最短経路を求めます。

経路でしたので、とりあえずダイクストラ法を念頭に置きました。あとは、結局はすべての街から出発をするので、多始点のダイクストラ法なのかなと、となると、過去問で似た問題があるな、と思いました。

F - Making Palindrome

この問題は橙なのでとっても難しいですが、最後に多始点ダイクストラ法を用います。ということで、この問題に沿って議論を進めました。

はじめは、すべての街にinfを書き込んで、すべての街から一斉にダイクストラ法を回しました。が、全然正しい答えがでず、、

考えてみればよくわからないことをしてますね。焦ってました。

そのあと、まず街０だけ考えてみようとなりました。再び0に帰ることができるかを判定しますので、街0から一つだけ進んだ街をダイクストラ法の初期点に投げ込んで回しました。探索終了後も距離がinfだったら -1、 そうでなければ距離を出力とやってみたら、上手くいきました。あとは、街の初期点を変えるだけです。すべての街で試しました。計算量が怖いなとおもいましたが、何とか通って一安心。

今思えば、多始点ってややこしい考え方じゃなくて、1回目の探索のみ距離を工夫すればいいのかな、という感じです。でもやってることは同じか。

今まで、ちょこっと忙しく解説記事をさぼってましたが、今回からまじめに書きます。もしよろしければそちらも読んでいただけるととても嬉しいです。