Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

AOJ

AOJ 2419 Acrophobia

Cheeseに似てる問題。 巻物が高々5個しかないのでcost[100][100][1 基本的にはBFSしていけばいいがコストが均一でないので初めに見つけたものが最適では ない可能性があるので、現在よりもよいコストで行けるのが見つかったらそこからまた 探索していけばよ…

AOJ 1179-1182

AOJ1179から1182までを解きました(先日のICPCの問題) 1179 Millennium やるだけ。 xxxx/yy/zzから1000/01/01までの日数を求める。 ただし1年は10ヶ月で、うるう年もどき(mod 3 == 0)だと全ての月が20日、 そうでない場合は20と19が交互。(1月は20日) 1000/01…

AOJ 2353:Four Arithmetic Operations

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=404152 方針 制約が大きい…JavaならBigIntegerを使えばよいかもしれない。 2^32より大きいmodを使うとlong longでもoverflowする可能性があるので 10^5((10^5)^2 >= 10^9.6≒2^32)程度のmodを素…

AOJ 2232:Space-Time Sugoroku Road

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2332 ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=398012 方針 0のマスからはサイコロを振れるので+1〜+6のノードへedgeを張り、 それ以外は書いてある通りにedgeを張る。…

AOJ 2364: Lucky Dip

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=391002 方針 2 0 >10^9で8秒なら間に合うかもしれない…? しかし、Nがある値以上ならば必ず到達でき、それより小さければ到達できないので 二分探索をすることができる。 >O(WHlogN)で充分間に…

AOJ 2254: Fastest Route

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=390527 方針 dp[i] := (ビット表記で)iまでクリアしたときの所要時間の最小値とすればよい。 TSPと違うのは「いまどこにいるか」は関係ないので1次元配列で済む。 あとは再帰内で 次に(j-thス…

AOJ2253:Brave Force Story

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=390516 方針 ハニカム構造の隣接は図より int dx[6] = {1,1,0,-1,-1,0}; int dy[6] = {0,1,1,0,-1,-1};とすればいい。 あとは制約が小さいので各ターンごとに 既にvisitedな場所からいける場所…

AOJ0145: Cards

Vol.12がだんだんきつくなってきたのでここらでVol.01の残りを掃除でもしようかと。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0145 ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=385224 方針 solve(a,b):=a番目の山…

AOJ1126: The Secret Number

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382916 方針 DP。 dp[i][j] := (i-1,j-1)を末尾とする最大の文字列 dp[i][j] = "" ((i,j)がアルファベット) dp[i][j] = max(dp[i-1][j] + (i,j), dp[i][j-1] + (i,j)) (左から来るか、上から来…

AOJ1277:Minimal Backgammon

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382422 方針 典型的なDP dp[i][j] := i回振った後にjマス目にいる確率を計算していけばよい。n番のマスに到達した場合それ以上の移動はせず、 答えとしては を出力すればよい。

AOJ1275:And Then There Was One

ソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=382200 解き方 継子立てのバリエーション。(ヨセフスの問題とも言うらしい) http://ja.wikipedia.org/wiki/%E3%81%BE%E3%81%BE%E3%81%93%E7%AB%8B%E3%81%A61,2,...,nのn人を円形にclockwiseに…

AOJ 1241:Lagrange's Four-Square Theorem

AOJ上でソースを公開できるようになったのでそのテストも兼ねてソース http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=376363与えられたN(1 2^15以下の平方数は181個しかないのでDPで dp[i][j][k] := i番目の平方数まででj個使った和がkになるような…

AOJ1100,1104,1132,1144

いくつか通しました 1100 1132 幾何。幾何問題はcomplexを使うと非常に楽です。 1104 実装ゲー 1144 DFS。 10回の移動までなので最大でも4^10*20(盤面の広さ)なので間に合う。 結構実装戸惑った。しょぼい。

AOJ1109:Fermat's Last Theorem

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1109 問題文通り。与えられたzについて z^3-max{x^3 + y^3| x>0, y>0, x^3 + y^3 を計算する。 方針 xを決めて条件を満たす最大のyを二分探索で求めて計算する。 二分探索は割とすぐ思いつけ…

AOJ0232:Life Game

久々にDPを全部自力で解けた。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 方針 dp[i][j] := i-thマスに得点jで来る確率 としてDP。 マスに止まる確率のみだと期待値が計算できないので、得点をDPテーブルに 入れるという発想が出…

AOJ0230:Ninja Climbing

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230 方針 nが割と小さいのでDFSで間に合う。 これまでの最小値を保持しておいてそれが更新される場合 そこから再帰的に最小値を更新していく。グラフを作って最短経路問題にも落とせる気が…

AOJ0155:Spider Jin

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155 方針 1 すべてのビル間の距離を計算して50以下ならedgeを張ってdijkstraすればよい。前々からdijkstraは書いておきたいなと思いつつも 下手なライブラリ書いて使っていくことにためらい…

AOJ0203:A New Plan of Aizu Ski Resort

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0203 方針 配るDP。貰うDPでも書けなくはないと思う。 下から二段目にジャンプ台がある場合に注意。以下ソースコード #include <iostream> #include <cstring> #include <algorithm> using namespace std; int dw[3] = {-1,</algorithm></cstring></iostream>…

AOJ0221:FizzBuzz

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221 方針 シミュレートする。 (Fizz || Buzz || FizzBuzz)でないときの処理を自前tointに任せていると文字列のときにうまくいかないのに気づかず数回WAした。基本的にはやるだけ。以下ソー…

AOJ0181:Persistence

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0181 方針 本棚の幅で二分探索。 あとはn冊の本を詰めるシミュレートをして、lb/ubを更新していけばよい。 判定は必要な段数のみでなく、本の厚みの最大値 計算量はO(n*log(本棚の最大値))だ…

AOJ0191:Baby Tree

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0191 方針 i回目に選ぶものを決めるために影響するのはi-1回目に何を選んだかのみで、それまでにどういう選び方をしたかは関係ないので dp[i][j] := i回目にjを選んだ場合の最大の長さ とし…

AOJ0120: Patisserie

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0120 方針 左から円を並べていくと考えると、右端の円の大きさと追加する円の大きさによって増加する長さが変わることが解る。n dp[state][back] := state使った右端がbackであるものの長さ…

AOJ1082:11224111122411

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1082 元ネタが解りません… 方針 配る系のDP。 5種類音のある子音列はループするまでは あ->ああ->あああ あい ->い ->いあ ->う というように、最後にa音を1文字つけるor最後の文字を1つ進め…

AOJ1079: Cosmic Market

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1079 方針 同一のマスに対するクエリは最後のものが有効であることに着目して クエリを逆順に見ていけばよい。逆順に見て既にクエリを処理したことがあればそのクエリは無視、 そうでなけれ…

AOJ1078:SAT-EN-3

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1078 佐天さん。 方針 加法標準形のSATなので1clauseでもsatisfiableなら全体としてsatisfiableである。 文字処理が若干めんどくさい。 mapでどの文字リテラルがtrueかfalseのどちらのassign…

AOJ1077:The Great Summer Contest

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1077 方針 問題は6種類あるように見えて実は3種類しかない。 Math or DP -> MD Greedy or Graph -> GG Geometry or Other -> GO とすると、 MD,GG,GOのコンテストを3回開くのはそれぞれ3問の…

AOJ1076:Time Manipulation

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1076 [1,n]の整数のうちa_k(1 方針 包除原理。m 計算するものは選んだ数の公倍数の和とその個数。 公倍数の個数は n / lcm, 公倍数の和はlcm * (n / lcm) * ((n/lcm)+1)。nが大きいのでlong …

AOJ 1056 Ben Toh

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056 方針 DP。誤差制限が緩いので dp[n][k] := n回目にゲットできる確率が2^-kである確率 として dp[i+1][0] += dp[i][k] * (1 - pow(0.5,k)) //取れなかったら次の確率は1 dp[i+1][k+1] …

AOJ 1020 Cleaning Robot

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1020 方針 dp[second][pos]で i+1秒後に次の移動先next_posに移動できるなら dp[i+1][next_pos] += dp[i][pos] * 0.25; そうでなければ dp[i+1][pos] += dp[i][pos] * 0.25; とすればよい…