ゼロから始めるAtCoder 第1回 【私的発想の転換】
※きっと水色コーダーになる私の、駆け出しからその時までを描く日記でございます。どうぞ温かい目で見守ってやってくださいませ。
こんにちは、におーだちです。
一昨日のABC132が、私にとって競技プログラミング初陣だったわけですが、結果は。。。
A,B,Cを17分で解き終え、D問題に残り時間をすべて費やしたものの解けずに敗北。
その後出回っている今回の難易度評価を見ると、ABCはとても簡単だったようですね。。。
私にとってこのD問題が当面の目標となる問題でしょうか。
さて、今回書きたいことは、競技プログラミングの勉強を始めて最初に出会った衝撃です。
こちらの問題。
現在AtCoder Problemsで、ABC-ABの全埋めチャレンジをしている最中なのですが、この問題。
あぁなんかこんな問題、中学受験で解いたなー、
条件に当てはまる組を一つ見つけて、それで500円硬貨一枚を100円硬貨に置き換える組と、100円硬貨を50円硬貨にしていくのを書き出していって。。。
。。。さて、この問題、精選問題10選にも選ばれていました。
このcoinの解説を見たとき、私的衝撃が走りました。
なるほど、全通り、くまなく計算させてしまうのね。。。
最近、計算量の勉強を始めましたので、アルゴリズムとか計算量とかまだまだ分からないことだらけなんですが、いわゆるこれを全探索というのでしょうか?
この方法を知ってから、B問題もサクサク解ける気がします(B問題までは情報量がそんなにおおくないから全探索で解けてしまうような気がします。)
ない頭で考えると足元すくわれるぞという事を、学んだような気がしましたとさ。