hotpepsiの練習帳

Google Code Jam 2013 Round 1C

22:35

A. Consonants

問題

• 連続する子音が多いほうが偉い村がある
• 名前が与えられる
• 連続する子音がL以上の部分文字列がいくつあるか答える

方針 (small,large)

• smallのみは時間がもったいないので、O(N)解法だけ書いた
• 準備として、子音の開始位置posと、連続する長さclengthを求めておく
• ただし長さがL未満なら無視する
• 現在位置iについて処理する
• iからはじまる部分文字列がいくつあるか求めて、iを1つずつ進めていく
• iからL文字以上子音が連続しているなら、L文字以上の任意の文字列が該当する
• そうでなければ、iよりあとの子音の位置からL文字以上の地点からはじまる
• 整理すると、着目するpos[x]の終点が、現在位置iから長さLの地点よりあとならば、max(pos[x],i)からL文字から先は全て条件を満たす
• そうでなければ、pos[x]は現在位置には無縁なので、xを進める
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1C_A.cpp

B. Pogo

問題

• NEWSいずれかの方向へジャンプできる
• ジャンプする距離は1ずつ増える
• 座標(X,Y)に到達するためのジャンプ手順を求める

方針 (small)

• メモ化した
• バグっているけど通った
• (書き直したもの)
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1C_B_s.cpp
• 横横縦縦のように交互に移動すると＋1が実現できるので、それでやればよかったらしい。頭いいな...

方針 (large)

• autumn festで類題が出題されていたらしい
• http://www.slideshare.net/tomerun/together-14867665
• 1～tまでの合計と偶奇が必要条件らしいことは理解
• 書いてみた
• https://github.com/firewood/topcoder/blob/master/gcj_2013/R1C_B_l.cpp

結果

A small+large, B small = 38pt 1181th/4467

round1で戦いが終わってしまった。

Aについてはwrong answerを2回出してしまい、それだったらsmallのみ解法で提出しつつ、それをlargeのテスターに使うようにすればよかった。

Bはメモ化テーブルの作り方を間違って1回wrong answerになった。バグっぽい解を提出した。

出来は去年と大差ないけど、復習の速度はだいぶ速くなっているので、全体的には前より解けるようになっているんじゃないかなという気はする。

来年はもう少し予習して臨みたい。