ヤマカサの競技プログラミング

問題方針

見るからに桁DPの問題なので動的計画法を行います。

\( d(i, j, 0) \) を \( N \) の上位 \( i \) 桁目まで一致する数字で、\( 0 \) でない数字の個数が \( j \) 個である ...

問題方針

サイコロの出る目が \( a \) まであるとき、このサイコロの出る目の期待値は、

\

となります。したがって、累積和などを用いて最大となる値を全探索します。

コード#include <bi ...

問題方針

モンスターの順序は問題に影響を与えないので、モンスターの座標について昇順に並び替えて考えます。

最適な攻撃方法

最適な攻撃方法は、モンスターの先頭から爆弾を使っていくやり方です。爆弾の位置は、爆弾の範囲の最も左を今注 ...

問題方針

商品を無数に選ぶことができるナップザック問題なので、動的計画法を使って解きます。\( d(i) \) をモンスターに \( i \) ダメージ与えれるために必要な魔力とします。初期値は、\( d(0) = 0 \) であり、\ ...

問題方針

モンスターの体力が \( H \) から \( 1 \) になるまでのモンスターの体力の種類を考えます。このとき、\( i \) 番目に大きい体力を \( H_i \) とします。ここで、\( H_1 = H \) であり、\ ...

問題方針

必殺技をHPの多いモンスターから使えば良いので、体力の順に整列させます。

コード#include <bits/stdc++.h>using namespace std;typedef long long ll;in ...

問題方針

時刻の変換と同じように、いったん最小単位に変換してから計算を行います。西暦からマヤ歴への変換は、2012年12月21日からどれだけの日数が経過したかどうかを計算します。このときうるう日に気を付けます。マヤ歴から西暦への変換は、 ...

問題方針

\( i \) 回目の質問で脱落する人数を \( a_i \) とし、\( a_i \) の累積和 \( s_i \) を \( s_i = a_1 + a_2 + \cdots a_i \) とします。このとき、得られる賞金 ...

問題方針

\( n \) 階建てビルの \( s \) 階から一番近いレストランを探します。フロア \( a_i \) のレストランは閉店しているので、\( s – k \) から \( s + k \) の範囲を全探索を行 ...

問題方針

\( a(i, j) \) を先頭の数字が \( i \) で末尾が \( j \) である \( N \) 以下の正の整数の個数とします。これをもちいて、求める答えは、

\

となります。

コード ...