2015年のICPC国内予選が開催されてから2ヶ月近く経ってしまいましたが、ようやく全問解き終わったので回答を公開しました。

2008年が現役最後の年だったので実に7年ぶりの挑戦になりましたが、面白い問題も多く楽しむことができました(もちろん、苦しむことも！)。

すでに入出力データや順位表などの各種情報は出揃っていますので、興味がある方はそちらも見てみると面白いと思います。

問題はA〜Hの全部で8問でしたが、A〜Cが易しく、D〜FとHにやや苦戦、Gに大苦戦という感じでした。特に時間などは決めずに解いていましたが、本番の3時間半にあわせるとわたしは3〜4問くらいしか解けないだろうなと思います。問題の難易度を正確に判定することは難しいですが、体感的にはA < B < C << D < H < E = F < Gでした。個人的に面白かったのは問題EとFで、一番苦しんだのは問題Gでした。

以降は、各問題についての概要、自分の解法とその説明です。

問題A

ループが使えれば解ける問題で、どちらかというと落ち着いて問題文を読解できるかどうかが鍵だと思います。

問題B

単語列が与えられるので、短句の条件を満たす最初の連続な部分列を求める問題です。短句の条件は次の通りです。

（短句の条件）
単語の並びを五つにうまく区切ることで，
最初の区切中の単語の総文字数が 5，7，5，7，7 と続くようにできる．

問題C

カッコを使わない特殊な記法で記述された式の値を計算する問題です。

構文解析しつつ式の評価を行うだけです。構文解析に慣れていない人は、tanakhさんの10分で書ける、お手軽パーザー(Web Archive)という記事を読んで、一度実装してみると同じような問題を解けるようになると思います。

問題D

500円玉貯金をするために、買い物のお釣りで最大何枚の500円玉を得ることができるか、また、そのときに必要なお金の総額の最小値を求める問題です。

一目見てDPだなと思いましたが、DPでした。表は、500円玉の最大枚数[n件目のお店][n件目で持っている小銭の総額]と構成しました。最終的な答えはこの表の最後の行の最大値になります。表の要素を計算するためには、次の3つのパターンを考慮するだけで十分です。

n件目のお店で買わない
n件目のお店で買う
2.1. お札だけ出して買う(500円玉の枚数は増えない。持っている小銭の総額が増える。)
2.2. お札と小銭を出して買う(500円玉の枚数は1枚だけ増える。持っている小銭の総額は減る。可能でない場合もある。)

もう少し数学っぽく書くなら次のようになります(お釣りの計算方法は端折ります)。

500円玉の最大枚数[n件目のお店][n件目で持っている小銭の総額] =
  min(500円玉の最大枚数[n-1件目のお店][n-1件目で持っている小銭の総額],
      500円玉の最大枚数[n-1件目のお店][n-1件目で持っている小銭の総額 + n件目のお釣り],
      500円玉の最大枚数[n-1件目のお店][n-1件目で持っている小銭の総額 + n件目のお釣り - 500] + 1)

最終的な答えには500円玉の最大枚数だけでなく、そのときに必要なお金の総額の最小値も必要ですが、少し工夫するだけで対応できます。具体的には、500円玉の最大枚数の表と同じ大きさの表を用意して、500円玉の最大枚数の表が更新されたときだけ更新するだけでOKです。

この解法での計算量は、持っている小銭の総額をxとすると、 $O(nx)$ です。nは最大で100、xは最大で49900(1円の商品を売っているお店が100件ある場合)です。

なお、わたしは1度の買い物で得られる500円玉は高々1枚であることを見逃し、少しハマってしまいました。これは、例えば1000円のお釣りは、500円玉2枚ではなく1000円札1枚でお釣りが返ってくる、ということです。

お釣りの枚数の最小化などの類題を解いた経験があれば、手持ちの金額を表のインデックスにするという点は同じなので、解法を思いつきやすいかなと思います。お釣りの枚数の最小化を知らない人は、DPの話に出てくるコインの両替問題を読んでみると良いと思います。

問題E

命令列が与えられてデッドロックを検出する問題です。ロックとスレッド数は10個で固定ですが、命令長が最大10000です。

状態数を考えると素直にシミュレーションするのはダメということは分かるので、DPっぽいなと思いましたがしばらく解けませんでした。

まず、2つのスレッドの場合を考えてみると、スレッドの状態(獲得済みのロック集合と、次に獲得しようとしているロック)が決まればデッドロックを判定できます。したがって、2つのスレッドの状態の組み合わせを列挙できれば良さそうです。1つのスレッドの状態を列挙するには、与えられた命令列を実行するだけです。1つのスレッドの状態が列挙できれば、2つのスレッドの状態の組み合わせも列挙できます。ここで、2つのスレッドの状態の組み合わせについてさらに考えてみると、次の4つのパターンに分類できることがわかります。

(1) 任意の順序で実行できる

(2) デッドロックする

(3) ブロックする

(4) 同じロックを獲得済み

「(1) 任意の順序で実行できる」のケースは、どちらの状態も発生する可能性があります。
「(2) デッドロックする」のケースは、お互いに獲得済みのロックを獲得しようとしているのでデッドロックします。このケースを一つでも検出したら、与えられた命令列が危険であると判断することができます。
「(3) ブロックする」のケースは、両方のスレッドが獲得済みのロック集合の和集合を獲得済みで、ブロックされていない方のスレッドが獲得しようとしているロックを次に獲得しようとしている状態と考えることができます。
「(4) 同じロックを獲得済み」のケースは、発生することはないのでこの組み合わせの状態は無視します。

特に(3)が重要で、これに気がつけば、1つのスレッドで発生する状態から、2つのスレッドで発生する状態、3つのスレッドで発生する状態、…と次々に求めていけることが分かります。したがって、10個のスレッドで発生する状態まで列挙して、その間にデッドロックする状態がなければ安全と判断することができます。

スレッドの数を $T$ 、ロックの数を $L$ とすると、スレッドの状態数は最大で $L \times 2^L$ 個なので、計算量は $O(T \times (L \times 2^L)^2)$ になります。 $T$ と $L$ が10であることを考えると厳しいように思えますが、スレッドの状態数はそれほど多くならないようです。

問題F

$n$ 個の島の間で行き来できるように、建設会社Aの橋を $k$ 本、建設会社Bの橋を $n-1-k$ 本建設するときの最小の費用を求める問題です。

建設会社が1つであれば単なる最小全域木(MST)の問題ですが、2つだとどう構成すれば良いのか自明でなくなります。最初はDPで解けるのではないかと考えていましたが、うまく構成できる方法が思いつかず、最終的には証明なしで貪欲法で解きました。

建設会社Bの橋だけでMSTを構成して、 $k$ 本になるまでMSTを保ったままA社の橋を使うと良くなる、あるいは、同じ橋を見つけて交換します。

tmaeharaさんが国内予選F問題の解説のふりをしたマトロイドの解説で詳しく解説されていますので、そちらを参照するのが良いと思います。

問題G

与えられた凸多角形を2つの頂点が重なるように1度だけ折ってできる多角形のうち最も複雑な多角形を求める問題です。複雑な多角形とは、頂点数が多く、同じ頂点数の場合には周長が長いことをいいます。

問題Gが一番苦戦した問題でした。計算幾何の問題はコーナーケースが多いので間違えやすく、本番ではライブラリがないと解くことがなかなか難しいジャンルの問題だと思います。解法は、すべての頂点対に関して折ってみて、2つの凸多角形をマージしてできた多角形の中で最も複雑なものを計算すれば良いです。私がつまずいたのは、2つの凸多角形のマージ操作でした。外側の点列を追跡するだけなのですが、間違っている答えを出力したときにどこが間違っているのかを突き止めることが難しく、デバッグが難航しました。結局、計算途中と最終的な図形をPostScript形式で出力するようにして、間違いを視えるようにすることで、デバッグしきることができました。

一番苦戦したサンプル入力の7個目の複雑な折り方を図にしてみました。