ryo’s blog

日々学んだことをまとめています.

競プロ典型90問

競プロ典型90問 050(★3) DP

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

競プロ典型90問 048(★3) 貪欲法

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

競プロ典型90問 046(★3) 組合せの問題

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

競プロ典型90問 038(★3) オーバーフロー

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

競プロ典型90問 032(★3) 順列全探索

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

競プロ典型90問 020(★3) 浮動小数点の誤差

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

競プロ典型90問 018(★3) 三角関数

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

競プロ典型90問 016(★3) 全探索

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

競プロ典型90問 014(★3) 貪欲法

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

競プロ典型90問 007(★3) 二分探索

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

競プロ典型90問 002(★3) next_permutation

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