AOJ

AOJ 2026 Divisor is the Conqueror

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026) N枚のカードがあったそれを一枚ずつ出していく。出せるのは今までに出した、カードの総和の約数だけ。 解法 DFSで解く。普通に解いても無理だった。逆から解くとできるんだって コー…

AOJ 1218 Push!!

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1218) 図だけでもなんとか分かるよね。ゴールまで最短で何回動かせばいいか 解法 BFSで動かしていきます。押す方向と逆の方向に人が立てるか、現在いるところからそこにいくことができるか…

AOJ 1103 Board Arrangements for Concentration Games

問題 AからHのカードを並べてく、カードのセットに相対的な位置だけでカウントしていくから AとBのセットをかえても同じ 解法 DFSで解きます。 コード int board[4][4]; int dy[4], dx[4]; int dfs(int n){ if(n >= 8) return 1; int res = 0; int y, x; rep…

AOJ 0169 Blackjack

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0169) 解法 DFSが楽。あとは1以外を全部足してから1をどうするかってやる。 コード DFS int a[512], p; int dfs(int n, int c){ if(n > 21) return 0; if(c == p) return n; if(a[c] == 1) …

AOJ 1210 Die Game

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1210) top、north、westはそれぞれ1,2,3とする さいころを指示通りに転がした時、topに来る面は何か? 解法 シュミレーション問題です。 コード int n, top, west, north; string op; int m…

AOJ 0199 Chairs Where Demanding People Sit

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0199。 解法 シュミレーション問題です。 Cの座る条件をいくつか見逃していてWA連発。 『How to Solve It』に問題を理解することって書いてあったのに。 ちゃんと問題を読むようにします コ…

AOJ 0178 TETORIS

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0178。 解法 シュミレーション問題です。 指示通りに処理すればできる高さは十分にとっておかないとRUNTIME ERROR吐かれる コード int t[UNDER+10][5], n; int count(){ int res = 0; rep(i,…

AOJ 1117 Missing Numbers

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1117。 所々、虫食いになってる表が与えられるからそれを埋める。 解法 一カ所だけ?の行(列)なら埋められる。 コード int p, s; char row[10]; int a[128][128], b[128][128]; int main(){ b…

AOJ 1248 The Balance

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1248。 2つの重りと計りたい分量が与えられる。それぞれ重りをいくつ使えば計れるか? 重りはより少なく、軽いものを選ぶ。 解法 aの数、xがでれば、yは一つに定まる。xに関するループを回…

AOJ 0165 Lottery

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0165。 解法 p-m以上p+m以下の素数数えていく。素数を用意する配列にはa[i]、i以下の素数の数を累積和で記録しておかないとTLEになる コード int p[MAX_P], n, sum[MAX_P]; int main(){ p[0]…

AOJ 1006 Boring Commercials

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1006。 チャンネル数とCMの時間が与えられる。CMを見ずに何分間テレビを見れるか。 解法 実装するだけ コード int n, p, q, m, s, e; int t[100000]; int main(){ while(scanf("%d%d%d", &n,…

AOJ 1214 Walking Ant

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1214。 antが自分の巣に帰る最短距離を求める。四方向に一つ進むのに1timeかかる。初期の体力が6で1timeごとに1ずつ減っていく、食べ物のマスを通ると体力が6になる。 解法 食べ物は2回以上…

AOJ 0156 Moats around the Castle

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0156。 解法 天守閣からBFS、複数続いている堀をその度にカウントしてWAを出していた。 コード nt dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0}; int main(){ int n, m, i, j, d, res; while(scanf…

AOJ 1055 Spider Jin

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155。 解法 それぞれの距離をはかり、距離が50以下のものだけでグラフを作る。 あとはダイクストラで最短距離を求めて経路復元。 上限が1000なのでO(N2)で十分だと思う。 コード double cos…

AOJ 1044 Camel Case

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1044。 解法 これもシュミレーション問題かな。たぶんそうだと思います。 与えられた文字列の記法が分かれば記法ごとに別の記法に変える。 最初は一緒くたに変換しようとしてWA出してた。 コ…

AOJ 0111 Doctor's Memorable Codes

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0111。 解法 シュミレーション問題かな コード string encode(string code){ map<char, string> m; m['A'] = "00000"; m['B'] = "00001"; m['C'] = "00010"; m['D'] = "00011"; m['E'] = "00100"; m['F'] =</char,>…

AOJ 1035 Sleeping Cats

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1035。 日本語。 解法 以前、WA出したのは何故かな。 Wの大きさの配列用意して、それぞれどの猫が寝ているか見ていけばいい。 首輪でもつけるのかな コード int a[128], i, j, k; int main()…

AOJ 1008 What Color Is The Universe

問題 |A|と配列Aが与えられる。N[i]はAに含まれるiの数。 N[i] > |A| / 2 を満たす。iを探す。 解法 実装するだけ コード int A, N[1000001]; int main(){ int a, i; while(scanf("%d", &a) && a){ memset(N, 0, sizeof(N)); rep(i, a){ scanf("%d", &A); N[…

AOJ 1084 K Cards

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1084。 日本語 解法 全探索で解けます。計算量はどれくらいなのかな。どうやって表記するのかよくわからない。 単純にループのとこだけでやるとO(n(n-1)/2(n-k))とか?こんな複雑な書き方な…

AOJ 1074 Popularity Estimation

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1074. 日本語。 解法 i秒後に何人映っているかをメモしておけば簡単。やるだけ。 計算量は*O(nm)ぐらいでいいのかな。 コード int main(){ int n, m, d; char name[256]; while(scanf("%d", …

AOJ 2014 Surrounding Area

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2014 日本語。 解法 あるマスからDFSしていって黒に到達したら、1、白に到達したら2って感じにして行く。 dfsの再帰のところを最初+=にしようとしていた コード int f[50][50], c[50][50];…

AOJ 1144 Curling 2.0

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1144&lang=jp 日本語。 解法 DFSで解く。四方向見て、進めるなら進む。盤面の外に行ったら次っていう感じでまわしてく。 コード int w, h; int board[20][20]; int dx[] = {0,-1,0,1}, dy[] …

AOJ 1045 Split Up!

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045 日本語。 解法 適当にDFSすればできる。 コード int n; int a[128]; int dfs(int p, int g, int c){ if(n == c) return abs(p-g); return min(dfs(p+a[c], g, c+1), dfs(p, g+a[c], c+1…

AOJ 2281 Swap Cipher

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2281 日本語 解法 aとbを逆から読んで復号する。 コード int main(){ int N; while(scanf("%d", &N) && N){ char mes[128]; scanf("%s", mes); int a[128], b[128]; for(int i = N - 1; i >=…

AOJ 1110 Patience

問題文 5*4の20枚のカードがある(1~5)。あるカードと同じ数字の書いてあるカードが隣接(斜めでもよい)していれば、その二つのカードを取り出す。最適な取り出し方をした時、残るカードは何枚か 解法 幅優先探索で解く。状態をメモしておかないと状態数が爆発…

AOJ 0209 Scene in a Picture

問題 日本語なので特に説明はないです。何故、数ヶ月にWAだしたのか分からない問題、放置してた。 解法 切れ端を90度ずつ回転させたのを配列に入れておいて、全探索。 O(4n2m2)ぐらいかなと思ってたけど以外に速く終わった。 コード int pic[100][100]; int …

AOJ 2503 Project Management

何のことはない、有効グラフつくってクリティカルパス求めるだけ。 ワーシャルフロイド法でもなんでも解けるんじゃないかな。 int n, m; int cost[400][400]; int main(){ scanf("%d%d", &n, &m); rep(i, n) rep(j, n) cost[i][j] = 0; int a, b, c; rep(i, …