AOJ
問題リンク：The Morning after Halloween | Aizu Online Judge問題概要： h*wのグリッドが与えられる グリッドは壁と何もないマスからなり、その中に幽霊が１以上３以下存在する 幽霊はそれぞれ対応した目的地をもっており、すべての幽霊はその対応した目的…
問題リンク : Enegy Transporter | Aizu Online Judge問題概要： n個のノードが一直線上につながれている ノードはそれぞれ値を持つ 両端のノードと値が０のノード以外のノードは自分の値をマイナス１することで 右のノードの値に左のノードの値を加えること…
問題リンク : Geometric Map | Aizu Online Judge問題概要： n本の線分が与えられる （n 線分は必ず１本以上の他の線分と端点で交差している 線分の両端が別の線分の端点と交差しているならばそれは道である 線分の片方だけが別の線分の端点と交差しているな…
問題リンク : Laser Beam Reflections | Aizu Online Judge解法： レーザービームを打つ方向を３６０度ちょっとずつずらしながらシュミレーションした レーザービームを打つ方向さえ決めてしまえばそこからゴールまで到達できるかどうかは一意に定まるので判…
問題リンク：Nails | Aizu Online Judge解法： いもす法のサイトの解説参照以下手順だけ 輪ゴムの頂点を(x,y),三角形のサイズをdとする ２次元配列gを用意する（vectorで動的にサイズを確保した） gの(x,y),(x+1,y+d+2),(x+d+2,y+d+1)の値をプラス１ (x+1,y)…
問題リンク : Substring | Aizu Online Judge 解法： ローリングハッシュを使う 文字列をハッシュ値に変えてsetで管理した 適当に基数選んで逆元を手元で計算して使った本番解けなくて解説聞いたまま放置してたけどついにやったったコード： #define REP(i,s…
問題リンク : Angel Stairs | Aizu Online Judge解法： 天使が奏でたい曲を最初からみていくのではなく最後からみていく 最初から見ていくと移動先が複数考えられるが、後ろから見ていくと移動先は１つに定まる文字列だと扱いにくいのでCからBまでの音を数字…
問題リンク：Bitwise Kingdom | Aizu Online Judge 解法： 最初に求るビット列に何個１が含まれているのかを考える Nビット中i個１を立てた時の組み合わせの数をどんどん足していき、和がM以上になった時点でループを打ち切る (iは１の数で１から最大Nまで)…
問題リンク：Worst Sportswriter | Aizu Online Judge解法： トポロジカル順で色を塗っていき同じ色を持つノードが複数存在するかどうかをしらべた 同じ色を持つノードが複数存在する => どちらが先でも良いノード数をnとする 色は0からn-1までの整数 color[…
問題リンク:Nim | Aizu Online Judge解法：実際にゲーム木をみていく memo[i][j] := 人i に山の残りがjの状態できたときの勝敗 としてメモ化した 自分のチーム基準で結果のブール型をリターンする 山が残り１枚以下になった時、 自分のチームのターンなら re…
問題リンク：One-Dimensional Cellular Automaton | Aizu Online Judge解法： 行列におとして計算した N = 5 T = 1の場合、与えられた式を行列で表すと次の様になる [ S(0,1) ] [ S(-1,0) S(0,0) S(1,0) ] [A] [ S(1,1) ] [ S(0, 0) S(1,0) S(2,0) ] [ ] [ S…
問題リンク：Restrictive Filesystem | Aizu Online Judge解法： 双方向連結リストを実装したコード： const uint64_t INF = 100000000000010; struct List { int identifier; uint64_t range[2];// [range[0],range[1]] bool hasNext,hasPrev; List *prev; …
問題リンク：Binary Tree Intersection And Union | Aizu Online Judge解法： 実際に２つ木を作って指定された処理を行った 配列で２分木を実装するとノードが最大１００個なので配列内に収まらない なのでポインタを使って実装した struct Tree { bool chil…
問題リンク : A Two Floors Dungeon | Aizu Online Judge問題概要： H*Wのグリッドが与えられる 自分は上下左右に移動することができる もし今いる場所が階段なら階段を利用して階を移動することもできる スイッチがあるマスにいるならばスイッチを押すこと…
問題リンク：City Merger | Aizu Online Judge 解法： 巡回セールスマン問題みたいであったcost[i][j] := 文字列jを文字列iの後ろにつなげてできる文字列の長さから文字列iの長さを引いた値dp[1 for i 0..n // 初期化 これ以外はinf dp[1<<i][i] = s[i].length() //s[i] は 文字列i for S i 0..(1<<n)-1 for from 0..n //状態Sでfromからtoへ行く if !((S>>from) & 1) //まだ</i][i]>…
問題リンク：Merry Christmas | Aizu Online Judge解法： 二部グラフにおとしてマッチングをした 二部グラフにする際にリクエストをノードとした エッジをつなぐ前に、家と家の最短距離をフロイドワーシャルで求め、 (リクエストiが終わる時間)+(リクエストi…
問題リンク：格子状の経路 | Aizu Online Judge解法： 問題で言われている通りに書く 自分は最初にcharの2次元配列に壁や床を書き、スタート地点から人を動かしていった dx = {+1,+0,-1,+0}; dy = {+0,+1,+0,-1}; という配列を用意して、最初の時点では0の方…
問題リンク : Never Wait for Weights | Aizu Online Judge解法： Union-Find Tree を使ってグループ分けした 各ノードは色と重さをもつものとする 最初は各ノードの色を自分の配列上でのインデックスと同じにしておく findメソッドでは引数xが属するグルー…
問題リンク : Cards | Aizu Online Judge解法： ほとんど連鎖行列積 コスト計算は連鎖行列積と異なるのでそこを変更するだけ 入力を保存した配列を pair p[] とすると、 コストは p[どこから].first*p[中間地点-1].second*p[中間地点].first*p[どこまで].sec…
問題リンク : Telescope | Aizu Online Judge問題概要： n個の点が円上に存在する その内m個を選んだ時にできる多角形の面積の最大値を求めよ解法： 動的計画法で解いた dp[始点となる点][最後に使った点][点を選んだ回数]:=その時の最大面積 とした for sp …
問題リンク : Road Construction | Aizu Online Judge解法： 各ノードについて、そのノードに最短路で入ってくるノードのなかで最もコストが小さいものを保存しておいた 最終的な答えはノード２からノードNまでのコストの総和 あるノードについて、入次数が…
問題リンク : e-market | Aizu Online Judge問題概要： マーケットの情報が次の形式で与えられる(与えられる情報は1000未満)ディーラーの名前 オーダー（sell か buyか）商品名 金額情報が与えられた順番でオーダーされたものとする つまり、最初に与えられ…
問題リンク：Leaky Cryptography | Aizu Online Judge問題概要：(N1^K) + (N2^K) + ・・・ + (N8^K) = (N9^K) となるKを見つけろ ここで、N1,...,N9,Kは32bit integerで16進数解法： 最下位ビットから決定していった 各Nの各桁についてKの同じ桁を0からfまで…
問題リンク：The Balance | Aizu Online Judge解法： xの値をループで決めて実際に条件を満たすもののなかで最小のものを探した xを決めるとyの値も一意に定まるループの上限はdだと少ないみたいだったので適当に大きくしたコード： int a,b,d; struct P { i…
問題リンク : Sum of Different Primes | Aizu Online Judge解法： 動的計画法を用いてあらかじめ結果をdp配列に入れておく dp[n][k] := nをk個の異なる素数でつくる時の数 dp[0][0] = 1 (０を０個の異なる素数で作る方法は一通りしかない)疑似コード: for i…
問題リンク：Minimal Backgammon | Aizu Online Judge解法： 動的計画法で確率を計算した double dp[T][N] := ターンTにマスNにいる確率 とした 初期ではdp[0][0] = 1 とする疑似コード for t 0..T for n 0..N for i 1..6 dp[next_T][next_N] += dp[t][n]*(1…
問題リンク:Malfatti Circles | Aizu Online Judge問題概要： 略解法： ３つの円の半径はそれぞれ以下のサイトにのっている式で求めることが可能http://forumgeom.fau.edu/FG2003volume3/FG200308.pdf２つの円の半径を2分探索をして求める方法もあるみたい２…
問題リンク : Pipeline Scheduling | Aizu Online Judge問題概要： 5*n (n これは、1回の処理をする際に使用するユニットの状態を文字で表したものである 入力の要素が'X'となっているならばその時間にそのユニットを使用する '.'はその時間にそのユニットを…
問題リンク：Patisserie | Aizu Online Judge問題概要： 箱の長さとn個のケーキの半径が与えられる(1 与えられた箱のにすべてのケーキを収めることができるか？ 大きなケーキの間に小さいケーキがはまり込むことはない解法： ビットDP ケーキの数が最大１２…
問題リンク：The Most Powerful Spell | Aizu Online Judge問題概要： 辺に文字列をコストとしてもつ有向グラフが与えられる スタートのノード番号とゴールのノード番号が与えられるので最小コストで到達した時のコスト（文字列）を出力せよ 最小コストが存…
