AtCoder,数学

方針方針座標から三角形の面積を求める

有名な公式として、点 \( O = (0, 0), A = (x_1, y_1), B = (x_2, y_2)\) において、三角形 \( OAB \) の面積 \( s \) は、

...

AtCoder,二分探索,動的計画法,探索

問題方針広義単調減少部分列

\( A_1 \geq A_2 \geq \cdots \geq A_i \) となるような広義単調減少列に対して、\( i \) 個の色が必要であることが分かります。これは、連続しない部分列に対しても言える ...

AOJ,セグメント木,二分探索,動的計画法,探索

問題方針

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

動的計画法と二分探索

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

AtCoder,実装

問題方針最後の箱から調べる

後ろの箱からボールを入れることを考えると、その箱以降の倍数の個数は変化しないことが分かります。

例えば、\( i < \dfrac{N}{2} \) を満たす \( i \) の倍数は、\( ...

AtCoder,整列

問題方針

\( A \) を昇順に整列させた配列を \( B \) とすると、\( B_N \) は \( A \) の最大値となります。\( A_i \) を取り除いた配列の最大値は、\( A_i = B_N \) ならば、\(B_{ ...

Codeforces,実装

問題方針題意

文字列 \( s \) に \( p\) に含まれる文字の数だけ任意の場所に挿入して、文字列 \(t\) を作ることができるか調べます。

文字が現れる頻度を計算する

各文字列についてどの文字の頻度を計算します。も ...

Codeforces,数え上げ

問題方針題意

\( 1 \) から \( n \) までの数字があり、\( k \) 個ごとに仕切りがあります。初期の配置では、仕切り \( i \) には、\( ik \) から \((i + 1)k\) までの数字が存在しています。 ...

yukicoder,グラフ理論,ダイクストラ法,全探索,探索

問題方針

解説を見ても良く分かりませんでした。

似たような問題で、CSA の良問があります。

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

AtCoder,数学

問題方針方程式を立てる

\( N = 2n + 1 \) として考えます。

山 \( i \) に降った雨の量を \( x_i \) とします。このとき、

\

となります。よって、\( S_{2n+1 ...

AtCoder,数学

問題方針

区間 \( \) を全探索する必要はなく、\( \) の範囲を調べればよいです。これは、

\

という関数を考えると、\( 0 \leq f(x) \leq 2018 \ (L \leq x \leq L ...