AtCoder,桁DP

問題方針

\( N \) を数値として扱うと制約が大きすぎるので、桁DPを行います。上位 \( i \) 桁目までの数字に対して、\( d(i, 0) \) を \( i \) 桁目の数字の分だけお札を使ったときの最小値とし、\( d( ...

AtCoder,二分探索,尺取り法

問題方針

\( A_i = 0 \) となる個数を \(N_0 \) とし、\( A_i < 0 \) となる数列を新たに \( B \) とし、\( A_i > 0 \) となる数列を新たに \( C \) とします。この ...

AtCoder,整列

問題方針

マップを使って文字のカウントをし、最多得票の文字列を辞書順に出力します。自作の比較関数を定義すれば整列を楽に行えます。

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

AtCoder,動的計画法,桁DP

問題方針

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

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

AtCoder,数学,累積和

問題方針

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

\

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

コード#include <bi ...

AtCoder,セグメント木,二分探索,整列

問題方針

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

最適な攻撃方法

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

AtCoder,動的計画法

問題方針

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

AtCoder,数学

問題方針

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

AtCoder,整列

問題方針

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

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

AtCoder,数え上げ

問題方針

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

\

となります。

コード ...