YU2TA7KA's BLOG ~take one step at a time~

派生開発、組み込み開発周りのこと。

入緑を目指している中でのポエム

先週末2回のAtCoderコンテストでレーティングを下げることしかできず、いろいろ思うことがあり、適当に書き散らかします。

緑に向けて過去問解いたり、螺旋本解いたりしていればそれなりに上がっていくだろうと思っていましたが、甘かった。特に問題に対する姿勢が甘かった。

「素朴に問題文を読んで解く」ではACできない。
「問題文を正しく深く読んで解く」ことでACできる。

問題文には、問われていること、入力、出力、制約が記載されており、それを読むことで素朴に考えた場合のシミュレーションが可能になる。が、そのままやってもACできない。結果的には計算が間に合わない、コーナーケースを考慮しきれていないなどでTLE、WAとなる。それで、そもそもそういうNG結果になるのは問題を正しく深く読んでいないことに起因すると思う。

問題は何を問われているのか、何の分野の議論をしようとしているのかを把握する必要がある。*1ひいては出題者の意図を汲み取る。出題者は解答者にこういうことを考えて楽しさを感じてほしかったのか、みたいな。出題者は問題になにか面白さ(宝物)を埋めて、解答者に贈っているはず的な*2

例えばC - Multiplication 3
f:id:yuji-tanaak:20200602061149p:plain

「素朴に問題文を読んで解く」ならばAとBを掛けて、整数出力する。当然これはWAになる。コンテスト中これをまさにやって、今思うとアホでしかない。考えが浅すぎる。
「問題文を正しく深く読む」ことで、これはコンピューター科学の丸め誤差に関する問題*3。誤差は入力時から発生している。だから整数として処理できるように実装しようと。考察していく必要がある。

文章にするとあまりにも当然のような気がしてくるが、コンテスト中全然できなかった。だからこんなポエムを書いてる。

なぜできないのか。。それは問われる分野の知識が薄いからかなと。AtCoderの問題はアルゴリズムとデータ構造、数学のいずれかを問われる問題が多いイメージ。例にしたようなコンピューター科学に関するものはたまによく出るようになってきた問題なイメージ*4

アルゴリズムとデータ構造に関しては螺旋本を読み進めていて知識が増えていると思う。一方で数学がノータッチすぎる。そして数学の範囲がだいぶ広い*5D - Div Gameは整数論で、その他にも確率、幾何とかたくさんある。言われると聞いたことあるくらいで全く知識になっていない。。数学に関する知識も深めていきたいぞい。数学ガール読めば良いと思っているがどうなんだろう?緊急事態宣言も解除されたし週末に買ってくるか。

と、知識不足なところがあるのでは?と振り返ってきたが、もう一つ重要なのが「気持ち」というふわっとしたものだと思う。

コンテストのA,B問題を解いているときは毎回勝手に緊張している。具体的にはタイピングが震えている。それはきっと、A,B問題は「素朴に問題文を読んで」実装できてしまい、それで提出しているからでは?その実装でA問題は通ることが多いがB問題はWAする。ここでも問題をちゃんと読めという話になってしまう。ただちゃんと読むということは時間をかけるということで、問題を解くのが遅いのは良くないとなる。ここで焦る気持ちが出てくる。コンテスト開始時間付近の気持ちは、開始前:ワクワク、開始直後:緊張、実装中:焦り、という感じでとてもよろしく無い気がする。。ここで早解きは捨ててA問題からそれなりに考察する、何を問われているかをノートに明記するようにしてみても良いかもしれない。B問題からでも良い気がするが、もうA問題からで。ふわっとした良くない「気持ち」の問題が少し見えた気がする。

以上、2夜の敗北(レーティング下げ)を受けていろいろ思うところがあり書きました。ポエムを書いて自分の弱点、問題を解く姿勢が少し整理された気がします。次のコンテスト前はこれを読み直してから挑戦してみようかと。


こんなポエムをここまで読んでいただきありがとうございました。

*1:うまい表現ができない

*2:B - Multiplication 2はどんなに大きな数字を掛けても1回でも0をかけると答えは0になる、のが宝物と思った

*3:chokudai(高橋 直大)🍆 on Twitter: "整数を2進数で表現する時、各桁は1,2,4,8,16....ってなるんだけど、これを後ろ側に拡張すると、0.5,0.25,0.125....ってなってくのね。 これで0.1とか0.01を表現しようとすると、実はぴったり表現することが出来ないので、誤差が出ちゃいます>< https://t.co/qs9a10xcJF"

*4:C - Sqrt Inequalityでも同様にコンテスト中にACできなかった。

*5:あとは実装方法に関する知識も必要か、実装しやすい言語を知っていてそれを選択できるというのもできると良さそう。