AtCoder,貪欲法

問題方針

まず初めに仮の最小値 \( d \) を \( d = 0 \) とします。\( i \) 番目の最小値は、\( d \) が \( p_1, \cdots, p_i \) のいずれとも一致しなければ良いので、一致しなくなるま ...

AtCoder,実装

問題方針

現在 \( y \) 行 \( x \) 列にいるとします。このとき、境界を超えるような方向は反転されます。

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

AtCoder,貪欲法

問題方針

カードの種類を \( m \) とします。このとき、残ったカードを \( m \) 枚にするためには、\( N – m \) 枚のカードを取り除かなければいけません。\( 1 \) 回の操作で取り除かれるカードは ...

AtCoder,セグメント木,動的計画法

問題方針

最長増加部分列を解くような感じで解けるみたいですが、あまり理解できませんでした。

まず初めに、\( A_i \leftarrow A_i + K \) と再定義します。ここで、\( d(i) \) を末尾が \( ...

AtCoder,Union Find,幅優先探索

問題方針Union-Find

グラフが連結かどうかを調べるには Union-Find を使えば良いので、ライブラリの dsu を使います。グループの数から \( 1 \) を引いた値が必要な道路の本数です。グループの数は、groups( ...

AtCoder,動的計画法

問題方針

ナップサック問題なので動的計画法で解きます。\( d(i, j, k) \) を スクリーンショット \( i \) まで見た時、\( j \) 枚貼り付けて幅が \( k \) であるときの重要度の合計の最大値とします。遷移 ...

AtCoder,全探索,累積和

問題方針

長方形の和は二次元の累積和を使うことで高速に求めることができるので、全ての長方形のパターンを計算し、\( i \) 個のたこ焼きを焼くときの最大値 \( d(i) \) を求めます。\( d(j) > d(i) \ (j ...

AtCoder,動的計画法,累積和,遅延評価セグメント木

問題方針遅延評価セグメント木

動的計画法のようなことを遅延セグメント木を使って行います。\( v_i \) をマス \( i \) まで行く方法の個数とします。初期値は \( v_1 = 1 \) です。区間 \( \) から整数を選 ...

AtCoder,全探索,数え上げ,数学

問題方針\( A, B \) を全探索

\( A, B \) を全探索します。\( A \) を固定した時、\( A \times b \geq N \) となるような \( b \) より大きいものを探索する必要はありません。 ...

AtCoder,数学

問題方針

シミュレーションすると分かると思いますが、\( A_i \) の値は周期的に遷移します。剰余は \( 0 \) から \( M – 1 \) までの値を取ります。したがって、周期的になる前の \( A_i \) の ...