AtCoder

問題方針

実際に平方根の計算をすると誤差が怖いので、整数で比較する方法を考えます。

\

ここで、\( c – a – b < 0\) ならば上記の不等式は正しくありません。よって、\ ...

問題方針

文字列 \( S \) を前後を反転してできる文字列を \( S^* \) とします。\( S \) の先頭に追加された文字列を \( L \) とし、末尾に追加された文字列を \( R \) とすると、最終的な文字列は、\( ...

問題方針

消費税を題材にした問題ですね。全探索をするのが楽ですが、ここでは別の解き方をしようと思います。

\( A \) に着目

\( A \) に着目すると、

\

を満たす \( x \) を求めれば ...

問題方針

区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメ ...

問題方針

まず初めに、友達関係の Union-Find を作成します。このとき、人 \( i \) の友達の数を \( f_i \) として数えます。次に、人 \( i \) のブロック人数を \( b_i \) と、人 \( i \) ...

問題方針

\( d_i \) を上位から \( i \) 桁目の数字とします。\( d \) を \( -1 \) で初期化し、条件を満たすように数字を決めた時、\( d_i \) が異なる数字を取るときは整数が存在しません。また、\( ...

方針方針

部屋 \( i \) にいる人の数を \( a_i \) とすると、

\

が成り立ちます。このとき、\( a_i \geq 0 \) を満たす整数解は、\( {}_{2n – 1} \mat ...

問題方針

二項係数の剰余に関する問題です。二項係数の和は、

\

となるので、花束の種類は \( 2^n – 1 \) 通りあります。したがって、求める答えは、\( 2^n – 1 R ...

問題方針

問題は最小二乗法に関するものなので、最適な座標は平均値となります。最小二乗法の解説が詳しいです。

コード

 

問題方針

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