プログラミング始めて1か月の超初心者がPHP7技術者認定初級試験を受けてみたで、私はPHPを学び始めました。
そんなとき、AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～を読み、プログラミング自体を始めたばかりのくせにどんなものなのか試してみたくなってしまいました。
※この記事では本当の初心者が AtCoder を始める際に参考になる可能性がある程度の内容です。
※準備はそこそこにとりあえずやってみたいという超初心者の方が進めながら眺めるとちょうど良いかもしれません。
A - Welcome to AtCoder
登録が済むと、まずはチュートリアル的な課題に挑戦できます。
入力
入力は以下の形式で与えられる。
a
b c
s
……既に何言ってるかわからない。「以下の形式」って何。
超初心者の私は問題にたどり着くこともなく、早くも詰んだので解答例を見てみました。
見たこともなければ当然書いたこともないコードが載っていた。
調べてみると標準入力を受け取れって意味みたい。なるほど。
PHPで標準入力から値を受け取る(競技プログラミングとか)。なるほど。
よし、これでようやく問題に取り組めるぞ！
PHP7 を選択し、解答例とほぼ同じコードを書いて提出。
あれ、WA (Wrong Answer) になる。なんで？
……あー、PHP7 って言語を指定しても開始タグは必要なのね。
開始タグを入力して無事 AC (Accepted)。
AtCoder Beginner Contest
チュートリアルを終えて、
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
でおっしゃるように、ABC 042 からやってみることにしました。
(せっかく「過去問精選 10 問」してくれているのに、なぜかその10問を見ることなく。)
A、B、C はすんなりといけて、なんだ楽勝じゃん～と思っていたら、D で詰まった。
すんなりいけたとは言ったが、C はエレガントな解法がわからずめちゃめちゃ総当たり的に解いた。
大学入試の数学等を解くときには絶対にあり得ない解法。
とにかく計算量を少なくして、楽に解けるようにって頭の使い方ばかりして生きてきたので新鮮。
でも軽く調べてみると、この総当たり的解法は割と普通らしい。
動的計画法 Dynamic Programming
それなら詰んだ D 問題も、総当たり的に調べてやれば良いはず。でもどうやって総当たりを実装したら良いかわからない。
とりあえず諦めて、次の ABC 043 に行っても、結局 D 問題で似たような課題にぶち当たる。
さらに次の ABC 044 に行っても今度は C で似た課題に出くわす。
なんとなく詰んでいるポイントが似ていて、どれも同じような解法で解ける気がしたので、
仕方ないから先人から勉強するかぁと思って調べてみると、動的計画法を応用するらしい。
中学受験した人とかにはおなじみの最短経路を足し算して求めていくやつ。
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集
というすごくありがたい記事があったので読んでみます。なるほどなるほど。
イメージ的には、漸化式で解くのが DP 配列で、数学的帰納法で解くのがメモ化再帰ってことね。あくまで私のイメージですが。
(漸化式って言っても一般項を求めるわけではないので、結局はどっちも数学的帰納法のイメージかもしれません。)
それがわかれば、漸化式を思い浮かべながら Educational DP Contest の A 問題と B 問題はすらり。
C 問題は i-1 日目に幸福度最大の活動が複数あると i 日目の活動毎の幸福度によって i-1 日目の選択を変えなきゃいけない。
って思うんだけど、そうやって次の日のことまで考えると漸化式にならないから、
dp 配列の次元を増やして、高々 3 つの活動については総当たりしてしまおうという発想。
やっぱりこの総当たりという発想は慣れないとなかなか出てきませんね。
D 問題はイメージを掴むのに私は苦労しました。
その原因は恐らく、重さを for で総当たりするイメージが湧かないこと。
「重さ」という言葉がどうにも自然数に思えなくて、この記事にあるような表が全く思い描けなかったのです。
そこで、重さではなく値段とか、番号とか、自然数を思い描きやすいものに読み替えるとかなりスッキリしました。
そして、「イメージを膨らませて問題を解く」のではなく、「dp の表を埋める」と問題を読み替えてしまえばさらにスッキリ。
イメージしにくい立体図形や 4 次元以上の空間を、ベクトルを用いて代数的に解くようなイメージですね。
E 問題は D 問題と同じ……？
が、同じようにやるとメモリやら実行時間やらがすごいことになってしまいます。
解説を読んでみると、ランダウの記号が出てきたぞ・・・？
高校生の時に少しだけ微積分で出てきたけど、あまり深くは学んでいなかったオミクロン。
高校生のときにサボっていたツケがこんなところで回ってくるとは。
計算量オーダーの求め方を総整理！ 〜 どこから log が出て来るか 〜
なるほど、計算量オーダーという考え方なんですね。
成果が目に見えると嬉しい
そうして動的計画法も学びつつ、ちょくちょく AtCoder Beginner Contest の過去問を解き進めていっています。
が、なかなか D 問題をバシっと解けるようにはなりません。
そんな折、めちゃめちゃ簡単な D 問題に出会ってしまいます。
こんなに簡単でよいのかと恐る恐る提出してみるとしっかり AC される。
一応他の人の解答も見てみるかと提出一覧を確認すると……
おお、コード長も実行時間も大差で勝っている！
PHP は使っている方が少ないので、成果が見えやすくて嬉しいですね。
また、私のような初心者だとコードを書く技術では絶対的に劣りますが、
シンプルな解法を考えることで、コード長や実行時間で成果を出せるのも競技プログラミングの面白いところかもしれません。
(他の方はコンテストの限られた時間で解答を提出していらっしゃいます。単純に比較できないことを念のため申し上げておきます。)
月刊競技プログラミングは役に立たない？
少し競技プログラミングについて調べて見ると、Twitterのトレンドに定期的にこの話題が上がるらしい。
ベテランの方はどうかわかりませんが、私のような初心者であれば役に立たないなんてことは絶対にないと思います。
競技プログラミングでは極端に大きな値等を扱ったりすることもあり、
初心者が普段出くわさないようなエラー等が発生するので、そのときにいろいろ調べるきっかけになります。
例えば SplFixedArray を使うとかなりメモリを節約できるらしいとか、intdiv() なる関数が存在するとか。
他にも "恐らく" 素数の判定や、ビット演算子の使い方、合同式の復習等もできる。
競技プログラミングに限った話ではありませんが、どんなことにも学びはあるってことだと思います。
自分のタイプを知ることができる
競プロはいいぞ を読んですごく納得したのですが、
私は課題解決をしたい、そのためにプログラミングや数学を使いたいという人間なんだと思います。イメージ的にはコンサル？のような？
競技プログラミングをやってみて、楽しくなるならそういうタイプの人で、あまり楽しめないのであればモノづくりをしていきたいタイプの人ということなのかもしれません。
私の知人に最近 AtCoder を嗜んでいるって話をしたら、「好きそうだ」って言われたのはきっとそういうことなんだと思います。
独り言
せっかくだから土曜の夜にやってる AtCoder Beginner Contest に参加しようぜって知人に誘われた翌日の土曜日の話。
午前中に草野球の試合をして、帰ってきて昼寝して起きたら既にコンテストが終わっていた。