AOJ 1155: How can I satisfy thee? Let me count the ways...

問題 How can I satisfy thee? Let me count the ways... | Aizu Online Judge "true", "false", "unknown"の3種類があるロジックで、与えられた式を満たすP, Q, Rの組み合わせが何種類あるか数えよ 方針 P, Q, Rがそれぞれ3通りの値を取るため27通りしかな…

AOJ 1602: ICPC Calculator

問題 ICPC Calculator | Aizu Online Judge 国際反括弧会議が考えた変な記法に従って計算するプログラムを作れ 各行は入れ子レベルを表す'.'・加算を表す'+'・乗算を表す'*'・整数からなる 式の最初の行は入れ子レベルの数だけの'.'からなる レベルnの演算子…

AOJ 1194: Vampire

問題 Vampire | Aizu Online Judge 与えられたビルの位置から、あと何秒間太陽が隠れているか求めよ 方針 ビルの位置が整数値なのでビルがある場所についてグリッドを埋めていく 太陽が通りうる位置についてグリッドが埋まっていなかったら太陽が通過する瞬…

AOJ 1127: Building a Space Station

問題 Building a Space Station | Aizu Online Judge 宇宙ステーションの各ユニットを全てつなぎたい 各ユニットは座標(x, y, z)に存在し、半径がrの球形である。球が接触していない場合は廊下でつなぐ必要がある 必要な廊下の長さの最小値を求めよ 方針 い…

AOJ 1188: Hierarchical Democracy

問題 Hierarchical Democracy | Aizu Online Judge [[[99][59][63][85][51]][[1539][7995][467]][[51][57][79][99][3][91][59]]]という形で与えられる選挙区の区割りから、当選するために必要な最低得票数を求めよ [99]とある場合はその選挙区に99人の有権者…

AOJ 1149: Cut the Cake

問題 Cut the Cake | Aizu Online Judge 大きさwxdのケーキをn回切り分ける 入力はp, sという形で与えられ、p番目のピースの左上から時計回りにs進んだところを起点に垂直に切断する ピースの番号はカットが終わるたびに出来たのが古い順、出来たのが同じな…

AOJ 1144: Curling 2.0

問題 Curling 2.0 | Aizu Online Judge カーリングっぽいゲームを10回以内でクリアできるか調べよ 方針 シミュレーションして10回以内にクリアできるか調べる 障害物にぶつかったら消去するという盤面変化を記録する方法がbfsだと思いつかなかったのでdfsし…

AOJ 2400: You Are the Judge

問題 You Are the Judge | Aizu Online Judge 提出ログから求まる順位の順に、ID・正解数・ペネルティを表示せよ 方針 AOJ 1187: ICPC Ranking - はやくプロになりたいとほぼ同じ コード #include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(</bits/stdc++.h>…

AOJ 1007: JPEG Compression

問題 JPEG Compression | Aizu Online Judge NxNのマスをジグザグに走査するとき、各マスにアクセスする順番を求めよ 方針 合計sumになる(y,x)の組ごとに考える sumが偶数なら右上に、奇数なら左下に進んでいく 次に進むマスが範囲外ならsumの偶奇とnとの関…

AOJ 0101: Aizu PR

問題 Aizu PR | Aizu Online Judge 文字列中の"Hoshino"を"Hoshina"に書き換えろ 方針 "Hoshino"という文字列があったら最後の文字を'a'にする 置換関数を使わずに書く練習ということで。 cin >> nした後にgetline(cin, s)すると変な挙動をしたので、数字もg…

AOJ 0100: Sale Result

問題 Sale Result | Aizu Online Judge 総売上が1,000,000以上の従業員のIDを入力順に表示せよ どう考えても悪問だった 方針 問題文には明示されていないが、同じ従業員の売上記録が複数回与えられることがあるのでmapで保持しておく 問題文には明示されてい…

AOJ 0052: Factorial II

問題 n の階乗 | Aizu Online Judge nの階乗を求めたとき、末尾に0がいくつ並ぶか 方針 10=2x5であるので10をつくるには因数に2と5が必要。明らかに2の方がたくさんあるので5の個数を数える コード #include <bits/stdc++.h> using namespace std; #define rep(i, n) for(in</bits/stdc++.h>…

AOJ 0020: Capitalize

問題 Capitalize | Aizu Online Judge 小文字を大文字に変換せよ 方針 小文字なら'A'-'a'を足す コード #include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i=0; i<(n); ++i) int main(void){ string s; while(getline(cin, s)){ rep(i, s.size()) {</bits/stdc++.h>…

AOJ 0019: Factorial

問題 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>…

AOJ 0018: Sorting Five Numbers

問題 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>…

AOJ 0017: Caesar Cipher

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

*AOJ 1126: The Secret Number

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

AOJ 1136: Polygonal Line Search

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

AOJ 1167: Pollock's conjecture

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

AOJ 1193: Chain Disappearance Puzzle

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

AOJ 1148: Analyzing Login/Logout Records

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

AOJ 1154: Monday-Saturday Prime Factors

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

AOJ 1166: Amazing Mazes

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

AOJ 1601: Short Phrase

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

AOJ 1187: ICPC Ranking

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

AOJ 1186: Integral Rectangles

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

AOJ 1180: Recurring Decimals

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

AOJ 1137 Numeral System

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

AOJ 1142 Organize Your Train part II

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

AOJ 1173 The Balance of the World

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