国内予選総評

2008 年度の国内予選は７月４日にインターネット上で行われ、およそ２５０チームが参加しました。試合時間は３時間。予選突破するためには、３問を素早く正解するか４問を解く必要がありました。例年３問解けばまずアジア地区予選に進出できていたことからすると、やや問題が例年より易しかったにせよ、選手のレベルが上昇しています。また、全問正解が３チームあり、上位層のレベルもあがっています。

以下、各問題を解説していきます。それぞれの問題に対して、難易度／目標時間／必要能力（実装力・数学力・知識）を示した後、問題の概要、そして問題の解説を行っています。

難易度は ☆ の数（最高５つ）で表しています。★は☆半分を表しています。

• ☆の問題は、これを解けないようではもっと基礎的な部分を練習する必要があるような問題を表しています。
• ☆☆の問題はアジア地区予選に出場するためには絶対に解かなければならない問題です。
• ☆☆☆の問題がすべて解ければアジア地区予選に大学トップであればまず出場可能であるレベルを表しています。
• ☆☆☆☆の問題は、上位を狙うならばぜひ解いてほしい問題です。
• ☆☆☆☆☆は、まず時間内には解けない問題を表しています。

問題を解く目標時間は、問題を読み始めてからどれぐらいの時間で正解を出してほしいかと表しています。この目標時間は３段階に分けており、上位チーム／中位チーム／下位チーム向けの目標時間を記述しています。

問題を解く必要能力は、実装／数学／知識／応用の４つに分けて示しています。実装は実装のタフさを、数学は数学的知識を、知識はアルゴリズムの知識を、応用は必要とされるひらめきの力や基本的なアルゴリズムを適用することの難しさなどを表しています。

問題概要は、問題の概要を簡単にまとめて記述しています。

それでは、各問題の解説に入ります。おおよそ易しい問題ほど丁寧に解説してあり、問題に取り組む人のレベルに沿って解説してあるつもりです。

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

問題Ａ Equal Total Scores

• 難易：☆（大変易しい）
• 目標：７分／１０分／１５分
• 能力：実装１／数学１／知識１／応用１
• 概要：太郎と花子に手札がそれぞれ n, m 枚与えられる。手札には点数がついており、太郎と花子の手札を一枚ずつ交換して二人の点数を等しくしたい。どの手札を交換すればよいか？　複数の交換方法がある場合、交換した手札の合計点が少なくなるものを選べ。

例年問題 A は非常に易しい問題が出題されます。これが一瞬で解けないようでは国内予選通過はままなりません。おおよその傾向ですが、問題 A は問題文に書いてあることをそのまま実装すれば良いようになっています。もし、問題 A が解けないようであれば、まず「どのようにすれば二人の手札の合計点を等しくなるようにできるか」を日本語で書き下してみることから始めましょう。

今回の場合、次のようになります。

1. 太郎と花子の手札を読み込む
2. それぞれの合計点を出す
3. 太郎から手札を一枚、花子から手札を一枚選んで交換する
4. 交換したときの太郎と花子の合計点を求める
5. 等しければ解の候補。今まで解が出てなければそれを解とし、解が出ていれば交換した手札の合計が前に出た解よりか小さいかを確認し、小さければ解とする
6. 選ぶ手札がなくなるまで 3 に戻って繰り返し
7. 解が見つかれば解を表示。なければ -1 を表示。

まずこの作業をせずにプログラムを書こうとすると、問題 A が解けない様な初心者のうちは何を書いているのかわからなくなるでしょう。 問題 A がすらすらと解ける様になるまでは、まずこの作業をしてからそれをプログラムに直すようにしましょう。

では、これをプログラムに直していきます。ここでは STL を用いた C++ のコードを使って例示します。

まず、問題を読んでいる間に、手の空いた人がテンプレートコードを打ち込みます。

テンプレートを打ち込んで問題を理解したら実装の開始です。ICPC では入力／計算／出力がきれいに分かれることが多いので、私はいつも main 内で入力／出力を行い、計算部分は solve という名前の関数を作ってそこで計算を行っていました。ここでもそのように実装していきます。

太郎と花子の手札を読み込む

まず１行目に太郎と花子の手札の数 n, mが来ますので、それを読み込みます。

次に、太郎の手札が n 枚、花子の手札が m 枚来ますのでそれを読み込みます。読み込んだ手札を覚えておくために、配列、もしくは vector を用意します。

C++ であれば、特に速度を必要としない限りは vector を使った方が楽でしょう。（ただし、計算時間が厳しいと思ったときは普通の配列の方が速いことが多いので、普通の配列を使った方が良いでしょう。）

それぞれの合計点を出す

読み込んだ手札から、合計点を求めます。これは全ての手札の点数を足すだけなので簡単ですね。

もちろん、読み込むときに一緒に足してもかまいません。

太郎から手札を一枚、花子から手札を一枚選んで交換する

おそらく、初心者のうちはこういうところでつまるのではないかと思います。太郎の手札と花子の手札を全て列挙するには、二重ループを使う必要が有ります。

これで、太郎の手札 tarou[i] と、花子の手札 hanako[j] が選ばれました。

交換したときの太郎と花子の合計点を求める

これはどうすれば良いでしょう？　太郎はもともと tarou_sum 点の手札を持っており、花子に tarou[i] をあげ、花子から hanako[j] をもらいました。従って、このときの太郎の点数は、tarou_sum - tarou[i] + hanako[j] です。花子も同様に hanako_sum - hanako[j] + tarou[i] です。

添字を間違わないように注意してください。

等しければ解の候補。今まで解が出てなければそれを解とし、解が出ていれば交換した手札の合計が前に出た解よりか小さいかを確認し、小さければ解とする

等しいかどうかをまずチェック。

等しくない場合は、さっさと次にいきましょう。

等しい場合、今まで解が出ていたか、解が出ていたならば前に出た解より交換した手札の合計が低いかどうかを調べる必要が有ります。おっと、ここで解を覚えるための変数を用意してないことに気がつきました。ループの前に次を追加します。

選ぶ手札がなくなるまで 3 に戻って繰り返し

これは３のループでもう書かれています。

解が見つかれば解を表示。なければ -1 を表示。

解があるかどうかは found に bool 値として入れておいたので、それをみれば良いはずです。

さて、これではデータセット１つに対してしか解答していませんので、while でデータの終了が来るまでまわします。

これでプログラムは終わりです。これをコンパイルして実行してみましょう。コマンドラインが使える人は

の様に、サンプルインプットを in.a として保存してそれを与えましょう。eclipse などの統合環境を使っている人は各自のやりかたでコンパイルしてください。Java などは eclipse であれば補完が効きますから、eclipse で記述するのをお勧めしますが、コンパイル + 実行はコマンドラインの方が速いと思います。

プログラムを書いたら、必ずサンプルインプットを与えてただしい出力がなされているかを確認してください。

慣れるまで、何度も同じ問題を解いてみてください。答えを覚えてしまってもかまいません。むしろ、覚えるぐらいまで解いてしまった方が良いでしょう。はじめのうちは、そのようにした方が早く実力がつくと思います。

問題 B: Monday-Saturday Prime Factors

• 難易：☆★（易しい）
• 目標：１０分／１５分／３０分
• 能力：実装２／数学２／知識２／応用２
• 概要：７で割って 1 または 6 あまる自然数を考える。これを月曜土曜数と呼ぶ。１以外の月曜土曜数が、ほかの月曜土曜数で割れないとき、月曜土曜素数と呼ぶ。月曜土曜数が与えられたとき、それを割ることが出来る月曜土曜素数を全て出力しなさい。

問題 A よりは少し手強くなっています。なんとなく数学が絡んできて一瞬嫌な感じの問題に見えるかもしれませんが難しいものでは有りません。なんとなく難しそうな問題も、「簡単な小さな問題に分けて考える」と理解しやすくなり、またプログラムを書く上でも楽になります。簡単な問題に分ける場合、「どうやって作るかまだわからないけど、これがあったら後の計算が楽になる」というものを考えてみるのが得策です。この場合、もし「月曜土曜素数表が与えられていたら」どうするか？　素数を一つずつ試していって、与えられた数を割ることが出来るかどうかをチェックし、それを出力するだけですよね？　つまり、もし月曜土曜素数表が小さい順に

で与えられていたら、与えられた数 n に対して、

とやれば OK です。ということは、msprimes をどうやって作るかをうんうんうなって考えだせば良い訳です。

素数を求めるアルゴリズムといえば、エラトステネスのふるいが定石です。今回も、適用の仕方が少し違うだけで、同様に記述することが出来ます。今回の場合、「月曜土曜数 a が月曜土曜数 b の月曜土曜約数であるためには、a が b の普通の意味の約数であれば必要十分であると， 簡単に証明できる」という一文が問題文のなかにあり、これは結局 b をa で普通に割ってみて、割りきれたら a は b の月曜土曜約数である、ということを言っており、よけいなことを考えなくてもよくなっています。従って、月曜土曜素数版のエラトステネスのふるいは、次のように書けます。

基本的に殆ど一緒で、月曜土曜数のみを扱うようになっています。少し無駄な処理がありますが、特に問題ない量なので、本番ではこのようにある程度書きやすさを優先させても良いと思います。

問題 C: How can I satisfy thee? Let me count the ways…

• 難易：☆☆（やや易しい）
• 目標：１７分／３０分／６０分
• 能力：実装３／数学１／知識２／応用２
• 概要：真・偽・不明の３つの値を変数が取る。論理式が与えられたとき、その論理式の値が真になるような、変数の値の取り方の総数を求めよ。ただし、変数は P, Q, R しかない。

どちらかというと構文解析の問題。構文解析は ICPC アジア予選レベルでは頻出ですが、国内予選でもついに出てきました。ICPC で出てくる構文解析は難しいものではなく、再帰がちゃんと書ければ出来ます。アジア予選レベルではちょっと考えないとかけない問題も出ますが、今回の問題は素直に実装出来ます。

今回の問題は、P, Q, R が 0, 1, 2 のどれかしかとりません。構文解析の問題は、構文解析して構文木を作ってから変数に値を入れて実際に評価した方が良い場合と、構文解析と式の評価を同時にした方が良い場合があります。変数に入れる値の範囲が広い場合は前者の方が良いでしょうが、今回は最大 3 * 3 * 3 = 27 通りしかないので、P, Q, R をそれぞれの値で初期化してから構文解析と評価を同時に行った方が楽に記述出来ると思います。

さて、構文解析ですが、これは再帰に慣れた人なら楽に記述出来ますが慣れていないと難しいでしょう。慣れてない人は再帰についてこの機会になれることを勧めます。再帰は「信念」さえあれば書けます。それでは、再帰を書くための信念を身につけましょう。

を、pos から始まる構文を解析して評価した値を返し、pos を構文の最後まで進める関数である、と思ってください。eval は、どう実装されているかわからないけど、とにかく今はそんな関数なのです。そう「信じてください」。つまり、eval は、式が

だったら、pos が 0 のときは全てを構文解析評価して２を返して pos を 9 にし (すべての式を評価して pos を最後まで進める)、pos が 1 だったら、そこから始まる構文である (2*2) だけを解析して 2 を返して pos を 6 にする (+の位置まで pos を進める)、そんな関数であると「信じてください」。再帰はこの信じる心が重要です。そして、この「信じた関数を使ってない部分は信じた関数と同じ動きをする」ように記述していけば再帰はかけてしまうのです。

さて、そう信じたら、まず「再帰が必要ないところから」書き始めます。eval といういまよくわからない関数を使わなくても簡単に書けるところからスタートします。今回の文法を見ると、0, 1, 2 が来たら値はそのまま 0, 1, 2 を返します。これだったら書けますよね？　信じた関数と同じになるように、pos は読み込んだ後まですすめ、値をちゃんと返すようにします。

とりあえず、これだけで済みます。これを eval の最初の方に書いておきます。

あと文法を見ると、マイナス、かけ算、足し算が残っています。マイナスは expr が１回しか出てないのでこれから始めましょう。マイナスは、最初がマイナスで、そのあと expr がくると書いてあります。なので、まず最初が - であるかどうか調べます。

マイナスの符号を読んだら、pos を進めておくのを忘れないように。さて、次は expr ですが、ここで魔法を登場させます。eval は、初めに「信じたように」pos から始まる構文を解析して、値を返し、pos を構文の終わりまで持っていってくれる関数なのです。それを信じて使います。つまり、expr の構文解析と評価は eval がやってくれるのであとはそれに任せてしまうのです。マイナスは、0 なら 2 を、1 なら 1 を、2 なら 0 を返すので、eval を読んで得られた値を 2 からひけば良いでしょう。

これでマイナス部分が書けました。同様に + と * についても expr が出来たら同じように信じた eval を使って記述します。+, * に関しては、よく見ると a + b の値は a, b の大きい方、a * b は (a * b + 1) / 2 で書けてしまうのでそれを使っています。もしこの規則がわからなかった場合は、一つずつ (0 + 0) は 0, (0 + 1) は 1, というように全ての場合を記述してください。

これで与えられた式が全て記述出来ました。実はこれで最初信じた eval が出来上がっています。実際に動かしてみましょう。

このように、再帰は最初に「関数が何をするのかを決めて」、再帰を書いている間はずっと「その関数は決めたことをしているものだ」と信じ、「それを使って条件一つずつを書いていく」ようにすればよいのです。

しばらくは練習が必要ですが、再帰を上手に書ける様になるととたんにプログラミングが上達します。しばらく練習しましょう。

問題 D: Twirling Robot

• 難易：☆☆☆（標準）
• 目標：３０分／５０分／１２０分
• 能力：実装３／数学１／知識３／応用３
• 概要：ロボットをスタートからゴールまで動かすときの最小のコストを求めよ。コストはロボットに与える命令で決定される。途中の道には標準の命令が書いてありこれはコスト０である。これを上書きするとき、命令に応じたコストがかかる。

ゴールまで行く最短コストを求める問題。いくつか解く方法はありますが、ここは素直にダイクストラのアルゴリズムを用いて解きたいところ。ダイクストラのアルゴリズムは、プログラムを書く人にとって「絶対に知っておかなければならない」知識の一つです。なるべく早く身に付けましょう。

ダイクストラのアルゴリズムとは、負のコストがないグラフが与えられたときに指定された開始点から各点までの最短路およびそのコストを求めるアルゴリズムで、ICPC では非常に良く使うアルゴリズムです。易しい問題ではダイクストラのアルゴリズムをそのまま適用すれば答えが出るものもありますが、グラフの作り方を少しひねらせる問題もよく出ます。グラフの頂点がいくつかの状態を取る場合に頂点を分割してその状態全てを頂点とみなすようなグラフを作ってからダイクストラのアルゴリズムを使う、という出題形式が多いように思われます。

今回の問題の場合、上下左右のどちらを向いているかで頂点を４つに分割したグラフ（これをもとのグラフを拡大したという意味で拡大グラフという）を作って、ダイクストラのアルゴリズムを使えば良いでしょう。ロボットへの命令を枝とし、そのコストは標準の命令であれば０、そうでなければ、命令に応じたコストを枝のコストとします。

問題Ｅ Roll-A-Big-Ball

• 難易： ☆☆☆★（やや難しい）
• 目標：４５分／９０分／解けなくてよい
• 能力：実装２／数学３／知識４／応用３
• 概要：グラウンドに引かれたコース（直線）に沿って大玉を転がす。障害物にあたらないような大玉の最大の大きさを求めよ。

幾何問題は例年１題は出題されますが、幾何問題は「ライブラリがものを言う」問題です。幾何のライブラリは豊富に用意しておきましょう。今回は線分と線分の距離を求めることさえ出来れば容易に解ける問題です。

今回の問題の場合、障害物の壁部分を線分として、スタートからゴールまで行く線分との距離を求めます。壁の高さ h とその距離 d に対して、最大の玉の大きさを求め、その最小値が答えとなります。最大の玉の大きさは次の様のして求められます。

d < h の場合：　かべまでの距離が最大の玉の大きさなので d。

d >= h の場合、図を書いて方程式をたててしらべます。 三平方の定理より r2 = (r - h)2 + d2 従って、r = (h2 + d2) / 2h

なお、最初に既に障害物の中にした場合は、場合分けして答えを 0 とします。

問題は距離 d をどうやって求めるか、ですが、点と線分の距離のライブラリを持っていれば、線分と線分の距離は、両端の点ともう一つの線分の距離を求め、反対側も同じことをすれば OK というのはすぐにわかるでしょう。線分同士が交差している場合は別に判定し、距離を 0 としておきます。

最後に、許容誤差が指定されているので注意して出力します。

問題 F. ICPC: Intelligent Congruent Partition of Chocolate

• 難易： ☆☆☆☆（やや難しい）
• 目標：８０分／解けなくてよい／解けなくてよい
• 能力：実装４／数学２／知識３／応用４
• 概要：正方形のチョコレートをつなげてできた板チョコレートを合同に２つに分けられるかどうか答えよ。ただし分けられたチョコレートは連結でなければならず、また正方形チョコレートを２つにわってはならない。

やや難しいが解ける問題。東大予選を戦うのでもない限り国内予選では解かなくても良いでしょうが、アジア予選では解いておきたい程度の問題です。この問題は基本的には２つにチョコレートを分けて合同判定を行う全探索を書けば OK です。チョコレートを分けるときは、切り取り線を入れるようにして切り取り線が交差しないように分けると、切り取られた２つのピースは連結になっています。あるいは、一つ端の正方形チョコレートを決めてそれを含むように一方のチョコレートを決めて、それと他方のチョコレートを比較するという方法でも大丈夫でしょう。

そうしてチョコレートが２つに分けられたら、あとは一方のチョコレートを反転したり回転したりして８通り生成し、比較します。

ソースコード

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

• ２００８年度国内予選解答例