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 ...

AOJ,二分探索,実装,探索

問題方針

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

Codeforces,数学

問題方針

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

Codeforces,全探索,探索

問題方針

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

AtCoder,数え上げ

問題方針

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

\

となります。

コード ...

AtCoder,数え上げ

問題方針

\( 1 \leq j  \leq i \) において、\( P_i \leq P_j \) が成り立つことを確認するには、\( P_j \) の最小値が条件を満たしているかどうかを調べれば良いです。よって、最小値を ...

AtCoder,数学

問題方針

\( 0 \leq K \leq N \) という制約なので、この問題は簡単に解くことができます。\( A \) の \( K \) 個の要素が \( S \) を取るとき、\( N – K \) 個の要素をどのよ ...