AtCoder,全探索,動的計画法

問題方針

ショートカットは冗長に選んだとしても \( 4^4 \) 通りなので、全てのショートカットの組み合わせに対して必要なボタンの入力回数を求めます。ここで、\( d(i, 0) \) を \( i \) 文字をショートカットを使わ ...

AtCoder,深さ優先探索

問題方針

\( 8 \) クイーン問題です。深さ優先探索によって解答します。初期値が当てられたとき、配置が可能かに注意します。

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

AtCoder,全探索

問題方針

中心座標の候補は最大でも \( 10000 \) 個なので、中心座標に関して全探索します。\( h_i \neq 0 \) であるとき、

\begin{eqnarray}
h_i &=& H ...

AtCoder,数学

問題方針

点 \( i \) と点 \( j \) のマンハッタン距離を \( d(i, j) = |x_i – x_j| + |y_i – y_j|\) とすると、絶対値の外し方を考慮して、

\be ...

AtCoder,全探索,数学

問題方針非負整数解の個数

非負整数 \( x, y, z \) が

\

を満たすとき、\( x, y, z \) の組み合わせは、\( {}_{n} \mathrm{ H }_{2} = {}_{n + 1} \ ...

AtCoder,数学

問題方針組み合わせ

全ての数列の組み合わせは \( 10^N \) 個あります。\( 0 \) または \( 9 \) が存在しない数列の組合せは \( 9^N \) 個あります。\( 0 \) と \( 9 \) が存在しない数列の組 ...

AtCoder,データ構造,実装

問題方針

ある集合の最大値を管理し、その集合の最大値の中の最小値を答える問題です。これは、multiset を使って管理できるそうです。multiset は順序が保たれます。

ここで、幼稚園 \( i \) のレートの集合を ...

AtCoder,実装

問題方針

敷き詰めパズルのような問題ですが、実際はもっと簡単です。一番左上の行から右に向かって色 \( i \) を \( a_1 \) 個塗っていき、\( W \) 個塗ったあとは、下の行の右端から左に向かって塗っていきます。つまり、 ...

AtCoder,貪欲法

問題方針

\( p_i = i \) となる \( i \) に対して、\( (p_i, p_{i+1}) = (p_{i+1}, p_i)\) と交換します。このとき、\( p_{i+1} = i \) となるので、交換によるロスはあ ...

AtCoder,動的計画法

問題方針

マス \( (i, j)\) にあるアイテムの価値を \( g(i, j) \) とします。アイテムがない場合は \( 0 \) とします。次に、マス \( (i, j)\) において \( i \) 行目のアイテムを \( ...