2011/10/01にcodejam Japan(プログラミングコンテスト)の予選が開催されました。前回の世界大会やgdd11jpのスライドパズル問題に参加した際に自分の実力不足&伸びしろ不足を実感し、もうこの分野からは手を引こうと考えていたのですが、たまたま時間が有った&合ったのでついヤッちゃいました。で、ヘボい私がどう解いたか考えたかを初歩的にまとめて解説することで、これから競技プログラミングの分野に乗り込んで行こうという人たちの助けになるかもと思いましたので、ちょっと一問だけ書いて見ることにしました。
問題Aの要点
問題Aの要点を引用します。
カードは M 枚からなり、それぞれ 1 から M までの数字が重複しない カードの山を C 回カットすることでシャッフル i 回目のカットではカードの山の上から Ai 番目から Bi 枚、つまり Ai 番目から Ai + Bi - 1 番目のカードがそのままの順番で山の上に移動 (開始状態は)上から順番に 1 から M まで並んだ状態 シャッフル後に上から W 番目にあるカードが何か
一見するとシンプルな問題です。要素がM個の配列を作って実際に並べ換えたあとで指定場所のカードが何かをチェックすれば良さそうに見えます。しかしこの希望は問題のサイズにより脆くも打ち砕かれます。
M はカードの枚数 、C はカットの回数、W は知りたいカードの位置 制約(共通): 1 ≤ C ≤ 100 制約(Small): 1 ≤ M ≤ 100 制約(Large): 1 ≤ M ≤ 10^9
Mは最大で約100億の可能性があるため、実際に配列を並べ替える場合にはテラバイトオーダーのメモリが必要となり、現実的には解けなくなるのです。codejamの問題はだいたいがこの「シンプルだがサイズが大きくて解けない」パターンです。
考え方
まず基本なのですが、この問題で注目すべき&利用すべきは問題サイズによって変化しない「1 ≤ C ≤ 100」のほうです。このCに対してO(C)の時間で答えを求める方法を考えましょう。
そして問題を模式化しましょう。まずはこんな感じです。
- カードを上側から順に3つのグループに分け XYZ と定義する
- Xのカード枚数はx、Yのカード枚数はy、Zのカード枚数はz とする(もちろんx+y+z=Mが成り立つ)
- 前方(左側)を「上側」とする
- Yは1回のカットにより上側に移動させられる
- カット後のカードは YXZ と表記できる
ここでカット後の YXZ のカード状態において上側からW番目にあるカードは、元のカット前の XYZ の並びでは何番目(w)になるかを考えてみましょう。
- 仮に 1 ≤ W ≤ y ならばYにあるので w = W + x となる
- 仮に y + 1 ≤ W ≤ y + x ならばXにあるので w = W - y となる
- (1でも2でもなければ) y + x + 1 ≤ W ≤ y + x + z (=M)となりZにあるので、位置は変わらずに w = W となる
このように1回のカット操作の前の w が W と x, y, z の値から求まってしまいます。ここで少し考えれば、このxは問題文中のAi、yはBiで、zはM - Ai - Biに、それぞれ等しいことがわかります。
一方、開始状態ではW番目のカードの数字はWに等しくなっています。
以上から、カット操作を指定されたのとは逆順に一段ずつWを逆算していくと…最後のWがそのままカードの値になっています。カットの回数は多くとも100回ですから、逆算するのはコンピュータであれば余裕ですよね。あとはコレをコードに書き起こすだけです。
おおよそのコード
Perlでざっくり書くとこんな感じです。$p->{W}にはWが、$p->{AB}にはカット操作が格納されています。あとwは0始まりに補正しています。
my $idx = $p->{W} - 1;
foreach my $data (reverse @{$p->{AB}}) {
my $x = $data->[0] - 1;
my $y = $data->[1];
if ($idx < $y) {
$idx = $idx + $x;
} elsif ($idx < $y + $x) {
$idx = $idx - $y;
}
}
return $idx + 1;
どうでしたでしょうか。一見、大変そうに見える問題も、見かたを変えしっかりと分析することでシンプルにそして小さいサイズで解けるのです。