AtCoder, 実装

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

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

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

AtCoder, 整列

問題方針

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

AtCoder, 数学

問題方針方程式を立てる

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

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

\

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

AtCoder, 数学

問題方針

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

\

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

AtCoder, 動的計画法, 桁DP

問題方針桁DP

\( n \) 以下の数字の中で \( 4 \) または \( 9 \) を含まない数の個数を求めます。\( d_{i, 0} \) を上位 \( i \) 桁目まで調べたとき、\( 4 \) または \( 9 \) を ...

AtCoder, 幅優先探索, 探索

問題方針ステップ数が \( 3 \) の最短距離の探索

例えば、ステップ数が \( 3 \) の最短経路の探索では、スタート地点から \( 3 \) ステップ目で到達可能な頂点を距離 \( 1 \) で到達可能な頂点とします。また、この ...

AtCoder, 数学

問題方針

赤いボールの個数を \( a = N – K \) とします。まず初めに、青いボールを一列に並べておきます。

\( i \) 回操作するために必要なボールの冗長でない置き方\( i = 1 \) のとき

...

AtCoder, 整列

問題方針

配列 \( d \) の順序は入れ替えても大丈夫なので、昇順にソートさせます。\( N \) は偶数なので、\( d \) の中央値をそれぞれ、\( c_1 = d_{N/2 – 1} \)、\( c_2 = d_ ...

AtCoder, グラフ理論

問題方針

グラフが連結であることから、辺の数は最低でも \( N – 1\) 本必要になります。

構築できるグラフの最短距離が \( 2 \) の頂点対の個数の最大値

辺の数が \( N – 1 \) ...

AtCoder, 貪欲法

問題方針

締め切り時刻である \( B \) の値が小さいものから仕事を終わらせていくシミュレーションを行います。ある仕事が終わった時の時刻を \( t \) とすると、次に取り掛かる仕事 \( i \) が、\( t + A_i \l ...