問題文 ワーシャルフロイド法で解ける問題でした。 #include <iostream> #include <algorithm> using namespace std; const int INF = 1e+9; int main(){ int n,m; while( cin >> n >> m , n||m ){ int d[2][101][101]; for(int i=0 ; i < 101 ; i++ ){ for(int j=0 ; j < 101 ; j</algorithm></iostream>…

問題文 ワーシャルフロイド法で解くことができる問題でした。 #include <iostream> #include <algorithm> using namespace std; const int INF = 1e+9; int main(){ int n; while( cin >> n , n ){ int d[11][11], v=0, s[11]={0}; for(int i=0 ; i < 11 ; i++ ){ for(int j=0 ; j </algorithm></iostream>…

問題文 ワーシャルフロイド法で解くことができる問題でした。 ダイクストラ法でも解けるようですが、行きと帰りの最小コストだけ分かればよいのでワーシャルフロイド法を使うほうが楽なようです。(ノード数も少ない) #include <cstdio> #include <algorithm> using namespace st</algorithm></cstdio>…

問題文 1 #include <iostream> #include <algorithm> using namespace std; int main(){ int z; while( cin >> z , z ){ long long int ans = -1; for(long long int x = 1 ; x*x*x < z*z*z ; x++ ){ for(long long int y=1 ; x*x*x + y*y*y < z*z*z ; y++ ){ long long int s = z</algorithm></iostream>…

問題文 麻雀の役判定のような問題です。最初に2つ同じ数字のペアを決め、のこりを全探索で３個の数字の組み合わせ４つになるか調べるようにしました。同じ数字は4つまでしか使えないことに注意しましょう。 #include <iostream> #include <vector> #include <string> using namespace s</string></vector></iostream>…

自分のためのAOJの問題の解法ごとのジャンル分けメモです。二番煎じっぽくて緑の人に怒られそうな記事ですがお許しください。 最適な解法とは限りません。難易度順ではなく問題番号順に並んでいます。思い出したときに随時追加します。ソートする問題Problem…

問題文 再帰を使って深さ優先探索(DFS)で解くとよいと思います。特に気をつけることはないと思います。 #include <iostream> #include <string> using namespace std; string f[8]; int dx[12] = {0,0,0,-1,-2,-3,0,0,0,1,2,3}; int dy[12] = {-1,-2,-3,0,0,0,1,2,3,0,0,0}; vo</string></iostream>…

問題文 各チーム毎に勝ち点をそれぞれ勝(3点)、負(0点)、引分(1点)で計算し、勝点の高いチームから順にチーム名と勝点を出力します。 勝点が同じときは入力の順に出力することに気をつけてソートしましょう。 #include <iostream> #include <vector> #include <map> #include <string> #incl</string></map></vector></iostream>…

問題文 入力した数値に対応するようなそろばんの配置を出力します。 あらかじめ数字(0-9)ごとの文字列のテーブルをつくっておいて各桁ごとに数字を見ていけばよい思います。 #include <iostream> #include <string> using namespace std; string f[10] = { "* = ****", "* =* *</string></iostream>…

問題文 縦横斜めに連続して1が並ぶ列のうち列の長さが最大のものを出力します。全探索するだけでよいようです。 #include <iostream> #include <string> #include <algorithm> using namespace std; int dx[] = {1,0,1,-1}; int dy[] = {0,1,1,1}; int main(){ int n; while( cin >> n , n</algorithm></string></iostream>…

問題文 4種目の合計タイムの合計タイムが1番小さいチームと2番目に小さいチームと2番目に大きいチームのチーム番号を出力します。 ソートするとよいと思います。 #include <iostream> #include <vector> #include <map> #include <algorithm> using namespace std; typedef pair<int,int> P; int main(){</int,int></algorithm></map></vector></iostream>…

問題文 円に内接する2つの多角形の面積の大きさを比較する問題です。 三角形の面積は(半径)*(半径)*sinθ÷2で計算できます。 面積の大きさの比較だけなので半径を1として(÷2)を省略しても問題ないでしょう。 #include <iostream> #include <vector> #include <cmath> using namespace s</cmath></vector></iostream>…

問題文 BMIが22に一番近い人の番号を出力する問題です。 入力では身長が[cm]で与えられるので[m]に変換するのを忘れないようにしましょう。 #include <iostream> #include <cmath> #include <algorithm> using namespace std; int main(){ int n; while( cin >> n , n ){ double BMI[1000</algorithm></cmath></iostream>…

問題文 問題文の通りに文字列を変換します。入力した文字列の長さが奇数か変換表にないときは"NA"を出力します。 #include <iostream> #include <string> using namespace std; char table[6][5] = { {'a','b','c','d','e'}, {'f','g','h','i','j'}, {'k','l','m','n','o'}, {'</string></iostream>…

問題文 スタートからゴールまでの経路が何通りあるか調べる問題です。典型的な動的計画法で解くことができます。 動的計画法については最強最速アルゴリズマー養成講座のアルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だったの説明がわ…

問題文 入力が多いので面倒ですが落ち着いて考えるとそんなに難しくありません。 L:作物の名前 P:作物の値段 A:種から芽が出るまでの時間 B:芽が出てから若葉が出るまでの時間 C:若葉が出てから葉が茂るまでの時間 D:葉が茂ってから花が咲くまでの時間 E:花…

問題文 DPで解ける問題です。 DP[数列のi番目][途中の計算結果]：組み合わせ数 となるように計算します。 JOI君は途中の計算結果が0以上20以下のものしか扱えないようです。DP[n-2][ a[n-1] ]が解となります。 #include <iostream> using namespace std; int main(){ i</iostream>…

問題文 DPで解けます。i段目の上がり方がA[i]通りあるとすると i段目に来るためには1つ下の段か、2つ下の段か、3つ下の段から来るはずなので A[i]はA[i-1]+A[i-2]+A[i-3]で求まります。解は(A[n]/365/10)+1を出力します。 #include <iostream> using namespace std; in</iostream>…

問題文 図形はひとつなので普通に実装しただけです。 #include <iostream> #include <cstdio> using namespace std; int main(){ int ax, ay; char f[12][12]; bool flag = false; for(int y=0 ; y<12 ; y++){ for(int x=0 ; x<12 ; x++){ f[y][x] = 0; } } while( 1 ){ for(in</cstdio></iostream>…

問題文 線分ACと直線BD，あるいは直線ACと線分BDのどちらかが交差していない場合は、 凹みのある四角形です。 線分や縁の交差判定はよく使うので慣れておきたいものです。 #include <complex> #include <cstdio> #include <cmath> using namespace std; // 点座標を型とする typedef </cmath></cstdio></complex>…

問題文 ２つの列車がすれ違う区間を出力する問題です。 同時に２つの列車が出るので、どちらの列車も出発してからすれ違うまでの時間は同じはずです。 また速度が与えられているのでどこですれ違うかわかるはずです。 ただし、ちょうど駅のところですれ違う…

問題文 適当に試行錯誤してAcceptしました。無駄な処理を含んでいる気がします。 #include <iostream> #include <stack> #include <vector> using namespace std; int main(){ int n, a; vector<int> A; cin >> n; for(int i=0 ; i<n ; i++){ A.clear(); for(int j=0 ; j<10 ; j++){ cin >> a; A.push_back(a); } stack<int> B, C; bool flag = true; B.</int></n></int></vector></stack></iostream>…

問題文 AOJ - Problem 0003 : Is it a Right Triangle? と同じような問題です。 ピタゴラスの定理を使うだけの簡単な問題です。 #include <cstdio> using namespace std; int main(){ int a, b, c, ans1=0, ans2=0; while( scanf("%d,%d,%d", &a,&b,&c) != EOF ){ if</cstdio>…

問題文 入力aに対し、aを超えない最大の2nをaから引いていくとうまくいくと思います。 #include <iostream> #include <vector> using namespace std; int main(){ int w, g[10]; vector<int> ans; for(int i=0,j=1 ; j<=512 ; j*=2, i++){ g[i] = j; } while( cin >> w ){ ans.clear</int></vector></iostream>…

問題文 0 から 9 の数字から異なる n 個の数を取り出して合計が s となる組み合わせの数を出力する問題です。 0 から 9 の数字から異なる n 個の数を取り出す組み合わせもれなく列挙するといいと思います。「C言語による最新アルゴリズム辞典」を参考にして…

問題文 AOJ - Problem 0028 : の単語バージョンです。出現回数の最も多い単語を出力します。 C++ならを使って、単語と出現回数をペアで保持すると楽だと思いました。 #include <iostream> #include <string> #include <map> #include <vector> using namespace std; int main(){ map<string, int> word; v</string,></vector></map></string></iostream>…

問題文 入力された整数値のうち出現頻度が多いものを出力する問題です。 数字ごとに何回入力されたかを配列などに保持して最後にその出現回数の最大のものを出力するようにします。 複数あるときは、昇順にソートしてから複数の数字を出力します。 #include <iostream></iostream>…

問題文 1月1日から順に1日ずつ増やして曜日を判定するようにしました。 ツェラーの公式という西暦、月、日から曜日を求める有名な公式があるのでそちらを使った方がよかったかもしれません。 #include <iostream> #include <string> using namespace std; int main(){ string w</string></iostream>…

問題文 素直に実装するだけです。気を付けることは特になかった気がします。 #include <stdio.h> int main(){ int map[10][10],ink,x,y,max=0,count=0; int dx[] = { 0, 0,-1, 1,-1,-1, 1, 1, 0, 0,-2, 2}; int dy[] = {-1, 1, 0, 0,-1, 1,-1, 1,-2, 2, 0, 0}; for(in</stdio.h>…

問題文 有名なゲームのヒットアンドブローですね。学校が終わった後少し時間があったとき 自分で遊ぶ用のヒットアンドブローを暇つぶしにコーディングしたりしてたので、 わりとすぐに解けました。 位置も数字も一致している数はblowに含まれないので気をつ…