AOJ

AOJ2607 Invest Master

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2607初めX円所持している。株式は1つも所持していない。N種類の株式がある。 i日目に株式jに購入すると1つの株式jを入手でき、P[i][j]だけ掛かる i日目に株式jを1つ売却するとP[i][j]円入手…

AOJ1161 Verbal Arithmetic

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1161覆面算を解け。ただし、以下の条件を満たす。 異なる文字で同じ値が重複してはならない 複数桁ある数の時、先頭の数字は0であってはならない

AOJ2426 Treasure Hunt

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2426N個の宝の座標が与えられる。座標には重複も含む。 M個のクエリが与えられる。各クエリは長方形領域を示す。 クエリに対し、領域に含まれる宝の数を答えよ。 長方形領域は境界を含む。点…

AOJ2131 Pi is Three

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2131π-R 有理数Pの既約分数について考える。 分母を最小化して、同じ分母であれば、πにできるだけ近い値を求めよ。 R

AOJ2684 RLE Replacement

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2684ランレングス符号化された文字列A, B, Cが与えられる。 Aのうち、はじめてBが生じる場所をCに置換せよ。A, B, Cの各文字と数字のペアの数

AOJ2555 Everlasting Zero

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2555N個のスキルがあり、それぞれについて初めの経験値は0である。 あるコマンドを覚えるためには、指定された複数のスキルの経験値が条件を満たす必要がある。 条件は、スキルi >= 3, スキ…

AOJ2176 For the Peace

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2176N個の国がある。各々の国に対して、逆時系列順に新たに作ったミサイルの強さがM[i]個ずつ与えられる。 国力とは、持っているミサイルの強さの和で定義される。 ミサイルを破棄するには、…

AOJ2640 Prowler

AOJ

問題 N*Mのグリッドが与えられる。壁に右手を添えながらゴールに到達することが出来るか? 到達可能なとき、ゴールに到達するまでに踏んだマスの数を答えよ。 N, M

AOJ2224 Save your cats

AOJ

問題 N本の柱の座標が与えられ、柱と柱を繋ぐM個の壁が与えられる。 壁で囲まれた領域内に猫がいる。壁を壊して猫を助けたい。 壁を壊すコストは、壁の長さだけ掛かる。壁同士は交差しない。 すべての猫を助けるために壁を壊すコストを求めよ。

AOJ2566 Restore Calculation

AOJ

問題 3つのN桁の数A, B, Cがある。いくつかの数字は'?'となっている。 '?'には、数字の先頭であれば'1'から'9'が入り、先頭でなければ'0'から'9'が入る。 A + B = C が成立するパターン数を求めよ。(MOD 10^9+7)

AOJ1056 Ben Toh

AOJ

問題 初日、半額弁当は100%入手できる。2日目は50%の確率で入手できる。 3日目は、2日目で入手出来たのなら、25%の確率で入手できる。 2日目で入手できなかったなら、再び100%の確率で入手できるようになる。 以下このアルゴリズムをN日まで繰り返したと…

AOJ2534 Dictionary

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534アルファベットに対応させることのできる言語が発見されている。 単語が改行区切りで順に書かれている。辞書順が定義されている可能性のある言語かどうか判定せよ。

AOJ2178 Futon

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534N個の2*1マスの布団を広大なグリッド上に並べる。各々左上の座標と、縦と横のどちらの向きで配置するかの情報が与えられている。別の人の頭と足が隣り合わせになってしまう箇所が1つで…

AOJ2299 Tiles are Colorful

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2299以下のようなH*Wのグリッドがある。 ..A....... .......B.. .......... ..B....... ..A.CC.... ある空のマスから上下左右4方向に初めてぶつかったアルファベットに2つの同じ文字であれば…

AOJ2320 Infinity Maze

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2320以下の様なH*Wのグリッドが与えられる ####. ..... .#S#. ...#. #.##."NEWS"の何れかのアルファベットがおいてある場所を初期位置とする。 真っすぐ進み、壁にぶち当たったら90度回転す…

AOJ2241 Usaneko Matrix

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=22412人でN*Nのビンゴゲームを行う。マスの各値は互いに異なり、コールされる値もまた互いに異なる。 勝つ条件として、うさぎはU以上の列を揃える必要があり、ねこはV以上の列を揃える必要が…

AOJ1512 Smartphone Game

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1512パズドラを1回だけシミュレートせよ。ただし、移動可能回数は高々N回までである。 0 グリッドは5*5

AOJ1190 Anchored Balloon

AOJ

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1190&lang=jpZ=0の平面上にN個の整数座標が与えられる。各々に杭を打ち、それぞれ異なる長さのロープで一つのバルーンに繋ぐ。 上空に飛ばしたとき、バルーンの上昇する最大の高さを求めよ。…

AOJ1031 Simple GUI Application

AOJ

問題 指定された記法のXMLを解析してGUIオブジェクトの配置状況を読み取り、クリックした領域と子オブジェクトの数を答えよ。解説 地道にやる。sscanfを使って、','区切りの数値を読み取ったり、タグを正規表現で読み取るのが賢いらしい。 自分はまだ荒削り…

AOJ2363 Unequal Dice

AOJ

問題 多面体サイコロがあり、幾つかの面は数字が書かれていない場合もある。 サイコロを振ったとき、数字が書かれていない面が表になった場合、数字の面になるまでサイコロを振る。 多面体サイコロは、数字が書かれている面に対して、その数字とその面の出る…

AOJ2333 My friends are small

AOJ

問題 重さのみのナップザック問題が与えられる。 任意の順番で品物を詰めることができるが、まだ品物が入る場合は出来る限り詰めなければならない。 N個の品物を容量Wのナップザックに入れる組み合わせの数を答えよ。

AOJ2301 Sleeping Time

AOJ

解答 K = 30 までで O(2^K) なので、多少枝刈りすれば通るだろうと思っていたが TLE がなかなか取れなかった。決め手は solve() 関数内の 2行目の枝刈り。条件式を満たすとき今の確率を P倍 と (1-P)倍 に分割する必要がなくなる。コメントアウトしてある条…

AOJ1196 Bridge Removal

AOJ

#include <iostream> #include <vector> #include <algorithm> #include <set> using namespace std; struct Edge { int to, cost; }; typedef vector<Edge> Edges; typedef vector<Edges> Graph; typedef long long ll; typedef pair<ll, ll> Pll; int N; int p[810]; // p[0] no use ll allcost, delcost; Graph G;</ll,></edges></edge></set></algorithm></vector></iostream>…

AOJ2219 THE BYDOLM@STER

AOJ

解法 個数制限なしナップサック問題を3パラメータそれぞれについて解く。割と問題文読解ゲー。 配列を再利用すると、0-1ナップサックと個数制限なしナップサックの違いはループの方向のみとなる(蟻本) という意味を確認しておく。0-1の場合は、j のループ…

AOJ2200 Mr.Rito Post Office

AOJ

解法 先にワーシャルフロイドで陸路経由と海路経由それぞれについて全点対最短路を解く。あとは dp[配達し終えたノード][ボートの位置] = はじめの位置からの最短距離 としたDPを書けば良い。WarshallFloyd+DPでなく、普通にダイクストラでやろうとすると ML…

AOJ2011 Gather the Maps!

AOJ

解法 setのDPをする。任意の二人を遭遇させるたび、持っている断片を集める。それを日数でループする。 一度に多数の人間の断片が集積すること、また一度はぐれた人に二度以上合う事によりさらに集められる事を考えると良い。日数と人の番号の表で、それぞれ…

AOJ2255 6/2(1+2)

AOJ

解法 区間DP。計算結果の重複を防ぐので set memo[l][r]; で計算結果を管理する。事前に括弧付けされたものは一つの項としてまとめなければならないので、文字列[l,r) が、完全に "(expr)" の形で表せる場合を捉える必要がある。(str[l] = '(', str[r-1] = …

AOJ1150 Cliff Climbing

AOJ

解法 拡張グラフにおけるダイクストラを書くだけ。 ポイントは 座標に対応したノード番号のナンバリング(座標としてxとyの2要素持つよりキューに入れるとき都合が良い) ノード番号から座標への変換 左右の足を交互に移動 -> グラフの要素を2倍にする 複数…

AOJ1140 Cleaning Robot

AOJ

解法 BFSして、'o' と '*' 間に張ることの出来る全てのエッジのコストを求める。汚れたタイル '*' は高々10個なので、ロボットの位置のノードを含めて最大11個のノードで巡回セールスマン問題を解く。反省 コード量が多くなってきたときに、マップなどのコン…

AOJ1168 ぐらぐら

AOJ

未実装