問題概要、制約 省略。 Cleaning Robot | Aizu Online Judge 解法 確率DPをする。dp[i][j] := バッテリーをi使って位置jにいるときの確率。 位置は二次元座標だが、(x, y)をy * 3 + xのようにすると次元を1つ落とすことができる。 コード #include <bits/stdc++.h> using na</bits/stdc++.h>…

問題概要 n!を求めよ。 制約 1 ≤ n ≤ 20 解法 n! = n × n-1 × ... × 2 × 1 であるので、それを計算すれば良い。計算方法には、ループで書く方法と再帰関数で書く方法がある。 ループ fact = 1; for (int i = 1; i <= n; i++) { fact *= i; // fact = fact * …

問題概要 整数nが与えられるので、n以下の素数の数を出力せよ。 なお、素数とは、「1と自分自身でしか割り切れない正の整数のうち1を除いたもの」である。 制約 1 ≤ n ≤ 999999 解法 エラトステネスの篩 + 累積和 エラトステネスの篩については、wikipedia(…

問題概要 正の整数a, bが与えられるので、これらの最大公約数と最小公倍数を出力せよ。 制約 0 ≤ a, b ≤ 2 × 109 aとbの最小公倍数は、2 × 109を超えない。 データセットの数は50を超えない。 解法 まず、最大公約数を求める。 ただし、N = min(a, b)とし、 …

問題概要 a, b, c, d, eが与えられたとき、 連立方程式 ax + by = c dx + ey = f を解き、x, yの値を求めよ。 なお、解は一意に定まる。出力の際には、小数点第4位を四捨五入せよ。 制約 -1000 ≤ a, b, c, d, e ≤ 1000 解法 ガウスジョルダン法に投げる。式…

問題概要 三角形の3辺の長さが与えられるので、これらを好きな辺に割り当てて直角三角形を作れるか判定し、 作れる場合、"YES"を作れない場合、"NO"を出力せよ。 制約 1 ≤ 1辺の長さ ≤ 1000 データセットの数 ≤ 1000 解法 まず、3辺の長さを昇順(小さい順)に…

問題概要 N個の町があり、その中には町sと町tが含まれる。町sでFリットル生クリームが製造され、他の町に運び、町tまで運ぶ。移動の際に移動元の町と移動先の町の気温差の絶対値だけ生クリームが傷む。各町の気温はN元一次連立方程式の解により求められる。…

問題概要 nとpが与えられる。 1~nまでの数字で分子と分母を作ったとき、x/y > √p > u/vとなる最小のx/yと最大のu/vを分数の形で出力せよ。出力する分数は既約分数である必要がある。 制約 n < 10000 p < 10000 解法 √pより大きくなる分数、小さくなる分数そ…

問題概要 N個の数字(c1,c2,...,cN)が与えられる。Q個のクエリがあり、各クエリでqが与えられる。このときN個の数字の中でqで割った余りの最大値を出力せよ。 制約 2 ≤ N ≤ 300000 2 ≤ Q ≤ 100000 1 ≤ ci ≤ 300000 1 ≤ qi ≤ 300000 解法 まず、入力されたN個…

問題概要 a,b,cが与えられるので、 ax2+bx+c = (px+q)(rx+s)を満たすp,q,r,sを求めよ。 そのような組み合わせがない場合は、"Impossible"を出力する。 制約 0 < a ≤ 10000 -10000 ≤ b ≤ 10000 -10000 ≤ c ≤ 10000 0 < p 0 < r (r < p) or (p == r and s ≤ q)…

問題概要 H行に空白(' ')またはアスタリスク('*')が与えられる。そしてアスタリスクは、いくつかの四角形(長方形または平行四辺形または台形)を構成している。任意の2つの四角形は接することはなく、辺を共有することもない。ある四角形の中に別の四角形が存…

問題概要 洞穴がいくつか存在する。そのうち中央の洞穴の番号を1とし、そこから渦巻き状にm個の番号がつけられている。ある洞穴からは左下、下、右下のいずれかに移動できる。また、洞穴のうちその番号が素数のものを素数洞穴という。スタート地点の番号をn…

問題概要 縦A × 横Bのノートがある。 箱がN個あり、各箱の大きさは縦C × 横Dである。 それぞれの箱にノートが入るかどうかを判定し、入る場合は"YES"を入らない場合は"NO"を出力せよ。 ただし、ノートを回転させたり平行移動させてもよい。 制約 1 ≤ A , B ,…