2007 年アジア地区予選日本大会総評

2007 年は試合時間５時間で、出題された問題セットは簡単な問題から難しい問題までバランスがよく取れたセットであり、実力が十分に反映されるセットでした。このとき京大の echizen がこのセットを９問解き、海外からの強豪もはねのけて見事優勝しました。このセットで９問解かれるととしか言いようがないですね。

問題セットは、公式サイトから入手できます。

Problem A: And Then There Was One

• 難易： ☆（易しい）
• 目標：１５分／２０分／２５分
• 能力：実装２／数学１／知識２／応用１
• 概要：石が n 個円上に並んでおり、時計回りに 1, 2, …, n と名前を付ける。はじめに m 番目の石を取り、次にそこから時計回りに k 個の間隔をあけて石を取っていった場合、最後まで残るのは何番目の石か？

一番易しい肩ならしの為の問題。日本地区予選では問題 A に一番易しい問題が基本的にくるので、さっさと解いて調子にのりたいところです。

ある程度アルゴリズムに詳しい人であれば、これがヨセフス数を求める問題の応用問題であることに気がつくと思いますが、n がそんなに大きくないのでヨセフス数を求めるアルゴリズムを知らなくても実際にシミュレーションして求めることも可能です。

シミュレーションしようと思ったら、まずそれが「可能であるかどうか」を問題の条件から読み取る必要が有ります。本番では実行時間３分の間に解を出さなければなりません。あまりにも時間のかかるアルゴリズムは例えそれが正しい解を出力するものであったとしても不正解扱いされてしまいます。従って、まず時間に間に合うかを考える必要が有ります。

今回の問題の場合、石を vector か list で表し、実際に取り除いていけば良いでしょう。vector で表すと、次の k 番目の石を見つけるのは足し算と剰余演算で O(1) で出来ますが、取り除いたあとでつめる作業が O(n) かかります。list で表すと k 番目の石を見つける作業は O(n) かかりますが (O(k) でないのは実際には k mod n 進めれば十分だから)、取り除く作業は O(1) ですみます。どちらも計算量の観点からするとそんなに差はなさそうです。そういう場合は迷わず vector を選びしょう。その方が概して計算量の定数部分が小さいので高速に動く上、またコードも楽に記述できるからです。

Problem B: Prime Gap

• 難易： ☆（易しい）
• 目標：１５分／２０分／２５分
• 能力：実装２／数学１／知識２／応用１
• 概要：連続した素数 p, p + n の間の合成数の列 p + 1, p + 2, …, p + n - 1 を、長さ n の prime gap と呼ぶとき、与えられた整数 (1299709 以下) を含むような prime gap の長さを出力せよ。

素数の列挙は、2008 年の国内でも出てきましたが、エラトステネスのふるいで OK。

素数が全て小さい順に列挙出来たら、次は与えられた合成数がどの素数の間に入っているかを調べることが出来れば OK です。これには、素数を小さい順に並べて二分探索を使うのが筋というものでしょう。二分探索は、C++ であれば、lower_bound を使うと一発で書けます。

lower_bound は、指定されている要素以上が入っている最初の要素のイテレータを返します。従って、n が合成数であれば *(it - 1) と *it が n を含むような連続する素数になるので、*it - *(it - 1) を返せば OK です。n が素数の場合 *it が n と等しくなるので、それで場合分けします。

Java であれば Arrays.binarySearch を使うと二分探索はやってくれますが、少し使い方に癖があります。要素が配列中に見つからなかった場合は -(insertion point) - 1 を返すので、負かどうか判定し、正に直してから C++ と同様にする必要があります。

この問題の場合は input の種類が少ないので、事前に全部答えを求めておいて出力はその答えを出すだけという方法も取ることが出来ます。

Problem C: Minimal Backgammon

• 難易： ☆☆（やや易しい）
• 目標：３０分／５０分／７０分
• 能力：実装３／数学１／知識２／応用２
• 概要：簡単化されたルールの一人用のすごろく（バックギャモン）がある。このすごろくには、「最初に戻る」と「一回休みのマーク」がある。ゴールにぴったりとまれなければ、行き過ぎた分だけ戻らなければならない。このすごろくを T ステップ以内にクリア出来る確率を求めよ。

いかにも動的計画法（Dynamic Programming, DP）で解いてくださいという問題。動的計画法をわかっていれば易しい問題なのですが、動的計画法を理解していない場合は厳しい問題になります。

動的計画法は、非常におおざっぱに言うと、これまでにわかっている値を用いて次の値が簡単に計算できるときにその値を求め、それを繰り返して所望の値を得る、という手法です。以下、少し易しい例（フィボナッチ数列）で説明します。

フィボナッチ数列 f(n) は、次の式で定義される数列で、定義通りに f(n) を計算すると非常に効率が悪いことでしられる数列です。

定義通りに f(n) を計算すると、同じ f(n) を何度も計算することになってしまい非常に遅くなってしまいます。例えば、f(n - 2) は f(n) と f(n-1) の２つで必要とされ、計２回計算されます。f(n-3) は f(n-1) と f(n-2) で必要とされますが、f(n-2) は２回計算されるので、結局３回計算されます。これがどんどん進んでいくと、結局 f(n) を計算するには f(n) の値と同じ数の計算が必要とされます。f(n) の値はすぐに大きくなり、例えば f(50) は 12586269025 です。これでは計算できません。しかし、f(1), f(2), f(3), … と下から計算していき、その値を全て覚えておけばどうでしょうか。f(3) は f(1) と f(2) を覚えておけばすぐに計算できます。f(3) の値も覚えておけば、f(4) は f(2) と f(3) の値を足せば良いので一回の足し算で計算できます。こうすると、f(50) は結局 48 回の足し算で計算できることになります。このように、わかっている値から、すぐにわかる値を計算して覚え所望の値になるまで繰り返していきます。計算した値は表の形式になっていることが多いので、途中の計算を表を埋めるとも言います。

さて、この問題の場合はどうでしょう。もし、t ステップ目にどのマスにどの確率でいるかがわかれば、t + 1 ステップ目にどのマスにどの確率でいるかはすぐに計算できます。例えば、t ステップ目に k 番目のマスにいる確率をαとしましょう。そこから１の目を出した場合に k + 1 番目のマスがスタートに戻るでなければ、k + 1 番目のマスにいる確率を α / 6 増やすことが出来ます。αを 6 で割っているのは、もちろん１の目が出る確率が 1/6 だからです。同様に、２の目が出る場合、３の目が出る場合…、また今 1 番目のマスにいる場合、2 番目のマスにいる場合、…、を全て計算していけば、t + 1 ステップ目に各マスにいる確率が計算できます。これを T ステップ繰り返し、ゴールにいる確率を求めれば良いのです。ただし、一度ゴールに到着するともうさいころは振らなくて良いので、次のステップでもゴールにいると考えるかゴールに行った確率は考慮せず最後に各ステップでゴールに到着した確率を足し合わせるかしてあげる必要があります。

また、このすごろくには一回休みがあるのでそれも考慮する必要があります。一回休みのマスにとまった場合、次のステップではさいころをふれないので、休んでいるという状態を作る必要があります。すなわち、各マスは「休み中」マスと「休み中でない」マスの２つの状態にわけ、「休み中」マスにいる場合、次のステップでは確率１で「休み中でない」マスに移動するようにします。

つまり、この問題の場合は t ステップ目、k 番目、休み or 非休み の３つの要素からなる３次元の表を埋めていくことになります。

日本大会の場合、動的計画法の問題は易しい問題になっていることが多いのでぜひとも解いておきたいところです。

Problem D: Lowest Pyramid

• 難易： ☆☆☆☆★（難しい）
• 目標：７０分／解けなくてよい／解けなくてよい
• 能力：実装４／数学４／知識３／応用４
• 概要：頂点が全て格子点にある様な三角形が与えられたとき、それを底面にして四面体を作りたい。作った四面体の展開図でも頂点が格子点になるとき、作れる四面体の最小の高さを求めよ。

空間幾何の非常に嫌な問題で、落とし穴がいくつもあります。本番では最後の方まで手を出さないのが無難。最後もしくは最後から２番目に解く問題になるでしょう。

基本的なアルゴリズムとしては、３頂点を全て列挙してそこから作られる四面体の高さを計算し最も低いものを選べば良さそうです。この問題の難しいところは、どうやって３頂点を選ぶか、３頂点が与えられたときにどうやって高さを求めるかの２点。どちらもある程度難しく、非常にハマりやすい問題になっています。

まずは３頂点をすべて列挙していくところから始めましょう。全部列挙しようとすると、各頂点の x, y 座標は [-100, 100] の範囲の整数を取るのでおよそ 2002 = 40000 通り考えられ、それが３つあるので 400003 通りあります。これはさすがに多すぎて計算できないので、別の方法を考える必要があります。次の図を見てください。

３頂点と三角形は四面体を作らなければならないという制約から、長さが等しい辺が３カ所あります。よって、一つ頂点 Pa を適当に決めると、頂点 Pb は長さ PaP2 と PbP2 が等しくなるようにとらなければならないので、多くても４００点ぐらい（P2 を中心にした半径 PaP2 の円上しか Pb はくることが出来ない）で、また Pc に至っては Pa と Pb が決まれば、長さ PaP1 とPcP2 が等しいこと、PcP3 と PbP3 が等しいことから１点に決まります。これで３頂点の位置がかなり絞られ、全列挙することが可能になります。また、各頂点が存在することが出来る領域もある程度制限されています。頂点 Pa であれば、P1 と P2 を通る直線の、三角形が存在しない方でなければなりません。これは、P1P2 と P1Pa のなす角が0度超180 度未満である必要があります。もちろん実際になす角を求めても良いのですが、この場合（０度から１８０度の範囲にあるかどうか調べる場合）は外積を使うのが定石。ベクトル a = (xa, ya), b = (ya, yb) の外積はなす角をθとすると |a||b| sin θ でθが０度から１８０度にあるということは sin θ が正ということですが、外積の値は xayb - xbya でも求められるので、この値が正であるかどうかを調べれば OK です。

さて、３頂点を列挙するのも一苦労でしたが、次は四面体の高さを求めなければなりません。Pa, Pb, Pc がどこで四面体のもう一つの頂点を作るかが分かれば良いですが、それはどうやって求めれば良いのでしょうか。

それには、まず Pa がどこを動くことが出来るかを考えましょう。三角形 PaP1P2 は、P1P2 は固定されているので P1P2 を軸として回転することが出来ます。従って、Pa が動く平面は、Pa から P1P2 に垂ろした垂線を含んで三角形 P1P2P3 に垂直な平面の上を動きます。Pb, Pc も同様です。従って、Pa, Pb から三角形 P1P2P3 に垂線を垂ろし、その垂線を延長した直線が交わる点が四面体の最後の頂点が乗っている場所になります。

あとはこれの高さを求めるだけですがこれは P1P4 の（３次元上の）長さが P1Pc に等しいことを使うと、P4 の x, y 座標は直線の交差で求まっているので z 座標もすぐに三平方の定理ですぐに求めることが出来ます。

Problem E: Geometric Map

• 難易： ☆☆☆☆（やや難しい）
• 目標：７０分／１００分／解けなくてよい
• 能力：実装５／数学３／知識３／応用２
• 概要：グラフが与えられたとき、ある点からある点までの最短経路を求めよ。ただしグラフは２次元平面上に与えられ、枝の制約（通行可能・不可能）をひとつの端点でしかほかの線分と交わってないような線分で与え、その線分のなす角によって通行可能・不可能が決められる。

グラフをきちんと構築することさえ出来れば、ダイクストラ一発で容易いのですが、本問の難しさはグラフの与えられ方にあります。

線分で図が与えられ、結合してないような線分が「標識」を表し一方通行や通行止めを決めています。標識でない線分はかならずどちらかの端点がほかの線と接していないので、与えられた線分が標識であるか道であるかで分け、道だけを使ってグラフを構築。そして標識を処理し、一方通行・通行止めを処理していくようにするのが良いでしょう。

実装してしまえば解ける問題なのですが、実装が大変なため、後回しにして解きたいところ。端末を使ってない人が、時間があるときに机上である程度コーディングしておくのが良いでしょう。求められるアルゴリズムはダイクストラぐらいですが、忍耐強く幾何の問題を処理してコーディングしていく足腰の強さが必要な問題です。

ただ、実装してしまえば解ける問題なので、解く問題がなくなったら手を出した方が良いでしょう。

Problem F: Slim Span

• 難易： ☆☆（易しい）
• 目標：３０分／５０分／８０分
• 能力：実装２／数学２／知識３／応用３
• 概要：与えられたグラフの全域木 (spanning tree) のなかで、枝の最小コストと最大コストの差が最も小さくなるような全域木の枝の最大コストと最小コストの差を求めよ。

前２問とはうって変わって易しい問題。アルゴリズムを組み立てることが出来れば、実装は易しい。アルゴリズムもそう難しいものではないので、本番では最初の方に解いておきたい問題になります。

おおまかなアルゴリズムの方針は、まず枝をコストでソートし、使ってよい枝のコストの下限を決めて、そのコスト以上の枝を順番に全域木が出来るまで追加していき、全域木が出来たら最大のコストの枝のコストと最小のコストの枝のコストの差を計算します。あとは、下限を上げながら試していき、コストの差が最小になるものを選べば OK です。

全域木の判定ですが、簡単なのは union-find を使う方法でしょう。union-find を使うときに、グループがいくつあるかを数えておくと、グループが残り１つになるまで枝を追加していけば良いので、全域木になったことが非常に簡単に分かります。

Problem G: The Morning after Halloween

• 難易： ☆☆☆（標準）
• 目標：４５分／９０分／１２０分
• 能力：実装３／数学１／知識３／応用３
• 概要：あるマップの中に幽霊が最大で３体いる。この幽霊を初期位置から決められた場所に移すのにかかる最小のステップ数を計算せよ。ただし、幽霊はお互いに場所を入れ替えることは出来ない。

一瞬どうしたら良いのか途方に暮れる問題です。探索したくなる問題ですが、幽霊は同じ状態に戻ってくることが有ります。そのチェックをすれば良さそうですが、いったいそれがどれぐらいになるかが問題になります。

状態数を計算してみましょう。マスが 16 × 16 しかないこと、および幽霊が３体しかいないことを使うと、幽霊の位置の取りうる状態は (16 × 16)3 つまりおよそ１００万個しかありません。この程度なら、状態を全て覚えておくことが出来ます。幅優先探索を用いて、各状態に到達可能な最低ステップ数をキャッシュしておけば、OK です。後は幽霊が同じ場所にこないこと、交差しないことをちゃんとチェックさえすれば OK。

それほど難しい問題ではないので、きっちりと解いておきたい問題です。

Problem H: Bug Hunt

• 難易： ☆☆☆（標準）
• 目標：４５分／９０分／１２０分
• 能力：実装３／数学１／知識２／応用２
• 概要：配列の操作を行うプログラムが与えられる。未定義の配列を扱ったり、初期化していない要素を参照するなどのバグを発見し、それがおこった行数を返しなさい。

どちらかというと構文解析の問題。一度でもなにかのインタープリターを作ったことがある人であれば実装はそんなに難しくはないでしょう。構文解析した後は、実際に実行してみてバグを見つけたら処理していく、という方針になります。

構文解析ですが、2008 年の国内予選Cでやったのと同じような方針で構文解析していくことが可能です。

まず各行に対してどういうプログラムであるかを構文解析していきます。各行は一つの式であるとみると、次の構造体 Expr で表現できます。

Type は型を表しており、ASSIGN は代入、VALUE は即値、EXPR は式を表しています。今回は、配列の宣言は EXPR で代用します。代入の場合は式 e1 に式 e2 の値を代入する、即値は val の値、式の場合は配列名が ident で添字が e1 の値、と定義し、それをそれぞれ ASSIGN(e1, e2), VALUE(val), EXPR(ident, e1) で表すことにすると、次の式

は、右辺は 2 だから VALUE(2)、左辺は EXPR(a, EXPR(b, VALUE(1))) で表せます。従って全体は

で表すことが出来ます。この様に式を作っていき、あとはその式の評価をしていけば OK です。

次に評価です。まず配列は map<int, int> と要素数で次のように表現。

間違っても elems を vector で表現してはいけません。配列の大きさは、非常に大きい値がくる可能性があるからです。sample input をみると 2147483647 の要素を持つ配列が宣言されており、明らかに vector で表現することは不可能だと分かります。次に配列名と配列を結びつける「環境」を map<string, Array> で表現します。あとは、配列を見るたびに環境に配列が定義されているか、配列が定義されていれば要素が定義されているか、size を超えていないかをチェックしていきます。チェックに失敗したら、その行数を返すようにします。

Problem I: Most Distant Point from the Sea

• 難易： ☆☆☆★（標準〜やや難しい）
• 目標：６０分／９０分／解けなくてよい
• 能力：実装４／数学３／知識３／応用３
• 概要：凸多角形の陸が与えられたとき、その陸の中の点で、最も海から遠い距離を求めよ。

やや面倒な幾何の問題です。面倒くさい問題なので、後半の方に解くことになるでしょう。

方針としては、適当に中の点を選んで、陸から遠ざかるように動かす方法や、距離を決めて陸をせばめて、陸がまだあるかどうかで二分探索するという方法がまず考えられます。

前者の場合、動かしていった先が最小でない極小点に陥ってしまわないか注意が必要ですが、問題で凸多角形がくることが保証されているので、極小点であれば最小点であることが保証されています。

後者の場合、陸を構成する線分をのばした直線を考え、これの左手側だけを残したものが陸を構成していると考えます（多角形の頂点は反時計回りに与えられると書かれている）。全ての直線を左に d だけ動かし、陸がまだ構成されているかどうかをチェック。最初の凸多角形を、動かした直線でカットしていき、陸が残っているかどうかを判定してすればチェックできます。

Problem J: The Teacher’s Side of Math

• 難易： ☆☆☆☆（やや難しい）
• 目標：６０分／１１０分／解けなくてよい
• 能力：実装３／数学５／知識４／応用５
• 概要：m√a + n√b がが与えられたとき、これを解にもつ方程式で、次数が最も低く、整数係数であるものを求めよ。但し、a, b は素数で、また互いに素である。

数学の問題です。数学的な洞察が出来ればプログラムを書くことはそれほど難しくないのですが、本番でどうやって解くかを考えるのはちょっと厳しいかもしれません。

こういう問題は、簡単な input で少し実験してみるのが良いでしょう。例えば、√2 + √3 を解に持つような方程式を自分で作ってみると、なにか見えてくるかもしれません。やってみましょう。とりあえず、

とおいてみます。根号を少しでも消すために二乗します。

さらに √2√3 を消すためにまた二乗します。

ここで、√2√3 は t2 と t4 で出てきたので消去できます。

さてこのあたりで、何乗かしたときに出てくる根号をもつ項は √2, √3, √2√3 だけであることに気がついたでしょう。

を考えたとき、t, t2, t3, … を求めたときに出てくる項は係数をのぞいて

の mn - 1個。従って、t, t2, …tmn を上の根号で表した mn 個の式があればこれらの根号を全て消し、t だけの式を得ることができます。これらの根号が変数だと思って連立方程式を作り、ガウスの消去法を使えば OK です。

しかし、 tmn まであれば十分であることは分かるのですが、これだけではまだ最低次数かどうかは分かりません。従って、ガウスの消去法を行うときに、ピボットの交換をする必要があればなるべく t が小さい次数のものと交換して掃き出していくようにし、tmn まで行かずとも途中で全て根号が消去できてしまえばそれを返すようにすると安全です。ただ、実際は本当に tmn まで必要（証明は略）なので、tmn まで必要であるという自信があれば、途中で返すようなコードは書かなくても大丈夫です。

消去法を使うときにこのとき注意しないといけないのが、オーバーフローです。なるべく係数が整数のままでいようとすると係数がオーバーフローする可能性が高くなります。簡単に試してみたところ、long long を使ってもオーバーフローしてしまいました（もしかしたらオーバーフローしないように出来るかもしれないが未確認）。double を使っても出来るかもしれませんが、Java の BigInteger を利用するのも安全でしょう。

解答例

解答例を配布しています。解答は、公式の output と合わせています。

• 2007 年度アジア予選日本大会解答例