AOJ
問題 M and A | Aizu Online Judge 方針 SとTの部分文字列を交互に繋げてSを作ることができるか調べる. Sの部分文字列は自明にSに含まれているので, Tの部分文字列を考える. Tの先頭から順に探索し, 部分文字列であるかを試す. （Sの偶数番目と奇数番目をと…
問題 Calling Extraterrestrial Intelligence Again | Aizu Online Judge 方針 とを満たすp, qを求める. (p, qは素数) エラトステネスの篩を使って素数を生成する. それらを使ってpとqの組を試す. qを求めるループの条件式は, という不等式から, とした. コ…
問題 Lagrange's Four-Square Theorem | Aizu Online Judge 方針 全部探索する. コード #include <iostream> using namespace std; signed main(){ int n; while(cin >> n, n){ int cnt = 0; for(int i = 1 ; i * i <= n ; i++){ if(i*i == n) cnt++; for(int j = i ; </iostream>…
問題 Calender Colors | Aizu Online Judge 方針 N個のLABカラーが与えられる. そこからM個取り出し, 要素それぞれの差の二乗の和を求める. その和の最大値が答え. であることから全探索しても良さそう. M個取り出すときにbitを使うと便利っぽい. コード #in…
問題 Counting Sort | Aizu Online Judge 方針 計数ソート（バケットソート）をしよう. アルゴリズムは問題をそのまま実装. コード #include<bits/stdc++.h> #define rep(i, n) REP(i, 0, n) #define REP(i, a, n) for(int i = a ; i < (int)n ; i++) using namespace std; </bits/stdc++.h>…
問題 Grey Area | Aizu Online Judge 方針 ヒストグラムを印刷するために必要なインク量を求めようという問題. vを入力する際に, 区画の最大値(imax), 頻度の最大値(hmax)を求める. hist[i] := の頻度としたとき, を計算する. 最後に0.01を足す(線とかを引く…
問題 And Then There Was One | Aizu Online Judge 方針 Josephus problemという有名な問題らしい. (ただし, ) という漸化式を解くことでで求まる. コード #include <iostream> using namespace std; int f(int n, int k){ if(n == 1) return 0; return (f(n-1, k)+k)%</iostream>…
問題 Era Name | Aizu Online Judge 方針 EraBasedYearとWesternYearが入力し, それらをs(start), e(end)という変数に代入. queryが ]にはいってるとき, が答え. 当てはまらない時はUnknownとなる. コード #include <iostream> #include <vector> #include <algorithm> using namespace st</algorithm></vector></iostream>…
問題 連鎖行列積 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 行列が5個与えられた時, 計算の順序は 1. 2. 3. など様々な順序がある. すべてのパターンを試すアルゴリズムでは, となってしまうため, これよりも計算効率の良いアルゴリズムを考える…
問題 Bamboo Blossoms | Aizu Online Judge 方針 エラトステネスの篩的に消していく. Nが0になったときのiが答え. コード #include <iostream> #include <cmath> using namespace std; #define MAX 7368791 int main(){ int m, n; bool flag[MAX]; while(cin >> m >> n, m||n)</cmath></iostream>…
問題 Airport Codes | Aizu Online Judge 方針 1文字目と母音の直後の文字を順に連結した文字列を作る. k文字未満ならその文字列, k文字以上なら取り出した文字列の先頭からk文字分をコードとする. kを1から50まですべて試す(試しても間に合う制約なので) コ…
問題 Let's Solve Geometric Problems | Aizu Online Judge 方針 b進数k桁の値は以下のように表すことができる. 上の式を変換すると,となることがわかる. 上記の式の形に変換したときのbが答え. コード #include <iostream> #include <cmath> #include <utility> #include <vector> #include <algorithm> u</algorithm></vector></utility></cmath></iostream>…
問題 Binary Trees | Aizu Online Judge 方針 二分木を作ろう. コード #include <iostream> using namespace std; struct Node{ int parent, left, right; }; int n; Node T[30]; int D[30], H[30]; void depth(int u, int d){ if(u == -1) return; D[u] = d; depth(T[</iostream>…
問題 A Way to Invite Friends | Aizu Online Judge 方針1 配列の[a, b]を++していく. 配列fをf[i]:=i人誘う時行くことができる友達の数とする. i-1（自分を抜いた数）誘うときに, i - 1 <= f[i]となればi-1人誘えるということになる. 方針2 aのときにf[a]を…
問題 連鎖消滅パズル | Aizu Online Judge 方針 横に3つ以上連鎖している箇所は消すことができる. 消えた部分には, 上にある石が空きを埋めるように落ちてくる. すべての石を落とした後に消滅の条件をみたすようなものがあればまた繰り返す. 上の通りにシミ…
問題 反転数 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 反転数を求める問題. バブルソートの要領で探すとになってTLEするので効率よく探す必要がある. タイトルの通り, 分割統治法（マージソート）を活用することででカウントすることができる. …
問題 Brave Force Story | Aizu Online Judge 方針 BFSをする. その際にそこにたどり着ける距離を保存し, 最後にたどり着けたマスの数を数える. 普通に探索するとインデックスが負になって悲しくなるので, 適当に座標をずらす. コード #include <algorithm> #include <iostream> #</iostream></algorithm>…
問題 Merge Sort | Aizu Online Judge 方針 マージソートをします. INFを適当においたせいで無事に死んだ コード #include <iostream> #include <cstdio> using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,a,n) for(int i = a ; i < (int)n ; i++) #define MAX</cstdio></iostream>…
問題 Earth Invasion Diary of Miyabi-sensei | Aizu Online Judge 方針 天秤に乗せるものをA, B, Cという3つに分け, AとBを天秤に載せたとき, 釣り合っているならばCにオリジナルが載っているし, どちらかに傾いたら傾いたグループにオリジナルが存在するこ…
問題 割り当て | アルゴリズムとデータ構造 | Aizu Online Judge 方針 積載量の最小値を求めたい. 0から順にを試し, そのPでk台のトラックを使いすべて積むことができたならそれが答えになる. しかし, 順番に調べていくとのアルゴリズムになって終わらなさそ…
問題 探索 3 | アルゴリズムとデータ構造 | Aizu Online Judge 方針 mapを実装する問題 STLのmap使えば簡単にできるんだけども, 「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」を見つつ愚直に実装. ハッシュ関数は「ダブルハッシュをつ…
問題 Moonlight Farm | Aizu Online Judge 方針 入力が色々あるので1度図に起こして考えてみると非常に簡単 収入効率の分母は, 分子はとなるのでこれをクラスにいれてソートをするだけ. 効率が同じ場合は名前を辞書順で表示する. ソース #include <iostream> #include <vector></vector></iostream>…
問題 Surrounding Area | Aizu Online Judge 方針 白い杭から探索した場合には黒い杭, 黒い杭から探索した場合は白い杭に当たるまでひたすら探索 黒だけで塗りつぶされた場所と白だけで塗りつぶされた場所を数える. コード #include <iostream> #include <utility> using namesp</utility></iostream>…
問題 Osaki | Aizu Online Judge 方針 与えられた時刻はすべて秒に変換する. pair<int, int>のfirstを時間, secondを出発するときは1, 到着したときは-1として保持 時刻順にソートする. 0～vec.size()まで調べ, 出発したときはカウンタを1, 到着したときは-1していきそ</int,>…
問題 Analyzing Login/Logout Records | Aizu Online Judge 方針 PCの番号nと生徒の番号mをキーとしたmapを使って計算する. ログには必ずログインとログアウトの記録が存在し, 時刻昇順で入力がされることからk番目をstart, k+1番目をend(ただしkは偶数)とし…
問題 Monday-Saturday Prime Factors | Aizu Online Judge 方針 月曜土曜数 a が月曜土曜数 b の月曜土曜約数であるための必要十分条件は, a が b の普通の意味の約数であること. 「エラトステネスの篩」の要領で月曜土曜素数を生成して試す. 出力のフォーマ…
問題 Amazing Mazes | Aizu Online Judge 方針 入力フォーマットが特殊な問題. （ここを理解するのに時間を取られる） 与えられた入力からフィールドを生成して, それに対してBFSする. BFSはいいとしてフィールドの生成めちゃくちゃ手こずった. kyuridenamid…
問題 Infected Computer | Aizu Online Judge 方針 与えられたデータをtで昇順ソートする. あとはdとsの値を見てフラグにチェックをいれていき, カウントする. コード #include <iostream> #include <algorithm> using namespace std; #define LOG_MAX 20000 #define N_MAX 20000 </algorithm></iostream>…
問題 Best Matched Pair | Aizu Online Judge 方針 全通り試す コード #include <iostream> using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,a,n) for(int i = a ; i < (int)n ; i++) int n; int a[1001]; bool check(int num){ int prev = num % 10;</iostream>…
問題 Koto Municipal Subway | Aizu Online Judge 方針 データセットの制約を見た上で全通り試すことにした. コード #include <iostream> #include <algorithm> #include <cmath> #include <cstdio> using namespace std; signed main(){ int D, E; while(scanf("%d %d", &D, &E), D || E){ doubl</cstdio></cmath></algorithm></iostream>…
