突然ですが、いまでも(いまだに?)仕事でプログラミングしています。こちらの記事でも書きましたが、プログラミング歴だけは長いです。(^^;;
今回、いまさらながら、AtCoderにチャレンジしてみました！
AtCoderとは？
AtCoderとは、競技プログラミングと呼ばれるサービスの一つです。
競技プログラミングのWikipedia の説明は以下の通りです。
競技プログラミングでは、参加者全員に同一の課題が出題され、より早く与えられた要求を満足するプログラムを正確に記述することを競う。
時間をかけてアイデアを競い合うようなコンテストとは違い、プログラミングの早さや正確さを競うもののようです。
そういえば昔、アルゴリズムか何かの授業で実際にプログラムを書いて、その早さや正確さを競ったことが少しだけありますね(時代的に言語は FORTRAN や Pascal ですが…)。たしかに燃えましたし、解けたときの達成感が得られます。
AtCoderに登録さえすれば、あとは自由にコンテストに参加するだけです。基本は、土曜や日曜の21時から100分程度のコンテストが開かれているようです。
プログラムの審査方法は？
挑戦前、素朴に疑問だったのが、書いたプログラムをどうやって審査(テスト)するの？ということです。私が実際に仕事で書いているプログラムの場合、全部の論理を動作させて確認するので、かなりの時間と手間がかかります。
AtCoder(他の競技プログラミングも？)だと、早ければ数秒程度で自動で審査されるようです！
一体、どうやって実現しているのでしょう？
課題を見ればわかりますが、入力されたデータを加工し、結果のデータを出力するような、いわゆるファイルタープログラムを書くことが求められます。そして、事前に準備されたたくさんの入力データをそのプログラムに食わせて、期待通りの出力データを吐くかをテストするようです。いわゆるブラックボックステストですね。たしかにこの方法なら即座にテストができますね。
逆に言うと、コードの可読性などは問われません。実行速度も所定時間(ex. 2秒)内に動作すればよいだけです。極端な話、バグっていても入力に対する出力が期待通りであればOKです。ただ、その分、テスト用のデータを工夫してあるようですね。
（そういえば、テストの自動化という話はちらほら聞くので、私が情弱なだけで、一般には実施されてるのかも）
AtCoderにチャレンジ
早速、AtCoderにチャレンジしてみました。
AtCoder Beginners Selection
最初は、AtCoder Beginners Selectionです。
なお、競技プログラミングは早さを競うと言いましたが、このコンテストは初心者向けの常設コンテストで、特に時間制限などはないようです。(^^;;
かなり時間かかりましたが、なんとか全問正解までたどり着きました。。
参考までに、ソースコード(C言語)はこちらに置いてあります。
初心者の私がチャレンジしてみた感想です。
プログラミング以前に、アルゴリズムの問題として面白くて、解き甲斐のある問題ばかりです。
ただ、問題文がくどい(笑)ので、読んだだけだと頭に入らないことが多かったです。紙に絵を描いてみると理解が進みました。
あと、ソートの問題がよく出てきますが、比較回数を抑えるために工夫しなくてはいけないのか？とか考えて、結構ドツボにハマったりしましたが、普通のソート(バブルソート)でよかったりします。そもそも実行速度は所定時間内であればよいので、ある程度しらみつぶしに近くてもよさそうですね。処理時間がかかりすぎたり、答えが全然合わないときは、工夫が足りないのではなくて何かしらバグっているというパターンが多かったです。
practice contest
もう一つ、初心者向けのコンテストの practice contest をやってみました。
1問目の「A – Welcome to AtCoder」は AtCoder Beginners Selectionの1問目と同じようですので、残るは「B – Interactive Sorting」の問題だけです。ただ、この問題がくせ者でした！
まず、以下の注意事項がありました。
これはインタラクティブ形式の例題です。初心者向け問題ではありませんので注意してください。初心者の方は、AtCoder Beginners Selectionに挑戦してみてください！
入力が与えられて結果の出力を返すような通常の問題ではなくて、随時クエリを行いながら、最後の結果を導く必要があります。その関係で？、標準出力を毎回、flushしてやる必要があるようです。
こういったインタラクティブ形式の部分が初心者向きではないという意味かと思いきや、そうではないようです！ その辺のバグ取りが終わって、あとはソートするだけ…と思ったら、100/300点しか取れません。あとの残りは全て不正解(WA)と出ました。。クエリが規定回数を超えたら実行エラーとなるようにしていたつもりですし、どこが問題なのか見当がつきませんでした。
仕方なく、問題のところに貼ってある「コード例」を見てみたところ、バブルソートのようでしたが、こんな記載がありました。
以下のコードは、C++で100点を獲得するための例です。部分点を取得可能なコードなので、提出するとWAになります。
この例のように単純な論理だと、ソート自体はできても100/300点しか取れないようになっているようです。つまり、この問題は効率の悪いソートは不正解となるようです。クエリが規定回数を超えているためと思われます。
(自分でクエリ回数超過をはじいたつもりがバグっている？)
その昔、バブルソートは効率悪くてマージソートがよいと習った記憶がありますし、マージソートに書き直してみました。今度こそ行けるかなと思いつつ、これで提出してみると 200/300点でした…。冗長なクエリを無くすように工夫してみても、残りの100点の50個のテストデータのうち22個は不正解のままです。マージソートの限界かもしれません。。依然として格闘中です…(^^;;
それにしても、それをちゃんと検出できるテストデータも見事だなと感心してしまいます。
ちなみに、現状のソースコードは以下の通りです。
進展があれば、アップデートしたいと思います。
まとめ
今回、競技プログラミングのAtCoderにチャレンジしてみました。
本来、早さを競うもののようですが、まずは初心者向けの問題を時間をかけて解いてみました。それだけで結構お腹いっぱいですが、過去問などで傾向と対策を練ってコンテストで戦えるようになると尚楽しそうですね！ 引き続きチャレンジしていきたいと思います。
最後まで読んでいただきありがとうございました！
