問題概要、制約 説明が難しいので省略。サンプルの説明のところ読むと概要を理解しやすい。 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>…

問題概要 RxCのグリッドがある。グリッドは、'.' (部屋)または'#'(壁)で構成されており、壁には侵入することができない。人は上下左右の部屋に移動することができ、移動するには1単位時間かかる。全ての部屋には、電気がついており、部屋に入るためには電気…

問題概要 文字列Sが与えられるので、それが "Cat" か "Rabbit" かを判定せよ。ただし、文字列Sが "Cat"とは、 CAT := ””(empty string) | ’m’+CAT+’e’+CAT+’w’ を満たすことである。(+は連結を意味する)文字列Sが"Cat"でなければ、"Rabbit"である。 制約 1 ≤…

問題文, 制約 日本語なので省略 解法 構文解析＋全探索まず、入力で与えられる文字列から木を構築する. その木の内部節点にナンバリングする.後は、内部節点の個数分(多くても8個)だけ、'A'を0, 'O'を1, 'X'を2として 全通り(例えば、内部節点が3個なら、000…

問題概要 平面上のn個の円環から構成される鎖がある。最初と最後の円はそれぞれ、次の円、1つ前の円のみと交差し、他の各円は隣の2つの円のみと交差する。以下の2つの条件を満たす最短経路を求めよ。 経路は、最初の円の中心がスタートで、最後の円の中心が…

問題概要 H×Wの大きさの店がある。店内は、床('.'), 壁('#'), 目的地('t')で構成されている。N個の(x,y)の組が与えられる。これは時間i(1 ≤ i ≤ N)に(xi,yi)のマスが開放される(そのマスが壁('#')ならば床('.')になる)。この条件の下、スタート地点(0,0)から…

問題概要 Claireという女性がいる。彼女がN人の男性のうちの何人かとデートをするプランを立てることを考える。N人の男性にはそれぞれM個のデートをする時間帯(SからE)とその男性とデートしたときの満足度Lが与えられる。彼女は各男性に対して、全ての時間帯…

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

問題概要 H×Wの二次元グリッドがある。このグリッドは以下の要素で構成されている。 '@' : スタート位置 'E' : ゴール位置 '#' : 壁のマス 'c' : コンテナが存在するマス 'w' : パネルのマス プレイヤーは隣接する上下左右のマスに移動することができる。た…

問題概要 n個の数値v1,v2,…,vnとwが与えられる。 1区間の範囲をwにしたヒストグラムを作成する。例えば、下図ならば、w = 10で各区間は、0~9,10~19,20~29,30~39のようになる。この各区間の棒グラフに色を塗る。一番左を黒に、それから右に行く毎に色を薄くし…

問題概要 折れ線0,1,….,nのn+1個の折れ線が与えられる。各折れ線はm個の頂点で構成される。折れ線を構成する各線分はx軸またはy軸に平行であり、頂点では必ず90°回転する。xy平面で回転または平行移動をして折れ線0と一致する折れ線iを出力せよ。テストケー…

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