AtCoder,グラフ理論,周期性

問題方針

\( k \) 回シミュレーションを行うことはできないので、シミュレーションを高速化の考えます。\( k \) が十分大きければ、探索の過程で同じ単語を調べることになるので、閉路が存在することになります。下記の問題がこの問題と ...

Codeforces,全探索,数学

問題方針

排他的論理和の問題です。最上位のビットが同じ \( 1 \) である自然数を \( a_{i}, a_{i + 1}, a_{i + 2} \) とすると、

\

となります。配列 \( a \) の連続 ...

Codeforces,ゲーム問題

問題方針

自分の勝利の最大化が一番優先されるので、ボブの勝利数が \( y \) となるかを考えます。もしアリスのサーブを全て返さずに、アリスのスタミナが \( 0 \) となったとき、ボブとアリスの勝利数は、\( x, y \) とな ...

Codeforces,二分探索,数学

問題方針

\( t \) 回のジャンプで行くことができる最大の点は

\

となります。ここで、自然数 \( t \) を

\

を満たす最小の \( t \) とします。このとき今いる座標がち ...

AtCoder,周期性

問題方針

参加者が出す手は周期性を持ち、最初に出す手は周期 \( n \) で変わります。ここで、\( T_0 = ss \) とします。ここで、\( f(t) \) を文字列 \( t \) を出す参加者で勝利した文字列とします。\( ...

AtCoder,二分探索

問題方針

\( n + 1 \) の長さの丸太を切断することを考えます。

\

を満たす最大の \( m \) を求めると、\( n + 1 – m \) 本の丸太を買えば良いです。

コード#in ...

AtCoder,数学

問題方針

廊下だけを使うか、廊下と階段を使うかの \( 2 \) 通りを考えます。階段を使う場合は、廊下を先に通り、残りは階段を使います。

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

yukicoder,数学

問題方針

期待値の問題では、\( 1 \) 回あたりどうなるかを考えることがあります。

\( i \) 回目の操作後の数列 \( A \) の総和を \( X_i \) とします。このとき、

\ = A_1 + ...

yukicoder,数学

問題方針

ビット演算を題材にした問題は、ビット毎に考えることがあります。自然数 \( N \) を \( 2 \) 進数で

\

と表します。

同様に、\( A, B, C \) についても \( 2 ...

AtCoder,分枝限定法,深さ優先探索

問題方針

整数計画法である 0-1 ナップサック問題を線形計画法で解くことを考えます。線形計画法では、重さ当たりの価値が大きいものから取っていけば良いです。ここで、荷物を重さ当たりの価値の降順になるように並び替えます。

深さ ...