データ構造

問題方針

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

最適な攻撃方法

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

問題方針

点数が更新されたとき、その時点で最も高い得点を持つチームの番号が分かればよいので、セグメント木を使います。クエリは全区間を対象とするので、根の値が最も高い得点を持つチームの番号となります。

コード#include < ...

問題方針

平方分割でこの問題を解いたことがありますが、セグメント木を使って解きました。

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

問題方針

カンニングされた人がカンニングを行っていないかどうかを調べます。これはセットを使って実現することができます。

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

問題方針

長さが \( N \) の文字列から \( 3 \) 文字取り出すことを考えると、計算量は \( {}_{N} \mathrm{ C }_{3}\) となってしまうので、別の方法を考えます。考えられる文字列は \( 1000 ...

問題方針チケットの使い方

チケットを一度に複数枚使うことと一枚ずつ使うことが同じであることを確認します。\( 2 \) の指数を用いて整数を表現することを考えます。例えば、\( 31 \) は、

\

と表現できま ...

問題方針

\( i \) 番目の人の正解数を \( p_i \) とすると、その人のポイントは、\( K + p_i – Q \) と表すことができます。よって、正解数の頻度を計算します。

コード#include &l ...

問題方針

「明日できることは今日するな」ということで、締め切りから考えていきます。残り \( i \) 日あるとき、まだ請け負っていないアルバイトに対して \( A_j \leq i \) を満たすものの中で報酬が一番大きいものを選びま ...

問題方針子どもの移動の挙動

どのような文字列でも十分に移動を行うと、’RL’ または ‘LR’ という二つのマスを行き来することになります。また、’RL’ という文 ...

問題方針

LIS: Longest Increasing Subsequence (最長部分増加列) という問題です。この問題では、狭義単調増加列の中で最も大きいものを求めます。

動的計画法と二分探索

参考を参照してください。 ...