GCJに参加しているなう

PC 雑多

GCJ = Google Code Jam。Googleがやってるプログラミングコンテスト。
アカウントはちょこちょこいろんなプログラミングコンテストに登録しているのだが、まともにやったのは今回が始めて。
Qualification roundとRound 1aが終わって、とりあえずRound 2には出られるらしいことが決まった（id: chiguri）。
今のところの問題を少し見直す。
今回はQualification roundについて。
問題はA,B,C,Dの四つだが、Dは解けなかった。

A

Googlereseとかいう謎の言語がGoogleで使われている・・・のかな？（問題文をあんまりまともに読んでない）
簡単に言うと、英文を単純にアルファベット置き換えした言語。
置き換えは1to1、変換逆変換が常に可能。
問題はGooglereseの文章を元の文章に戻せ、というもの。
で、このGooglereseとかいう言語の文字変換表は常に同じらしいのだが、「常に」のさす範囲がいまいちぴんとこなくて悩んでた。
何せ、「与えられる文章は正しい英語ではないかもしれない」とか書かれてるから。
復元する方法ないじゃん！！*1


いや、実はこの問題、Sampleがあり、すべての問題で同じ変換表を使うので、このSampleから表を作ればいいだけなのだ。
で、作ってみたらGooglereseのzに相当する文字だけSampleになかったので、それを探すプログラムを書いて変換表完成。
あとはinputを逐次変換して出力して終了。
さすが予選の予選の最初の問題、簡単だ。

B

Google社員はダンスコンテストがあるのか・・・？
3人の採点者が出場者を0点から10点までで採点するのだが、傾向が似てるから3人の評価は大きくても2点までしか開かない。
最終的な採点結果は3人のうち一番よかった点数。
なお、3人の評価が2点開いたら、それをsurprising scoreと呼ぶ。


で、問題は基準点、出場者全員の3人の評価の合計値、出場者の中でsurprising scoreである人数が与えられて、基準点以上になる人数は最大何人かを出す。
なんで合計値だけ出されるのか、とか気になるけれど、まあよしとしよう。


難しく考えると出場者の採点結果を復元するように探索しないといけないが、もう少し考えると「surprising scoreをとらなくても基準点を超える人」「surprising scoreじゃないと基準点にならない人」「どうしようが無駄な人」の三種類に分けられることがわかる。
合計が3点じゃどんながんばっても基準点3にはとどかない。surprising scoreで0 1 2、そうでなければ1 1 1しかないから。
まあ、こんな風に分類すれば、あとは最初の人たちと、真ん中の人たちのうちsurprising scoreにできる人たちの人数を加えればいい。
後者はmin(真ん中の人数, surprising scoreの人数)なので別に難しくもなんともない。


なお、この問題のSampleにはscoreが0になる例があって、これが適当にやってると間違う部分だったりする。
こんな例出すんだなあ、親切だなあ、と思ってしまった。

C

なんかテレビを使いまわしてるのを見るとむかつくよね？というよくわからない話から始まる問題。
ちなみに問題とその序文はほとんど関係ない。


数字をある桁で二つに分けて、その前後を入れ替えることでできる数字と元の数字をrecycled pairという。
与えられた値A,Bに対してA≦n＜m≦Bとなる(n,m)のうちrecycled pairとなる組の数を出せ、という問題。


で、まあいろいろあるのだが、nとmを全列挙して、nとmがrecycled pairになるかを調べてもいいのだが（smallならそれで通る）、もっと単純に、nを元にmとなる候補を作ればいい。
具体的には、nを桁でrotateしてnより大きくB以下となる値を列挙していけばいい。
多少rotateが遅くてもlargeがこれで余裕。


このとき注意するのは、rotateが周期的になる場合。
特に1212を桁の数だけrotateすると、2121,1212,2121となる。
対応は簡単。周期的なので「自分と同じ値になるまでrotateしてその回数を数える」ので十分。
同じ値が何回でるとか考えなくてもこれで通る。
ちなみに、上の例もSampleに出てくる。
やっぱり親切。


とりあえずQualification roundはこんなもの。
Dは他人のコードを読んで解法を知ったが、解説しづらいので今回はやめておこう。

*1:正しい英語なら、出現頻度などからEの文字を復元したりできるのだが、それにしたってちょっと難しすぎるだろう。