最近、暇があれば(なくても時間を無理やり搾り出して)プログラムを書いてるので、ブログの更新はあまりやっていない。というのは寂しいと言われそうなので、プログラムの正解にヒントなるものを適当に書いておく。

online-judge.uva.es での順位は現時点315位だが、4月までに100位以内に食い込むのは当面の目標。1位になることは不可能かもしれないが、できれば今年中に上位10位内に入りたい。

問題 208 Firetruck

消防所から火事箇所までの通るルート(道筋)をすべて列挙する問題。道路の各交差点に番号が振られていて、消防所最寄の交差点は常に番号1と決められている。火事箇所は各ケースの1行に与えられている。各交差点は最大1回 しか通ってはいけないのが条件。

まともな問題だが、特殊ケースは2つ。
 1.番号1が火事箇所であるケース。ルートは1本しかない。
 2.火事箇所に通じる道筋のないケース。ルートはない。つまり、0本になる。

再帰によるバックトラッキング手法を使うが、10秒以内に実行を終わらせるには、検索範囲を絞り込む必要がある。

個人的に考えたのは、火事箇所の回りの交差点リストをつくり、これらの交差点をすべて通ったルートなら、それ以上の検索を打ち切る方法。

例えば、ケース1では、火事箇所の6に直結の交差点は4と5、の2つだけ。したがって、4と5を通ったルートはすぐ6に来るか、打ち切られるかのどちらかにする。

問題 158 Calendar

日付関係のプログラムなので、ユリウス日に換算して使うと便利。

ほかには、大事な注意点として、1月の記念日は次年の1月記念日としてもカウントしないといけない。
つまり、入力データが

のようなケースでは、元日とYokoの誕生日を1999年にもセットしておかないとAcceptされない。

最後にテスト用 入力データ と対応の 出力結果 をのせておく。

問題 143 Orchard Trees

実数座標の三角形で囲める、整数グリッド点の数を求める問題。正解率は9.5%しかなく、計算精度が問われるらしい。

今回は下に書いた、点と線の領域判定法で、チャレンジしてみる。

まず、三角形の座標から、x, y の最大・最小範囲 S (長方形) を求める。
三角形の3頂点を A, B, C とし、

  A, B 両点を通る直線から、S の中の Cと同じ側にあるグリッド点を ひとつずつ確かめていく。
  B, C 両点を通る直線から、S の中の Aと同じ側にあるグリッド点を ひとつずつ確かめていく。
  A, C 両点を通る直線から、S の中の Bと同じ側にあるグリッド点を ひとつずつ確かめていく。

これら3回の計算ですべて同じ側にあるグリッド点の数が解答となる。

計算量についてだが、グリッドが最大1万点もあるので、3回の計算で、計 3万回の計算になる。すこし心配。でもやってみよう。

結果は大丈夫だったが、それよりも気をつけないといけないところは、三角形が点になったり、直線になったりする状況。以下は入力のテストデータと正解。

<入力テストデータ>

<それに対応する正解>

なお、3点の座標をそれぞれ、A(x1, y1)、B(x2, y2)、C(x3, y3) とすると、三角形の面積 S は

   S = |(x1*y2 + x2*y3 + x3*y1 - y1*x2 - y2*x3 - y3*x1) / 2|

なので、面積がゼロのときには、3点が同一点か一直線になるわけだ。つまり、

  x1*y2 + x2*y3 + x3*y1 と y1*x2 + y2*x3 + y3*x1

が等しいかどうかを計算すれば判定できる。この計算も線分が水平であろうと垂直であろうと、全く気に必要はないし、整数座標であれば(今回の問題は実数だが)計算誤差も発生しない。

問題 113 Power of Cryptography

正の整数同士のべき乗 p = kn において、教えてくれた n, p の値に対し、式を満たす k を求める問題。

各データの範囲:
   1 <= n <= 200
   1 <= p < 10101
   1 <= k <= 109

対数計算すればすぐに判ることだが、k は 230 以下なので、32ビットの unsigned long 整数でOK。

p について、桁数の多い値を正確にプログラムに取り込むのは困難なので、仮数部 x と指数部 y に以下のように分けて記録する。浮動小数点になり、精度は落ちるかもしれないが、101桁の巨大整数にも対応できる。

    p = x * 10y  ただし、 0.1 <= x < 1

それで、y は10進数の桁数になる。例えば、Sample Input にある数字 4357186184021382204544 を  0.4357186184021382 * 1022 と表現するし、4 を 0.4 * 101 とする。

仮数部 x は、pの入力行の先頭に 「0.」(つまり小数点)をつけ、sscanf 関数に読み込ませば、x の値が得られる。指数部 y は入力の桁数から正確に読み取れる。

それで、

   p = kn
   log10p = n * log10k
   log10(x * 10y) = n * log10k
   y + log10x = n * log10k
   k = 10(y + log10x)/n

となる。k を pow 関数 pow(10, (y + log10x) / n) で計算できる。

ちなみに、Gnu C の仮数部精度は、float で 7桁、double で16桁、long double で 20桁となっているようだ。たとえ、16桁で計算してみると、

正解は 1234 なので、誤差にどう対処するかは課題。

例えば、k-1, k, k+1 等と、得られた k の近辺の値で確かめ算して、誤差の一番少ないものを答えとするとか。

問題 111 History Grading

判りにくい説明といい加減な例。それに引っかかる人が多いのも無理がない。

例をもって説明するね。教師の正解は 3, 1, 2 だとする。事件1、事件2、事件3がある。どういう順番で事件がおきていたのだろうか。

 事件3 → 事件1 → 事件2

と理解したら大間違い!

正しくは、事件1が3番目、事件2が1番目、事件3が2番目で起きていたというふうに理解しないといけない。つまり、順番として、

 事件2 → 事件3 → 事件1

が正しい。

それで、Sample Input 2 の正解 3 1 2 4 9 5 10 6 8 7 と 2番目生徒の解答 4 7 2 3 10 6 9 1 5 8 を時間軸に直す。

それでやっと正解数5が得られる。つまり、4通りの最長一致部分列 3 (1|4) 6 10 (7|5) があるから。最初の間違った理解ではどうやっても5が出てこない。

さて、飛び飛びではあるけど、二つの文字列から、最長一致部分列(LCS)を選び出す方法を次のグラフで考えてください。


最長一致文字列の求め方

つまり、両文字列に文字の一致するところを○つけ、○が繋ぐような、右下方向にもっとも長く伸びるパスがその答えとなる。矢印はひとつの解だが、ほかにも長さの同じパスが3本存在する。

くだらないプログラムのため、Pascal コンパイラが必要になるかもしれない。

Gnu Pascal も有名だが、インストールがすんなりにいかないみたいで、手っ取り早く Free Pascal を Linux に入れてみた。ソースのコンパイルエラーの確認ならどれもいいだろう。

<ダウンロード先> Free Pascal

Linux (Intel X86) 用の RPM (Redhat Package Manager) Packages
ファイル名 fpc-1.0.10-0.i386.rpm
      (4.49 MB) contains the compiler, utils, RTL and all units.

ダウンロードしてきて、コマンド

一発でインストールできるはず。なお、コンパイルコマンドは

になる。

問題 109 SCUD Busters
難易度 投稿数 4752 (正解率 30.7 %)

まだ解けていないが、いくつかのことをメモしておく。

最初は簡単に解ける問題だと思っていたが、やってみたらサンプル出力の値よりはずいぶん小さい結果しか得られなかったことに驚いた。

与えられた多角形内の点(家とか発電所)が必ずしも多角形の頂点でないことにやっと気づいた。そうでないと、2番目の王国(下図)の例でも判るように、国境線が定まらない。

「the area of a kingdom is the area enclosed by the minimal-perimeter thin wall.」 見落としがちな文章だが、凸包のことを言っていると思う。また、説明文に頂点のことを一言も言ってないのもこれで納得した。

<問題の整理>
複数の多角形P(多角形自体ではなく、それに含まれる点だけが与えられる)と、いくつかの点Aが与えられ、多角形の中から、Aを囲むものだけをピックアップし、それらの多角形の面積を求める問題。

<クリアすべきこと>
  1.点を囲む多角形を求める ← 凸包を求める
  2.点が多角形内にあるかどうかの判定 ← 解決済(アルゴリズムは本ブログに既出
  3.多角形の面積計算 ← 簡単にできる

<凸包を求めるアルゴリズム>
  平面上の点集合の凸包とは、その集合のすべての点を含む最小の凸多角形のこと。また、凸包とは点を囲む最短の閉路(つまり、点をすべて囲み、周長が最短なものは凸包という)。
  与えられたN個の点に対して、そのいくつかが凸多角形を作り、残りのすべての点はそれに含まれる。凸多角形の頂点となる点をみつけるのは、凸包を求めるアルゴリズムという。

サンプル入力にあった2番目の王国の国境線(つまり、5点を囲む凸包)

問題 108 Maximum Sum
難易度 投稿数 15675 (正解率 42.1 %)

NXN の行列から、最大値をもつサブ行列を求める問題。

計算時間を意識しないといけない。O(N6) のプログラム、つまり for文を 6重に使う解答では、計算時間オーバーでパスできない。

O(N3) のアルゴリズムもあるみたいだが、O(N4) のものに思いつき、投稿したら accepted になった。

配列を沢山取り、ひたすら加算する。計算時間の稼ぎに、メモリ資源を使う。こういう戦略だった。

解答ヒントのメモ。

問題 107 The Cat in the Hat
難易度 投稿数 18906 (正解率 15.9 %)

技法の問題というよりも、純粋に数学の問題かもしれない。

入力データは正の整数二つ、data1 と data2。 問題を読めば判るが、
   data1 = (N+1)k
   data2 = Nk

となる。出力結果も2つの整数、 output1 と output2
   output1 = (data2-1)/(N-1)
   output2 = data1 + N * (data1 - data2)

つまり、Nの値さえ判れば、簡単にプログラムは解ける。

整数の長さ(上限)について、問題では全く(わざだと思うが)触れていなかったが、解答してみて判り、32ビットの整数だけを考えればOK。64ビットとか、さらに数百ビットとかになるとえらい大変だが。

ということで、与えられた、32ビット以内の整数 (N+1)k と Nk に対し、N を求めなさい、というのが問題の本質。

ただし、 2k と 1 の入力ペアについても、その処理を忘れないように。

今年のACM 国際大学対抗プログラミングコンテスト・ACM International Collegiate Programming Contest (ACM/ICPC) 2004 アジア地区予選 愛媛大会が無事終了したようだ。

今年は準備不足で参加できなかったが、来年はぜひ乗り込んで参加してみたい。大学生ではないので、プログラマとしては無理だが、コーチでもなんでもとにかく見てみたい。

スポーツと違って、優勝したからといって賞金をもらうわけではない。日本では、科学技術を見る世間の目が厳しい。しかし、就職等では圧倒的に有利だろうし、優勝すれば一生プログラマとしてやっていけるから、世界的に大きなアドバンテージを手にすることになる。

ここで優勝するのはそう簡単ではない。知識、熟練度、経験、英語力、チームプレー、すべてがものをいう。今年の問題は総じて易しいが、5時間内8問(問題は全部で9問)も解いた中国チームはやはり凄い。コーチの役割はよく判らないが、メンバー3人なので、1人が3問弱、5時間内解いたことになる。私だってこれぐらいのことしかできないと思う。

似たようなシステムが http://acm.uva.es/problemset/ にある。登録しておけば、解いたプログラムをオンラインで判定してくれる。オンラインコンテストも年数回開催している。本人 も2日間しかやってないが、昨日から判定の受付がどうも機能していないようだ。(後日の追加)理由不明だが、IDがどうも無効になってしまったようだ。それでまた登録し直した。

狂うほど毎日ゲームに夢中するひとが多いが、プログラミングの喜びはぜひ多くの人に味わってもらいたい。数学と違ってやればできるところ、実用的なところがプログラミングの魅力だろう。これからの世の中、プログラム無しではなにもかも機能しなくなるのだから。