2012年5月1日火曜日

GCJ2012 Qualification Round Problem C. 解き方

Google Code Jam 2012 Qualification Round
Problem C. Recycled Numbers 解き方

コンテストで提出したコードは ここ からダウンロードできます(Python)。
あと このへん。移動してたら探してください。
問題紹介はこちら

以下ネタバレ

純粋に AB の間の全ての n について、数字の並びを移動した数 m を作り、その m が条件に合致するかを調べていくだけです。(n < m ≤ B

コンテスト中に作ったプログラムは n を一旦文字列化して並びの移動をして数値化して条件比較する、、というものでした。これは無駄にコスト(時間)がかかってしまうので、並びの移動をする前に
m の最初の文字(最上位の数字)が n の最初の文字(最上位の数字)より小さくないか
m の最初の文字(最上位の数字)が B の最初の文字(最上位の数字)より大きくないか
をチェックして条件を外れる場合は検証しないことで高速化していました。(これでLargeも8分以内で解けていました)

改修したプログラムでは数値のまま m を作ります。
n = 1234 の場合、
10 で割った商(123)と余り(4) → 123 + 4×1000 → m = 4123
100 で割った商(12)と余り(34) → 12 + 34×100 → m = 3412

1000 で割った商(1)と余り(234) → 1 + 234×10 → m = 2341
です。
桁数 digits を求めておき、1 ≤ k < digits な k について
m = (n / pow(10, k)) + (n % pow(10, k)) * pow(10, digits - k)
という具合です。(pow(a, b) は aのb乗)

注意しないといけないのは、稀に同じ組み合せのペア (nm) ができてしまうことがあります。
Sample にある A=1111, B=2222 の場合も、(1212, 2121) ペアは
= 1212 → “1”+“212” → “212”+“1” → m = 2121
= 1212 → “121”+“2” → “2”+“121” → m = 2121
という2パターンが同じ組み合せで表現されます。
問題はあくまで (nm) ペアの数を答えるものなので、見つけたペアを保存しておいて重複をカウントしないようにしないといけません。


0 件のコメント:

コメントを投稿