問題概要 日本語なので本文参照（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0224&lang=jp）自宅から、ケーキ屋とランドマークからなるノードを通り役所まで行く。 ケーキ屋の前を通るときにはそのケーキ屋のケーキを食べ、カロリ…

問題概要 日本語なので本文参照（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0223&lang=jp）w*h枚の正方形からなる長方形のグリッドであらわされるデパートに双子がいる。 デパートにはいくつかの障害物が存在する。 双子は上下左…

問題概要 重みのない無向グラフで表される都市が与えられる。 グラフの頂点の場所にいくつかスーパーを出店し、どの頂点に住む人も、その頂点または隣の頂点にスーパーがあるような状態にしたい。 このとき、必要なスーパーの数の最小値を求めよ。

問題概要 日本語なので本文参照。（http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1161&lang=jp） ACM + IBM = ICPC のような覆面算の答えの総数を求めよ。 一つのアルファベットには0〜9の一つの数字が対応する 異なるアルファベッ…

問題概要 日本語なので詳しくは本文参照。 （http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1022） 盤面 4=..2 +#=#+ .-2=. =#*#= .-.=3 空白を埋める候補 7 3 1 4 / 8のようなパズルの盤面および候補が与えられる。 '#'は壁で、そこ…

問題概要 辺に英小文字からなる呪文が書かれた有向グラフがある。 スタートからゴールまでグラフを辿ったときに得られる、「それまでにたどった辺の呪文を並べた」文字列のうち、辞書順で最も先頭に来るものを最強の呪文と呼ぶ。 最強の呪文が一意に決まる場…

問題概要 グリッド上に描かれた迷路が与えられる。このとき、ゴールまでの最短の道のりを求めよ。 迷路は各グリッドの壁の情報によって与えられる。

夏に苦労したPKU1011 Sticksを彷彿とさせる探索問題。今回は2回目でACしたけど。 問題概要 それぞれの長さの与えられたn本の棒（n≦20）を使って正方形を作ることができるか判定せよ。 この問題、使わない棒があってもいいともダメとも書いてないしサンプルか…

東京大学プログラミングコンテスト2009(Problem F) いつの間にかUTPC2009の問題が追加されていたようだ。 問題概要 音の出るn段の階段を、長さmの決められた旋律を演奏しながら降りることはできるか。（n,m≦50000） 階段の降り方は以下の３通り。 1段降りる…

ICPC 2009 東京予選 Problem J 問題概要 n×n（n≦5）セルのライフゲームのセル全て死滅させるのにかかる最小ターン数を求める。ライフゲームのルールは通常と同じである。すなわち、 ターン開始時に、生物のセルについて、周囲8セルのうち、2つまたは3つが生…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2089カーペットで多重化(2^8)してBFS. DFSで書いたらTLEだったけれど、BFSだと枝刈り全くなしで0.2s未満で通る。

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1162昔BFSで書いてTLEだった問題。 隣接リスト使用＆アルゴリズムをダイクストラ法に変更したら時間制限内に終わった。久しぶりのダイクストラだったので演算子多重定義の書き方を忘れ…

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1048前にWA出て放置していた問題。商品で多重化(2^15*10個のノードに)して探索。 BFSで書いてみた。