UTPC2008

土曜日はUTPCに参加。一位を取れたみたい。やたー。

本当はコンテスト後の解説(とくに問題Iとか...)を聞きたかったんだけど、その後すぐにつくばに行かなければならなかったので競技終了後すぐに会場を離脱。懇親会にも出れなかったし、残念だったなあ。

各問題の方針を簡単に書いてみる。ちなみに問題文は今なら「UTPC」あたりでぐぐると上位に出てきます。

A(サイゾウ)

書くだけ。

B(完全数)

√Nくらいまで割ってみるだけ。問題文にあれだけ時間に注意しろと書いてあったのにTLEした自分pgr。

C(ラミー)

RGBにカードを分類して判定してみた。実は提出したコードが正しいか自信がない(ぉ)。B,C問題あたりは周りの人の勢いに焦っていて、酷いプログラムを生産してしまった。

D(バトルタウン)

シミュレーション。2Dフィールドがあったらとりあえず領域外は壁で囲っておこうね！

E(カントリーロード)

実はとなりあう家の間隔を昇順にn-k個取るだけ。こんな感じの、発想しだいでぱっと解けちゃう問題は解けると気持ちよくていい。

F(リズムマシーン)

与えられたリズムパターンを簡約してしまえばあとはマージするだけ。簡約サイズは非零要素の位置についてgcdをとれば分かる。>1024の条件を最初>=1024と書いていてWA。はずかしー。

G(エナジー・トランスポーター)

励起順は右方向に進むものだけ考えればいいと信じてメモ再帰。

H(いけるかな？)

台湾大会で涙目になった問題の類題。kステップで各枝に到達できるかどうかを表す{false,true}ベクトルX(k)を考えると、X(k)とX(k-1)の関係式は(or,and)を加法・乗法とする環上における行列の掛け算に対応する。なので、boolを要素に持つ行列のべき乗からX(z)が計算できる。

I(Aaron と Bruce)

前に類題を見たことがあるけど結局解けてなかった問題。id:EmKさんの解法に納得。

J(いにしえの数式)

スタック作ってがんばる。演算子順位法とかいうらしい。

K(電波基地)

反復深化しながら基地を造っていってみた。中継点として選ぶ二つの基地が直線上に並ぶときが問題になるけど、たぶん目的位置と同じx/y座標を持つやつだけで十分だろーと適当にやったら通っちゃった。

L(チクチクバンバン)

どう見ても図が最終防衛問題だと主張していたので捨て。

あと、先輩のお二方に倣って提出物一式を置いておいた。焦ってて汚いコードになっているので、真似するのはお勧めできません。