問題 Factorial | Aizu Online Judge nの階乗を出力せよ 方針 事前に20までの階乗を保持しておいて出力 コード #include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) long long dp[21]; int main(void){ dp[0] = 1; for(int i=1; i<2</bits/stdc++.h>…

問題 Sorting Five Numbers | Aizu Online Judge 5つの数字を降順にソートせよ 方針 さすがにやるだけ コード #include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) int a[5]; int main(void){ rep(i, 5) cin >> a[i]; sort(a, a+5, </bits/stdc++.h>…

問題 Caesar Cipher | Aizu Online Judge シーザー暗号を解読せよ。ただし文章に"this", "that", "the"のいずれかの単語が含まれていることは既知とする。 方針 "this", "that", "the"のどれかが暗号化されていそうな文字列を探して、keyを求めたあと復号化…

問題 The Secret Number | Aizu Online Judge タイルの中を右または下に進んで生成できる数字のうち最大のものを求めよ 方針 深さ優先探索で数を作っていく 普通にやったらTLEするのでC[y][x]からスタートして作れる最大の数字をmemo[y][x]に入れておく 最大…

問題 Polygonal Line Search | Aizu Online Judge 与えられた折れ線と同じ形状の折れ線の番号をすべて答えよ 方針 折れ線を(次に曲がる向き, 線分の長さ）のvectorとして保持し、テンプレートと比較する 向きは1: 右折、-1: 左折、0: 終わりとした 後ろから…

問題 Pollock's conjecture | Aizu Online Judge 与えられた数を正四面体数（n番目の正四面体数はである）の和で表すときに最小でいくつの数が必要か また奇数の正四面体数のみの和で表すときはどうか 方針 動的計画法を使う dp[n]はnを表すのに必要な最小の…

問題 Chain Disappearance Puzzle | Aizu Online Judge 横方向のみ考えるぷよぷよっぽいゲームの得点を求めよ 方針 与えられた盤面で横方向に3つ以上並んでるやつを全て-1に書き換える 各列ごとに-1を詰める -1に書き換えられる部分がなくなったら終了して得…

問題 Analyzing Login/Logout Records | Aizu Online Judge パソコンのログイン/ログアウト履歴が与えられる 学生mがts〜teの間に1台以上のPCを利用していた時間を答えよ 方針 学生ごとにPC nのログイン・ログアウトの時間を記録する いもす法の気持ちで1台…

問題 Monday-Saturday Prime Factors | Aizu Online Judge 7で割った余りが1または6の数をMonday-Saturday numberと呼ぶ Monday-Saturday numberが与えられたとき、それを割り切るMonday-Saturday prime (Monday-Saturday numberにおける素数）を全て求めよ …

問題 Amazing Mazes | Aizu Online Judge 迷路で(0, 0)から(w-1, h-1)に移動したい 壁の位置が与えられるので最短の移動回数を求めよ。到達できないときは0を出力せよ 方針 最短経路なので幅優先探索。壁の与えられ方が少し特殊かも。 コード #include <bits/stdc++.h> usin</bits/stdc++.h>…

問題 Short Phrase | Aizu Online Judge 単語の列から57577になっている部分列を探し、最初の部分列の最初の単語番号を出力せよ 方針 57577のどこをチェックしているかをstageで管理して最終ステージまで言ったらクリアみたいな感じ コード #include <bits/stdc++.h> using </bits/stdc++.h>…

問題 ICPC Ranking | Aizu Online Judge ICPCっぽいコンテストの提出履歴から順位を決定せよ 順位は、解いた問題数が多い順・解いた問題数が同じならかかった時間が短い順に決まる 異なる順位ならカンマ区切り、同順位なら=区切りで出力せよ 同順位ならチー…

問題 Integral Rectangles | Aizu Online Judge 長方形に 1. 対角線の長さが短いほうが小さい． 2. 対角線の長さが同じならば，高さの低いほうが小さい． という大小関係を定める hxwより大きい横長の長方形で最小のものを求めよ 方針 全通り作って調べる コ…

問題 Recurring Decimals | Aizu Online Judge L桁の数字を並び替えて作れる数字の最大値と最小値の差で数列を作っていく。 数列に同じ数字が現れるのはいつか 方針 実際に並び替えて数列を作り、一つ作るたびに数列をチェックする コード #include <bits/stdc++.h> using n</bits/stdc++.h>…

問題 Numeral System | Aizu Online Judge 'm'が1000、'c'が100、'x'が10、'i'が1を表す記数法で書かれた2つの数字を足して、その記数法で出力せよ 方針 与えられた文字列を左から見て10進数に変換し足し算する。和をもとの記法に戻す コード #include <bits/stdc++.h> usin</bits/stdc++.h>…

問題 Organize Your Train part II | Aizu Online Judge 与えられた文字列を2つに分けて、各部分文字列を逆向きにするか入れ替えるという操作をしてもよい 生成される文字列が何種類あるか数える 方針 文字列を全部作る コード #include <bits/stdc++.h> using namespace st</bits/stdc++.h>…

問題 The Balance of the World | Aizu Online Judge 与えられた文について丸カッコと角カッコの対応が取れているか調べよ なお、カッコのペアで囲まれた部分文字列についても対応が取れないといけない 方針 与えられた文字列について、任意の位置で左カッコ…

問題 Dirichlet's Theorem on Arithmetic Progressions | Aizu Online Judge a+i*dという形の数字でn番目の素数を求めよ 方針 エラトステネスのふるいで素数リストを保持しておき、実際に求める コード #include <bits/stdc++.h> using namespace std; typedef long long ll</bits/stdc++.h>…

問題 Pablo Squarson's Headache | Aizu Online Judge 指示に従ってタイルを並べていくときに横幅と縦幅を求めよ。 指示はn_i番目のタイルの上下左右どこに置くかという形で与えられる。 方針 各タイルの座標を保持しておき、指示を読み込む度にx, y軸の最大…

問題 Chebyshev's Theorem | Aizu Online Judge n<x<=2nの範囲にある素数の数を出力 方針 エラトステネスの篩で素数リストを事前に作っておいて、実際に数える コード #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(int i=0; i<(n); ++i) const int max_n = 1000000; int prime[max_n]; int main(void){ rep(i, max_n) prime[i] =…</x<=2nの範囲にある素数の数を出力>

問題 How Many Islands? | Aizu Online Judge 8方向に隣接した陸地を島と定義する。 フィールドの各タイルが陸か海かの情報から、いくつ島があるか数えよ。 方針 dfsで隣接した土地に同じidを振り、idが何種類あるかを数える コード #include <bits/stdc++.h> using namespa</bits/stdc++.h>…

問題 Red and Black | Aizu Online Judge WxHのフィールドの中でスタート地点から四方に移動する。黒のタイルの上だけを通って移動できるタイルの数を求めよ。 方針 スタート地点からdfsして到達可能なタイルをメモ。タイルの数を最後に数える。 コード #inc…

問題 Entrance Examination | Aizu Online Judge 受験者の点数リストが与えられる。不合格者と合格者の点数差が最大になるn_min以上n_max以下で最大の合格者数を出力せよ 方針 点数を大きい順にソートし、n_min以上n_max以下の合格者数全てについて点数差を…

問題 Get Many Persimmon Trees | Aizu Online Judge WxHの土地のうちでSxTの領域に含まれる木の本数の最大値を求める 方針 全てのSxTの領域について木の本数を数える コード #include <bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, n) for(i</bits/stdc++.h>…

問題 When Can We Meet? | Aizu Online Judge 会議参加者の都合が良い日のリストが与えられるので、最も多くの人が参加できる一番早い日程を決める 定足数に達する日がある開催日を出力、達しなければ0を出力 方針 日付から参加人数を求めるmapを作って最大…

問題 Tax Rate Changed | Aizu Online Judge 消費税がx%のとき合計金額がs円だった2つの品物を消費税y%のときに買ったときの値段の最大値を求めよ。 なお、消費税がx%のときの値段はp (100+x) / 100を切り捨てた整数値である。 方針 合計がsになるペアを全探…

問題 Millennium | Aizu Online Judge 変則的な暦でy年m月d日から1000年1月1日まで何日あるかを数える 一年は10ヶ月で、通常の年は20日ある月と19日ある月が交互に訪れる 3の倍数の年は全ての月が20日ある 方針 1年1月1日を1日目として、y年m月d日が何日目か…

問題 Equal Total Scores | Aizu Online Judge n枚のカードを持つ太郎とm枚のカードを持つ花子が1枚ずつカードを交換して合計点数が等しくなるようにする 交換するカードの点数を出力（複数通りあるときは和が最小のもの） 方針 n, mが100以下なので全通りの…

問題 Next Mayor | Aizu Online Judge 円卓に並んだn人の人が碗の中のp個の石を取り合うゲーム。 0番目の人から数字が大きくなる方向に碗を順番に回していく。 碗に石が入っているときは石を一つ取り、入っていないときは持っている石を全てボウルに入れる。…

問題 Hanafuda Shuffle | Aizu Online Judge N枚のカードの山のp番目からc枚を抜き出して一番上に持ってくるシャッフルを繰り返したときに一番上に来るカードは何か 方針 シャッフルをそのまま実行する コード #include <bits/stdc++.h> using namespace std; typedef long </bits/stdc++.h>…