050 - Stair Jump（★3） 問題 N 段の階段 があり、一歩で 1 段か L 段上がれる。 0 段目からN 段目までたどり着く移動方法何通りか、109 + 7 で割った余りを求める。 解法 そこまでに行ける通り数をDPで下から計算する。 答えは大きくなるので常にmodを取り…

048 - I will not drop out（★3） 問題 N 問, K 分間, 満点 A 点, 部分点 B 点(部分点は満点未満, 半分より大きい) つまり を満たす。 1分で部分点, 2分で満点が取れる。 K 分間で得られる最大得点を求める。 解法 得点方法は2パターン。 B 点取る or B 点取…

046 - I Love 46（★3） 問題 3つの長さ N の数列 A, B, C が与えられる。 が46の倍数となるの選び方の総数を求める。 解法 3つの数列が最大105と制約が厳しいため全探索ではTLEになってしまう。 そのため、最初にmodを取ることで、0〜45の46種類に絞る。 463…

038 - Large LCM（★3） 問題 A, Bの最小公倍数を求める。 を超える場合は Large と出力する。 解法 最小公倍数は で表される。 そのまま計算すると でオーバーフローすることがあるので、式を変換する。 であれば が成り立つので正しく答えが求まる。 ちなみ…

032 - AtCoder Ekiden（★3） 問題 N人の駅伝選手。 コースは 1からN区まであり、選手 i が j 区までかかる時間は M 個のルールがあり、 と はたすきの受け渡しができない。 ゴールまでにかかる時間の最小値を求める。 解法 制約が N ≤ 10 と小さいため最大で…

020 - Log Inequality（★3） 問題 < が成り立つか。 解法 愚直に log() を使って求めると誤差が出てしまう。 そのため全て整数で処理をする必要がある。 対数 log は 底が同じ値の場合、log が外せるので、 は と表せる。 そして累乗の場合は、 が成り立つ。…

018 - Statue of Chokudai（★3） 問題 平面 x = 0 上に、高さ L の T 分で一周する観覧車がある。 xy 平面が水平で z が垂直。 0 分後の座標は 分後の座標は 分後の座標は 分後の座標は 銅像が にある。 以下の形式の質問が Q 個与えられるので順に求める。 …

016 - Minimum Coins（★3） 問題 A円、B円、C円と硬貨が3種類ある。 それぞれ0枚以上使ってちょうどN円を支払うとき、使う硬貨の枚数の最小値を求める。 解法 そのまま全探索すると になり、TLEする。 そのためループを3重から2重へと減らす必要がある。 xと…

014 - We Used to Sing a Song Together（★3） 問題 N人。家は にある。 学校は N校あり、 にある。 全員別の学校に通わせる。 学生 i の家から学校までの距離 , 不便さは距離の総和 である。 位置 u から位置 vまでの距離は 不便さの最小値を求める。 解法 …

007 - CP Classes（★3） 問題 N個のクラス、Q人の生徒。 クラスのレーティングは , 生徒のレーティングは と表す。 不満度は対象レーティングと自分のレーティングの差の絶対値。 各生徒の不満度の最小値を求める。 解法 Aをソートして 以上と未満の値の2つ…

002 - Encyclopedia of Parentheses（★3） 問題 長さNの正しいカッコ列を出力する。 条件 () は正しい。 Sが正しいとき、 ( + S + ) は正しい。 S,Tが正しいとき、文字列 S + T は正しい。 ( の方が ) よりも辞書順で早いものとする。 解法 まず奇数の場合は…