AtCoder,幾何学

問題方針

\( N = 2n \) とします。点 \( p_0 \) と 点 \( p_{n} \) を結ぶ線は正 \( N \) 角形の重心である

\

を通ります。したがって、この重心を中心として点 \( p_ ...

AtCoder,ビット全探索

問題方針

長さ \( N \) の数列から得られる長さ \( 1 \) 以上の連続した部分数列は、\( 2^{N-1} \) 通りあるので、ビット全探索します。イメージとして、分割される位置をビット列で表し、その値を更新していけば良いで ...

AtCoder,全探索

問題方針

前半と後半の文字が同じ数字を考えるので、前半の部分について全探索します。

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

AtCoder,貪欲法

問題方針

価値が高い荷物からその大きさに最も近い箱に入れます。

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

AtCoder,数え上げ

問題方針

コンマの数が \( i \) 個となる数字 \( x \) の範囲は、\( 10^{3i} \leq x \leq 10^{3i + 3} – 1 \) なのでこの範囲を \( i \) を全探索すれば良いです。

AtCoder,データ構造

問題方針セットとマップによる値の管理

まず初めに、セットに \( 1 \) から \( M \) までの値を入れます。次に、先頭から \( M \) 個までの \( M \) 未満の値の頻度をマップで管理します。このとき現れた値をセット ...

AtCoder,数学

問題方針確率 \( p \) が起こるまでの期待値

確率 \( p \) が起こるまでの期待値を \( E \) とします。\( i \) 回目に初めて確率 \( p \) が起こるときの確率は \( (1-p)^{i – ...

AtCoder,データ構造

問題方針

各要素同士の差の \( 2 \) 乗の和を求めるために、\( A_i \) の頻度を数えます。

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

AtCoder,ダイクストラ法

問題方針

都市 \( X \) から都市 \( i \) へたどり着いたときの最短時間を \( d_i \) とします。初期値は、\( d_X = 0, d_i = \infty \ (i \neq X) \) とします。 また、鉄道が ...