AOJ
問題リンク : Equals are Equals | Aizu Online Judge問題概要 : 複数の数式が与えられる 一番最初の式が正しい答えで、その他の式がそれと同じかどうか判定せよ 細かい制約は略解法 : 各変数に対してランダムに値を割り当て、式の結果が一致するかどうかチ…
問題リンク : True Liars | Aizu Online Judge問題概要 : 自分今、伝説の島にいる その島には正直者と嘘つきがいて、自分はその正直者に用事がある 以前の調査で正直者はp1人、嘘つきはp2人いることが分かっている 今、各人に１から昇順に(p1+p2)まで番号を…
問題リンク : TV Watching | Aizu Online Judge問題概要 : N本のテレビ番組の情報が与えられる 同じ時刻に複数の番組を同時に見ることは不可能なので、自分はそのテレビ番組をリアルタイムで見るか録画して後で見るかを選べる リアルタイムで見た時の満足度…
問題リンク : Crop Circle | Aizu Online Judge問題概要 : n個の円の中心点の座標と半径が与えられる 円周上で他のどの円にも囲まれていないような部分の長さの総和を求めよ解法 : 各円について、他の円との交点で細分化する 例えば円0については以下通りに…
問題リンク : Pump up Batteries | Aizu Online Judge問題概要： N人のボディーガードは1から順にNまで番号が割り振られており、それぞれがウェアラブルコンピュータを身につけている 各ウェアラブルコンピュータは使える時間とその後充電にかかる時間を周期…
問題リンク：Sort the Panels | Aizu Online Judge問題概要： 長さの同じ文字列が２つA、Bが与えられる それぞれの文字列は'B'または'W'のみを要素としてもつ 文字列上のどこかにポインタが存在し、自分はそのポインタを１つ左か１つ右かに動かすことができ…
問題リンク:Square Carpets | Aizu Online Judge問題概要： 最大10*10のマスがあり、それらの中には０か１が書かれている 値が１であるようなマスを全てカーペットで覆いたい カーペットは正方形で、長さは自由に決めれる ただしカーペットで覆うマスの値は…
問題リンク:Nets of Dice | Aizu Online Judge問題概要： 5*5のセルには0から6までの数字がかかれている これがサイコロの展開図になっているかどうか判定せよ解法： 小さいので実際にDFSで展開図になっているかどうか確かめるまず最初に明らかに駄目なケー…
問題リンク:Connect | Aizu Online Judge問題概要: 略解法: １行覚えるタイプの動的計画法 dp[r][c][bit] := (c,r)までで使用する文字列の状態がbitの時の最大値 としてDPする bitの数を数えてその行の文字列よりも多く使用する場合などはcontinueする ２重…
問題リンク:Farey Sequence | Aizu Online Judge問題概要： 略解法： オイラーのΦ関数を使う i == 0 のとき、F_0 = 2 その他のとき、F_i = F_i-1 + (iと互いに素なものの数) となる iと互いに素なものの数はオイラーのΦ関数で求める 前処理でFを作っておいて…
問題リンク:Anipero | Aizu Online Judge問題概要: 略解法： 動的計画法 pre[使用した金額][選んだシークレットアーティストの数(0,1,2人のみ)] := この時得られる最大の満足度 pre2[使用した金額][選んだスタンダードアーティストの数] := この時得られる最…
問題リンク：Futon | Aizu Online Judge問題概要： n枚の布団の位置情報が与えられる それらの布団に人が寝るわけだが、 人の頭のに隣接する部分に他の人の足があってはならない そのような寝方があるかどうか判定せよ解法： グラフを構築して2色でそれらの…
問題リンク：Map of Ninja House | Aizu Online Judge問題概要： 無向グラフが存在する 自分は最初そのグラフのノード番号０のノードにいる 入力が正のとき、それは今いるノードの次数を表す 入力が負のとき、それは（今いるノードの深さ）ー（１つ前にいた…
問題リンク : Petoris | Aizu Online Judge問題概要： h * w のピースと H * W のボードがある ピースとボードは'.'または'#'からなる '.'はそこが空であることを意味し、'#'はそこが埋まっている亊を意味する ピースをボード上に置きたい 置く際には、ピー…
問題リンク：Repeated Subsequences | Aizu Online Judge問題概要： 長さが300以下の文字列があたえられる この文字列を空でない２つの文字列に分ける こうしてできる２つの文字列のLCSの中で最も長いものを出力せよ 複数ある場合はどれを出力しても良い解法…
問題リンク：Triangles | Aizu Online Judge問題概要： 1辺の長さが１の正三角形をn個、任意の点を中心として 360/n 度間隔で置いていく この時n個の正三角形が覆う面積はどのくらいか？解法： 正多角形から余計な部分を引いて面積を出した上の図の黒い矢印…
問題リンク：Color the Map | Aizu Online Judge問題概要： 10個以下の国の情報が多角形として与えられる それらの国に色を塗っていきたいのだが、隣接する国同士は異なる色で塗りたい 同じ国であるならば同じ色で塗らなければならない 最低何色必要か解法：…
問題リンク : Hexerpents of Hexwamp | Aizu Online Judge問題概要 : 略解法：A*(移動した回数) + (大蛇の頭からゴールまでの距離) > 20 なら枝刈りをしたこの問題での２つの6角座標の距離は以下のように計算する (x1,y1) から (x2,y2) への距離distを求める…
問題リンク：Search of Concatenated Strings | Aizu Online Judge問題概要： n個(1 n個の文字列を任意の順で全てつなげた文字列がtのなかにどのくらい存在するか？ ただし、n個の文字列をつなげた際に同じものが複数できた場合はそれらを１つとみなす解法：…
問題リンク：Weather Forecast | Aizu Online Judge問題概要： 略解法： メモ化再帰をした 今何日かと今どこかと1,3,9,11を最後に雨を降らしてから何日訪れていないかを記録した初期化で毎回365*9*7*7*7*7してたらTLEをくらってしまったコード： #define REP…
問題概要：Elevator | Aizu Online Judge問題概要： 日本語なので略解法： 動的計画法を行う 荷物があるフロアの中で最も上にあるフロアから１フロアずつ全ての荷物をもっていきながらおりていく そのフロアにある荷物を全て１つ下のフロアに持っていくため…
問題リンク：Twin book report | Aizu Online Judge問題概要： 日本語なので略・自分が読み落としていた文 > 加えて，本の返却期限が近いため，まずはなるべく早くすべての本を読み終えるようにしてもらう事にした つまり、読める本があるなら感想文よりもそ…
問題リンク：Stopped Watches | Aizu Online Judge問題概要： n個の時計の情報が与えられる ただ、どれが秒針でどれが分針、時針なのかはわからないし どこを基準に数えているのかも分からない 全ての時計がとりうる時間の間隔のうちもっとも短いものを出力…
問題リンク：Live Schedule | Aizu Online Judge解法： 動的計画法dp[何日目か][負担][連続してライブをした日数] := 最大利益 とする遷移の状態としては、 ・何もしない ・その場所だけでライブ ・連続してライブ の３つがあるEが0の時はそこでライブを行え…
問題リンク：Bingo | Aizu Online Judge解法： 動的計画法を行う 問題の制約より、N*Nのマスを全て異なる数で総和がSになるような状態の数を求めれば良い亊がわかるコード： #define REP(i,s,n) for(int i=s;i
問題リンク：Three-way Branch | Aizu Online Judge問題概要； H*Wのセルからなるグリッドが存在する 自分は最初セル(1,1)にいて、セル(W,H)に移動する 今いるセルの左下、下、右下に移動できる いくつかのセル上には障害物が存在しており、そのセルに移動す…
問題リンク : Hotel | Aizu Online Judge解法： 動的計画法を行う D日間にかかるホテルの費用の最小は各日にちでもっとも安いホテルを選んだときの費用の和だが、 移動回数の最小化や複数あったときに辞書順で最小のものを選びたいのでDPする配列は dp[何日…
問題リンク : Ice Maze | Aizu Online Judge問題概要： 日本語なので略解法： 反復深化で解いた氷の塊の情報をvectorで管理した 入力をとった後に氷の塊に番号を付けていき、氷の塊の分だけvectorの要素を確保する 氷の塊の番号とvectorのインデックスが対応…
問題リンク : Life Game | Aizu Online Judge問題概要： 六角のセルにウィルスが存在する １ターン毎にウィルスが存在するセルに隣接する全てのセルに今いるセルに存在するウィルスの数と同じ数のウィルスが発生する １つのセルにM以上のウィルスが存在する…
問題リンク：Swimming Jam | Aizu Online Judge問題概要： n人の人が２つのレーンを使って水泳をする 入力として人の数nとそれぞれの人が１レーンを泳ぐのにかかる時間と往復する回数が与えられる ある人が泳いでる途中で前の人に追いついてしまった場合はレ…
