研究室の友達に誘われてGoogleCodeJam2011@Japanなるものに挑戦してみました。
多量のデータから数値計算するコードなんて今まで書いたことなくて、更に言うとPython(macbook Pro使ったとかいろいろな関係で)なんて初めて触るような言語で、色々苦戦しましたが楽しかったです。
A問題small
カードシャッフルをして、最後に上から何番目のカードが何？という問題でした。
最初は普通に言われた通り(M枚のカードのA枚目からB枚目のカードを山の頭に持ってくる)の実装を行って、その結果、M要素のリストのA番目からB番目までの要素をカットしてリストの先頭にくっつける、というコードを書きました。
問題表記上でのA枚目はリスト上ではA+1要素目であるとか、上からX番目のカードの数字は？と答えるところをXのカードは上から何番目にあるか答えたりだとか、実行したあとの出力結果をファイルに保存する必要があるのを忘れて提出期限の4分オーバーしたりと色々酷いこともしましたがなんとか正解出せました。
A問題large
10^9がナチュラルに出てくるラージ問題、当然のこと先ほどのコードでは動きません。
既に解答が出ているらしく(まだ確認していないのですが)、その解答の1つ目の解法と同じらしいのですが「連続しているカードの塊を１要素として考える」ような方法を考えました。
つまり、最初はリストは「1~MのM枚のカードが一塊となっている」ような１要素を持っており、次にシャッフルされると「A~Bの(B-A+1)枚のカードが一塊となっている」と「1~(A-1)の(A-1)枚のカードが一塊となっている」と「B+1~Mの(M-B)枚のカードが一塊となっている」という3要素になる、というのを繰り返して行く。
これだとメモリの消費量は カードの枚数のオーダーではなくシャッフル回数のオーダーとなるので、10^9みたいな大きな数字は扱わず、シャッフル最大数の100の数倍程度の要素しか利用しなくなると。
終わって一言
結局、実装が終わったのは制限時間終わって１時間ほどあとだったんですが。
楽しかったので良いと思います。
ただ、こういった催し物なりコードを書いて誰かと競う、もしくは共同で考えて実装するような機会は高専でやったプロコンや演習以来とんとなくなってしまったので、こういう「良い機会」には自分で探して、自分で向かって行かなきゃならないのかなと思います。
特に自分は、一人でプログラムを書くようなことをしていると、実装方法だとか、設計だとか、規格だとか、セキュリティだとか、他人に使ってもらうためにはとか、そういった部分を全く考えない汚くて効率の悪いプログラムを作る傾向にあるので、そんな現状を打開するためにも色々考えてやって行かないといけないかなと思います。
