Easy 問題概要 最初、整数値x = 0である。 N回、以下のいずれかの操作を繰り返す。 xに0からAまでのいずれかの整数値を加算する。 xに0からBまでのいずれかの整数値を減算する。 N回の操作の後、xの値が0でなければならない。 上記の操作を最適に行ったとき…

問題概要、制約 説明が難しいので省略。サンプルの説明のところ読むと概要を理解しやすい。 Authentication Level | Aizu Online Judge 解法 ダイクストラ。それぞれの事務所について、部屋をx個訪問したときの最小コストを求める。 これはダイクストラによ…

問題概要、制約 省略。 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>…

問題概要 長さL-1の平均台の上にN羽のうさぎがいる。i番目のうさぎの初期位置はxiであり、0 ≤ xi ≤ xi+1 ≤ L-1を満たす。それぞれのうさぎは、1回ジャンプすると右にaiだけ移動できる。任意の回数ジャンプすることできるが、別のうさぎを飛び越えたり、L以上…

問題概要, 制約 長いので省略。 ニッシン館マラソン部 | Aizu Online Judge 解法 シミュレーションをする。 シミュレーションする際には、それぞれの人のいる給水所、各給水所の空の容器の数、中身の入った容器の数を状態に持つと良い。まず、時間を1ずつ進…

問題概要 5つの整数a, b, c, d, eが与えられるので、これらを降順に並び替えよ。 制約 -105 ≤ a, b, c, d, e ≤ 105 解法 基本的な考え方は、これと同じ。 上記のリンク先の別解でやればOK。別解以外の方法では、ソートアルゴリズムを自分で実装する方法があ…

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

問題概要 w個の縦棒、n個の横棒で構成されるあみだくじがある。 横棒iは、aiとbiをつなぐ。 横棒は、上に存在するものから与えられる。 制約 w ≤ 30 n ≤ 30 解法 まず、始めに横棒が1本もない場合を考える。 その場合、i番目の縦棒から始めるとi番目の縦棒へ…

問題概要 平面上の3点(x1, y1), (x2, y2), (x3, y3)が与えられたとき、それらを頂点とした三角形の外接円の中心座標と半径を求めよ。 制約 -100 ≤ x1, y1, x2, y2, x3, y3 ≤ 100 データセットの数 ≤ 20 解法 点1と点2の垂直二等分線、点2と点3の垂直二等分線…

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

問題概要 nが与えられる。 a + b + c + d = n を満たすa, b, c, d(a, b, c, dそれぞれの値は、0から9までの範囲の整数に限る)の組み合わせの総数を求めよ。 制約 1 ≤ n ≤ 50 解法 全探索。 a, b, c, dについて、それぞれが0から9のいずれであるかをループで…

問題概要 最初お金が10万円ある。1週間ごとに5%の利子を加え、さらに1000円未満を切り上げる。 n週間後のお金を求めよ。 制約 0 ≤ n ≤ 100 解法 シミュレーションする。5%を加えるは、今持っているお金をmとすると、 m × 1.05である。1000円未満の切り上げ方…

問題概要 正の整数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 解法 ガウスジョルダン法に投げる。式…

問題概要 文字列strが与えられるので、その文字列を逆順に表示せよ。 制約 1 ≤ 文字列のサイズ ≤ 20 文字列中の文字は、半角英数字のみ 解法 まず、文字列を入力する。 文字列の入力について、C言語、C++では以下のように書く。 C言語 /* 注意点として、文字…

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

問題概要 整数a, bが与えられる。 a + bの桁数を出力せよ。 制約 0 ≤ a, b ≤ 106 データセットの数 ≤ 200 解法 まず、a + bを求める。この結果をcとする。 cについて、桁数を求めるためには、0になるまで、何回10で割れるか(切り捨て)を確かめれば良い。例え…

問題概要 10個の山の高さ(整数値)が与えられるので、高さが大きい順に3つ出力せよ。 制約 0 ≤ 山の高さ ≤ 10000 解法 与えられた10個のデータを降順にソートして、0番目から2番目を順に出力する。別解として、 与えられた10個のデータの最大値を求める。これ…

気が向いたらどんどん追加していく予定です。(9/21) 現在64問の解説があります。 Volume 0 0000: QQ 0001: List of Top 3 Hills 0002: Digit Number 0003: Is it a Right Triangle? 0004: Simultaneous Equation 0005: GCD and LCM 0006: Reverse Sequence 0…

問題概要 九九を出力せよ。 注意点 掛ける記号(×)は、小文字のx(エックス)を使用すること。 解法 そのまま全てを出力しても良いが、 forループを使用することによって簡単に実装できる。 コード #include <iostream> using namespace std; int main() { for (int i = 1</iostream>…