http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1339 実装：23分 問題 トーラス上で3x3のスライドパズルをするので最短手数を求めよ。 解法 やるだけ。状態管理が遅くてTLEになったのでunordered_mapとか使った。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1341 問題 3次元空間上に点がn+m個ある。ある点よりもx,y,z座標が全て大きい点をつなげていくと最大何点までつなげることができるか。 n+m 解法 x,yをソートして後に2分探索できると気づかんかっ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1337 実装：15分 問題 矩形で領域が複数の箇所に分割されている。何分割されているか求めよ。 1 0 解法 nが小さいので座標を2倍して座標圧縮した後にBFSで領域を数えた。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1336 実装：7分 問題 n匹のアリが長さlのトンネルの中を歩く。 トンネルの中は整数座標以外ではアリ同士はすれ違うことができるが、整数座標の場合はぶつかってそれぞれのアリが反対を向く。 アリ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1335 実装：4分 問題 n以下の数がちょうどk個であるような集合で、数値の和がsになるのは何通り？ 1 1 1 解法 数値が小さいのでn,k,s全部をキーにしたDPをした。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0553 問題 略 解法 尺取メソッドでやる。 潜れる場合は何も考えずに潜る。潜ると死ぬ場合は、headとtailの間で回復量最大の泉で回復する。HPの上限に達する場合は2番目に回復量が大きい泉と比較し…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2329 実装：40分 デバッグ：10分 問題 n個のマップがある。それぞれのマップにはmi頂点の平面埋め込みされたグラフが与えられる。またマップ間を移動する手段としてワープがあり、ワープを使って…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2384 設計：40分 実装：50分 デバッグ：1時間 問題 うさぎがk匹、岩がn個ある。うさぎは初期位置から岩を順に飛んでいってそれぞれの目的地に行きたい。ただし他のうさぎが踏んだ岩を踏むことは出…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2349 設計：1時間 実装：1時間 デバッグ：1時間 TLE解消：2時間 問題 N個の国がある。各国には都市がMi個あり、国際空港がFi個ある。国の間を移動するには国際空港からしかできない。上記の条件で…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2368 実装：30分 デバッグ：15分 問題 略 解法 まず全ての線分の端点と交点をset,mapに突っ込んでおく。次に各線分に対してsetに突っ込んでいた点が乗っているかチェックして、乗っている場合は距…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2341 問題 単語がn個ある。その単語を重複有りで並べ替えて出来るm文字の文字列でk番目のものを答えよ。ただし、使う単語の順番が異なった場合それは違う文字列とみなす。 1 1 1 解法 解説通りにx…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2343 問題 N*N行列に値が入っている。行列を回転させたり、列や行をswapさせる命令や行列のある場所に値を書き込むクエリがQ個来る。全てのクエリをさばいた後に指定された部分行列のハッシュ値を…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2393 問題 H*Wの盤面に仕切りをしいて迷路を作りたい。ただしある地点から別の地点への行きたかはちょうど一通りなければならい。迷路の作り方は何通りあるか？ 1 1 解法 迷路の作り方は全域木の…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1089 問題 略 解法 ConvexCutを使えばケーキをある角度で切った時の面積はでる。ここで角度0と角度PIで切った時、その左側の面積が片方は半分以下になり、片方は半分以上になる。なので中間値の定…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2367 問題 略 解法 てきとうにはしょりながら文字列を全部展開して、すべての部分文字列とstrstrで存在するかどうかを比較した。はしょる方法は400文字以上の繰り返しは繰り返し回数を適当に減ら…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 問題 m頂点の凸多角形の街がある。その街にはシェルターがn個ある。ある人がどの場所にいる確率も一様な時、シェルターまでの最短距離の二乗の期待値を求めよ。 3 1 座標 解法 ボロノイ図を…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2374 問題 略 解法 忘れた。たしか多い方からgreedyに取っていきつつ、取っていった分をずらしてごにょごにょすれば行けた気がする。 下のコードはたしかm-judgeではTLEしたけど、AOJでは通った。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2380 問題 図の様なパズルがあるので最短何手でクリア出きるか答えよ。答えが6以上になる場合は-1を出力すること。 解法 反復深化とか幅優先探索てきとうに。間に合わない場合はてきとうに最後の…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2372 問題 略 解法 Fib(10)くらいまでのIka Numberの表を2次元で書き下してみると法則性が分かるので後は実装するだけ。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2373 問題 略 解法 とする。どの長さを使うかと、どの様に並べるかは全探索する。その二つが決まったらを制約条件の下で求め目れば良い。これはラグランジュの未定乗数法を使うと解くことが出来、…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2379 問題 サイコロの展開図が8個ある。そのサイコロを8個を組み合わせて2倍の大きさのサイコロを作りたい。作るときの条件は サイコロの内側は黒色 サイコロの1つの表面の色は統一されている サ…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2386 問題 N頂点の完全無向グラフがある。ハミルトンパス出きるように辺に向きをつけたい。辺の向きを付ける時のコストを与えるのでその様なグラフを作るときの最小コストを求めよ。 1 0 解法 完…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2383 問題 ステージがN個ある。全てのステージをプレイしたいのだが、以前クリアしたステージの難易度-Tよりも簡単なステージはプレイできない。ステージの並べ方は何通りか？ 1 解法 ステージを…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2382 問題 W,Hのフィールドに居るN体のスライムを蹴って、一箇所に集めたい。スライムは一度蹴ると端か他のスライムに当たるまで止まらない。また蹴ったスライムが他のスライムに当たると2体は合…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2376 問題 略 解法 dp[odd][even][e]を計算して解く。oddは頂点の数が奇数の連結成分の個数、evenは頂点の数が偶数の連結成分の個数、eは連結成分内でまだ使用してない辺の個数の偶奇を表す。eの…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2370 問題 略 解法 まずグラフを2彩色出来なければ答えは-1になる。2彩色できたら各連結成分に白の数と黒の数のminと差を記憶しておく。追加する辺の数を最大にするには2部グラフの片側に何個頂点…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2234 問題 略 解法 解説を参照。法が互いに素でない場合の線形連立合同式の解き方はnyaさんのライブラリとMATHEMATICS.PDFを参考にした。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2107 問題 略 解法 辺の数が50と少ないので、最後に使った辺+どちらの頂点に行ったかで状態を保存し、その遷移行列を作る。この行列をz乗すればちょうどz歩でn-1の頂点に辿りつけるかどうか分かる…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2308 問題 Angry Birdというゲームがある。このゲームは鳥を初速度vで投げ飛ばし、豚にむかって卵爆弾を落とすゲームである。鳥は投げ飛ばすと放物線運動をし障害物にぶつかるまで移動する。豚に…

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2193 問題 略 解法 実質的に3頂点のシュタイナー木を求める問題になる。なのでレノンのいる場所から頂点vまで行き、なつめのいる場所により、また元の位置vまで戻ってきて、夏への扉へ向かえば良…