AtCoder Beginner Contest 101 にリベンジしてきた話

Atcoder

始まり

事の発端は先週に遡り、

 

こちらのツイートを見かけて、せっかくなのでABC100に参加してみました。

 

コンテスト自体は、実はプログラミングを始めてから、

過去に3回ほど受けたことがあり、

そのときはB問題までは解けるけど、C問題は厳しいくらいの感じでした。

 

そして、参加直後のツイートがこちら。

 

 

 0点でした。

 

言い訳をすると、A問題の内容を勘違いしてたというのもありますが、

何よりケーキの取り方のアルゴリズムがなかなか思い付けず……。

 

さすがにこの結果は悔しかったので、

ちゃんとプログラミングコンテストに取り組んでみようと思ったのでした……。

 

 

課題とやるべきこと

まず、AtCoderの勉強方法で調べたところ、

初心者向けにおすすめされていた、

 

・「過去問精選10問」を解いてみる

・「アルゴリズム」の勉強をする

 

をやってみました。

qiita.com 

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

 

  

「アルゴリズム」の勉強に関しては、

評判の良かった「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」

という参考書を使用してます。

 

まだ読み始めて5日ですが、

理解するのに少し時間はかかるものの、結構楽しく進められてます。

 

ただ、これらの勉強をしていて、

新たな弱点が浮き彫りになりました。

 

僕はそもそも数学ができませんでした。

 

高校時代はもっぱら赤点で、受験もしてこなかったので、

上記の参考書の解説を読んでも、理解できないところが出てきます。

 

（例）

参考書「1 + 2 + … N-1 = ( N^2 -N ) / 2 と、なり」

ぼく「なんで？」

 

参考書「オーダーがO( √n )、O(logn)、」

ぼく「log？」

 

なので今は、プロコンの勉強をする前に、

一日45分くらい、数学の勉強をする時間を設けています。

 

とりあえず、コンテストに関係ありそうな「場合の数」から始め、

今日は「順列」を覚えました。

異なるN個のものからR個取り出せるようになったので、

恥ずかしながら、かなり役立ってます。

 

 

リベンジしてみた

一週間の修行期間を経て、かなりモチベの高い状態で当日を迎えました。

AtCoder Beginner Contest 101 - AtCoder

 

かなりモチベの高い様子↓

 

A問題

与えられた4つの記号で、インクリメント、またはデクリメントするだけだったので、

これはスムーズに解けました。

 

B問題

B問題では、まさに修行の成果が発揮できました！

 

与えられた整数Nの各桁の和を求めて、

Nをその和で割り切れるかという問題だったのですが、

 

各桁の和の求め方は、

AtCoder Beginners Selection - AtCoder

の第5問「ABC083B - Some Sums」でやっていたのです。

 

10で割った余りで、一の位の桁が取得できるということに、感心していたのでよく覚えています。

 そのときは、まさに「あ！これ進研ゼミでやった問題だ！」みたいな感覚でした。

 

B問題もスムーズに解いて、ジャッジの経過も待たずに、駆け足でC問題へ移りました。　

 

C問題

難しかったです。

 

1,2,…,Nを並び替えた数列から、k個の連続した要素を取り出して、

その中の最小値ですべて上書きする操作を繰り返し、

すべての値を等しくしたい。

その必要な操作の回数の最小値を求めよ、という問題でした。

 

そのとき考えていたのは、

最初に、配列の先頭から、k個の連続した要素のグループを操作する。

次に、そのグループの最後の要素を先頭にしたグループを作り操作をかけ、

それを末尾まで繰り返すという方法でした。

 

ただ、この処理だと、最後の1回でK個の要素を取ろうとしたときに、

配列の末尾を超えて、配列エラーが起きてしまう可能性と、

要素の先頭からK個以内に、数列全体の最小値がないといけないことに注意しないといけません。

 

試行錯誤の末、試験終了1分切ったタイミングで、

ギリギリ完成して、テストする間もなく滑り込ませて提出しました。

 

これが実際のコードです。

 

一つの提出で「AC」「WA」「TLE」「RE」すべて網羅しました。

 

最小値を先頭に持ってきたかったので一旦ソートしましたが、

それだけならすべての要素をソートする必要ありませんでしたね……。

  

D問題 

たどり着けませんでした。

 

 

結果

f:id:a2606:20180624223300p:plain

 

 C問題は解けなかったものの、A問題とB問題は解けたので、

一問も解けなかった前回に比べたら大躍進ではないでしょうか。

 

って、あれ？

 

提出結果を見たらB問題が「WA」になってる！！！？

 

B問題は知ってる問題だったので、早くに答えてC問題へ進んでいましたが、

C問題を試験ギリギリまで提出していなかったので、

B問題のジャッジの結果を一度も確認していなかったのです……！

 

ちなみにコンテスト終了後のツイートです。

 

【成績】

100 / 1000点

1586 / 1664 位

 

 

終わりに

今回もまた、残念な結果に終わってしまいました。 

 

ただ、もちろんプログラミングコンテストはこれからも続けてみます。

現段階の目標は、「C問題まで解けるようになる」です。

 

それでは。