読者です 読者をやめる 読者になる 読者になる

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

未実装

AOJ0145 Cards

AOJ

解法 重ねあわせた全体のカードの束から、2つに分ける位置を決めるように区間DPする。 元のカード束のうち2つの隣接する束を重ねるという動作を最も原子的なものとして、同様のアルゴリズムが最後まで展開されることを汲み取れれば解ける。反省 問題文を読…

AOJ2002 X-Ray Screening System

AOJ

解法を考えている途中

AOJ1001 Binary Tree Intersection And Union

AOJ

概要 二分木が入力されるので Intersect または Union して出力せよ。解法以下がBNF。 := ( , ) | ε 一つの親ノードと2つの子ノードの3つのノードについての処理を考える。つまりカンマの位置を特定することが必要なのでその方法を考える。 先頭の'('を読…

AOJ2310 Rose Garden Witch

AOJ

解法 2×2の正方形のグリッドを取り出したとき、その中央の格子点を生命体の分割の数が変わるイベント点とする。するとグリッドのパターンは分割の数が 1 増加する2つと、1 減少する2つの4パターンのみに絞られる。(以下のコードでは check() 関数にそ…

AOJ0191 Baby Tree

AOJ

解法 直前与えた肥料が何であるかが、今回に何を与えるのが最適であるかを決める。 よって、状態として「肥料を与えた回数」と「直前に与えた肥料」を持ち、成長率を最大化するDPをすればよい。 具体的には、k 日目に肥料 j を与えたときの成長率は、k-1 日…

AOJ2524 Mysterious Operator

AOJ

解法 問題の「x+y=a」という式は x-y と x+y を繋げた式。 a を string とみなして切り分ける場所を決める。切り分け方が正しいかどうかのチェックは以下で可能。 切り分けた結果、先頭に0を含まない数字になるかどうか 和より差の方が必ず小さい xとyが両方…

AOJ0153 Triangle and Circle

AOJ

解法 容易に定まる条件を持つものから決定していく。 円の中心が三角形の内側にあるかどうか調べる必要があるが、これはCCWするかそれに値するような外積の符号を見る式を書けばよい。内積で角度出してやろうとしたらうまく行かなかった。単純なミスなのか、…

AOJ0152 Bowling

AOJ

解法 問題文を読んで、やるだけ反省 ボウリングの意味を勘違いしてたので、ずっとサンプルが合わなかった。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main() { typedef pair<int, int> Pii; int N; while(cin >> N && N) { vector<Pii> SCORE(N); for(int m</pii></int,></vector></algorithm></iostream>…

AOJ0186 Aizu Chicken

AOJ

解法 地鶏を上限まで買えるだけ買った後、鶏肉の地鶏と普通の鶏との合計が足りるように地鶏を減らしながら調整する。地鶏が1匹も購入できない場合は "NA" と出力。ポイント 購入できる地鶏の数を予算から単価を整数除算することで見積もること 購入する地鶏…

AOJ0178 TETORIS

AOJ

考え中の解法 シミュレートする。1000個のブロックが落ちてくるとき最悪ケースでフィールドがどれだけうまってしまうかは 5*1000 で 5000 なので、grid[5001][5] を用意すれば十分。

AOJ0177 Distance Between Two Cities

AOJ

解法考え中 多分、球面三角法使う。二点を最短で通る円から、その中心から二点までのベクトルのなす角を求める。 なす角が分かったら、半径に角度を掛けて弧を求める。

AOJ0156 Moats around the Castle

AOJ

解法 拡張ダイクストラ。各エッジをわたるコストが0または1で、1のみではないことを考えると幅優先ではなくコストの小さいものをキューから取り出す拡張ダイクストラがいいと思うけど、多分幅優先でも出来る。問題では場外から目的地に向かうが、スタート地…

AOJ0165 Lottery

AOJ

解法 問題文が長いが、冷静に必要な部分を把握して解く。 ポイントはエラトステネスの篩をかけた後に、区間の素数の数をO(1)で求められるように累積和を取ること。つまり、サブプライム(sub-prime)は求めずに、サムプライム(sum-prime)を求めればよい(激寒…

AOJ0143 Altair and Vega

AOJ

解法1 牽牛と織姫とをつなぐ線分と、三角形の3つの線分との交差を判定しカウントする。 一回の交差のみなら "OK" それ以外の回数の交差なら "NG" と出力する。解法2 牽牛と織姫が、三角形の内部か外部かで同じ場所にいるかどうかを判定すれば良い。 例え…

AOJ2254 模擬国内2011C Fastest Route

AOJ

解法 bitDPで解く。 dp[S] := 状態Sでステージを全てクリアするのにかかる最小時間 dp[0] = 0 for S[0, 1<

AOJ2208 UTPC2010 E: The Melancholy of Thomas Right

AOJ

解法 行の赤丸の数で降順sortする。全ての列の一つの赤丸で一行を丁度全て使いきったなら正しい。それをすべての行でループする二重ループ。 このGreedyで何故一意に復元できると言えるのかはわからない。 int n, row[10000], col[10000]; bool solve() { so…

AOJ0144 Packet Transportation

AOJ

解法 BFS (or Warshall-Floyd) BFSではノードの接続を隣接行列でなくて連結リストにして解いたけどその必要はあったのだろうか。 因みにnは100以下なので、コストを1に定めて Warshall-Floyd しても解ける。この方が実装が短いし、一度最短路を求めればクエ…

AOJ0131 Doctor's Strange Particles

AOJ

解法 蟻本の反転の考え方を使う。最上部を踏むか踏まないか2^10で決め打ちし、2段目からはマスの一つ上が 1 であるなら 0 に埋めることを 9*10回 繰り返す。反転のオーダーは O(M*N*2^N)蛇足 Emacsのゲームにある 5x5 で遊んだらイメージがしっかり掴めて実…

AOJ0203 A New Plan of Aizu Ski Resort

AOJ

解法 典型の配るDP。ジャンプ後の位置に障害物がある場合を見逃さないようにする。 あと問題文に書かれているけれど、ジャンプ台に乗って Y を超えるようなケースも注意。 自分は斜めからスキー台に侵入する場合分けが面倒になりそうだと思ったので直進を0, …

AOJ0129 Hide-and-Seek Supporting System

AOJ

解法 1.先ず太郎と鬼を結ぶ線分と円の中心点との距離を求める。 線分のベクトルと線分の端点と円の中心を結ぶベクトルのなす角が鈍角なら、線分と円の中心点との距離は、鈍角になる線分の端点と円の中心点との2点間の距離に当たる。鈍角の判定は内積が負…