ICPC2008国内予選

コーチしてない,というより開催終了したんだということを今知った.
のでざっと問題を見ての難易度と解法(コーディングしてないので本当に解けるかは不明)をメモしてみる.

A 等しい合計点 (Equal Total Scores)

100*100=10000だから全パターン試すのが一番楽かも.若干の高速化としては両者のカード数値の合計が奇数だったら-1を出力,という程度かな.

B 月曜土曜素因数 (Monday-Saturday Prime Factors)

そもそも名前がどうよ,という問題.こういう素因数分解系の問題は先に与えられた範囲での素数(MSP; Monday-Saturday Prime)のテーブルを作成するのが常套手段.30万÷7×2=8.4万の候補用フラグを作り,√30万=547以下のMSPを使って篩い落とすだけ.手元の資料によると30万以下の普通の素数は25997個あるらしいので,同じ率で考えれば7500個程度?
テーブルができたらあとは試し割りで出力のループ.

C 如何に汝を満足せしめむ? いざ数え上げむ… (How can I satisfy thee? Let me count the ways...)

演算については下手に012を組み合わせた演算を作るよりは配列で演算結果を定義して辞書引き.
あとは式解析器(多分,上記演算器と組み合わせて再起で作るのが楽)を作る.
あとはPQR(先に出てくる文字をチェックして不必要なカウントをしないようにして)の3重ループでカウント.

D ちょろちょろロボット (Twirling Robot)

正確な解法は思いつかず.とりあえずロボットシミュレータ必須かな.データは枠外の停止処理の例外が面倒なので[1〜h][1〜w]に入れて,[0,h+1][*],[*][0,w+1]はHalt番兵を代入.

E 大玉転がし (Roll-A-Big-Ball)

問題文の「ひとつ」「よっつ」「いつつ」の表記が非常に気になる.

  1. 最初に0出力(移動線上にブロックがあるか)を確認
  2. 半径をr=1000と仮定
  3. 各ブロックについて
    1. 動線分までの最短距離 d を計算(ブロックの辺から線分終端までの距離が最短になることがある,ということに注意)
    2. d < h なら(a)で,d > h なら(b)で仮半径prを計算
    3. rとprのうち小さい方をrに突っ込む

で大丈夫だと思う.多分一番面倒なのはdの計算?

F ICPC: チョコレートの知的合同分割 (ICPC: Intelligent Congruent Partition of Chocolate)

タイトルのICPCのネタは日本語を読む分には分からない,でも達也と和也とかいうネタは英語(を母国語とするような人には)分からないという罠.どっちも問題本質とは関係無い.
こちらもまだ確定的な解法は思いつかず.適当な1個を和也のとして,その隣接を再帰的に探る深さ優先探索だと時間がかかりすぎるんじゃないかなぁ…の予想.