japljさんが幾何の問題集をVirtual Arenaでセットしていたので、最近ちょこちょこやっている。 まだ途中だけど、とりあえずまとめる。 http://rhodon.u-aizu.ac.jp:8080/arena/room.jsp?id=1178&active=status AOJ 2045 - Turn Polygons 多角形の中にある多…

フィボナッチ数をまとめてみた。 「AOJ2372 - IkaNumber」の解説も入ってる。https://www.dropbox.com/s/6nx2f9htpfyvnkv/fibonacci.pdf競技プログラミングと関係のありそうなフィボナッチ数の話題があったら教えて下さい。とりあえずProject Eulerまわりを…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 ICPC Asia Tokyo 2012 Problem I 問題 図1のようにN個の単語を配置する。 1行にはスペースを含めW文字入る。 入力としては、i番目の単語の長さがxiとして与えられる。 以下良い配置の条件 入…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 問題 頂点数Mの多角形領域の中に，N個のシェルターがある。 多角形領域の中に等確率で位置すると考えたとき、最も近いシェルターまでの距離の期待値を求めよ。 制約 M,N -1000 解法 あるシェ…

現実逃避の続き http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2211 問題 略 解法 答えについて二分探索。 答えをk以下に出来るかどうかを判定したい。 猫と餌入れはx座標でソートしておく。 解説スライドの通り dp[i] = i番目に餌を置いた時に…

現実逃避 問題 n個の椅子がある円卓がある。 ここに8人の王子が座る。 ただし、王子が隣り合ったり、ちょうど向かい合ったりしてはいけない。 このとき、何通りの座り方があるか。 回転したり反転したりして同じになるものも区別して数える。 制約 答えは10^…

for アジア地区 問題 n個の円が与えられる。 i番目の円は、中心(x[i],y[i])、半径r[i]である。 全ての円を内包するような半径Rの円を動かしたときにできる領域の外周の長さを求めよ。 制約 1 円はoverlapしうる。 解法 求める外周は 1つの円に接するような半…

ICPCアジア地区予選に向けて 問題 h×wのマップが与えられる セルの意味は以下 数字セル：９近傍に宝がその数字の数だけ埋まっている '*'：宝が埋まっているかもしれない '.'：何も埋まってない このとき埋まっている宝の数は最小でいくらか 制約 1 1 解法 数…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1026&lang=jp 解法 はてなダイアリーで書くのが非常に面倒だったのでパワポで書いた 図のようにx軸y軸を取り、x軸とy軸に液体が接している時を考える 青線が液体の表面に対応している ということ…

問題 0~9の数字が書かれたk個のダイアルがある鍵を考える。 連続するダイアルを同じ方向に同じ数だけ回す動作を１手とする。 このときダイアルを初期状態sから目標状態tにする手数を求めよ。 制約 1 解法 まず回す順番は関係がないので左から数字を合わせて…

問題 ２枚ずつのM種類のカードN(=2M)枚で１人神経衰弱をする。 今までに開けたカード全てを記憶出来るとき、ミスマッチする回数の期待値を求めよ。 制約 2 解法 カードを１列に並べたものをイメージして、左から順に開けていく。 今開けようとしているカード…

問題 N種類のコインを使ってm円のお釣りを支払う。 違う種類のコインなら1つの操作で支払うことが出来る。 このとき操作の最小回数を求めよ。 制約 N M 解法 1回の操作での支払い方は2^N通りある。 2^N種類のコインがある場合の普通のお釣りDPをすればいい。…

問題 略 解法 文字列を引数とした再帰による構文解析を実装するのが楽。 優先順位が低い方から文字列を見る（同じ優先順位なら同時）（左結合なら右から、右結合なら左から）。 全体が括弧でくくられる式が来たら括弧をはずす。 ソース vector<vector<char> > g; vector<bool> t</bool></vector<char>…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2333 問題 略 解法 入力（a[i]とする）を降順でソートする。 a[i]までの合計をsum[i]とする。 答えを、 (a[n-1]まで全て使うときの解) + (a[n-2]まで全て使い、a[n-1]は使わないときの解) + ... +…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2028 問題 １人用ゲームをする。 カードを表す数列が与えられるので、カードを円状に並べることを考える。 1. あるカードを選んで、そのカードを時計回りで次のカードの上に被せる。 2. このとき…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308 問題 ライツアウトで解法があるかどうか調べる。 普通のライツアウトはある点を押すとその点とマンハッタン距離１の点が反転するが、この問題ではその点とマンハッタン距離dの点が反転する。…

ICPC2010アジア予選の問題で、 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1308 というものがあった。 普通のライツアウトはある点を押すとその点とマンハッタン距離１の点が反転するが、この問題ではその点とマンハッタン距離dの点が反転す…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1269 問題 n, kが与えられるので、nを異なる素数k個の和で表すときの表し方の数を求めよ。 ただし、順番を入れ替えただけのものは同じと考える。 解法 DP。 重複が許されないので、普通に考えると…

問題 車のレースをする。 １台の車だけを考える。 n個のチェックポイントでタイヤを交換するかしないか選ぶことができる。 ここで、n個目のチェックポイントがゴールである。 タイヤを交換した場所からの距離をxとすると、xからx+1まで走るのにかかる時間は…

問題 さいころ27個を図のように並べる。このとき、合わさる面の数字同士の和は7になるようにする。 また、それを上から見たときの数字と前から見たときの数字が入力として与えられる。 ただし入力の数字が0ならばその位置の数字は何でもいい。 考えられる全…

問題 三角形の頂点の座標が与えられる。 三角形に図のように内接する３つの円の半径をそれぞれ求めよ。

問題 ソース int ba[7][7][7]; int n, m; int d[13][3] = {{1,0,0},{0,1,0},{0,0,1}, {1,1,0},{0,1,1},{1,0,1},{1,-1,0},{0,1,-1},{-1,0,1}, {1,1,1},{1,1,-1},{1,-1,1},{-1,1,1}}; bool judge(vector<int> p, int c) { vector<int> a(3); REP(i, 13) { int cnt = 0; f</int></int>…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1243 問題 4×4で表される国がある。 風の神であるあなたは、2×2で表される雨雲を動かすことができる。 入力として、期間の長さと、それぞれの日のそれぞれの区画で市場もしくは祭りが開かれるかど…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2210 問題 略

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1237 問題 数字とtargetが与えられる。 数字を分割してその和がtargetを超えないで最大となる分割の仕方を出力する。 そのような分割の仕方が2つ以上ある時はrejected。 どのように分割してもtarg…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1068&lang=jp 問題 略

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1227 問題 "2"なら"a","b","c"の3通りが考えられる。 辞書が与えられるのでその単語が使われるような文を全て出力する。という程度の問題。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218 問題 図見れば分かる。 貨物を何回動かせばゴールに到達できるか。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2264 問題 略

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1213 問題 10000×10000の島があり、IC、PC、ACMが住んでいる。 この島では毎日、空から任意の場所に宝石が落ちてきて、この宝石が落ちた場所に最も近いところに住んでいる人が宝石を得ることが出…