AtCoder, Union Find, グラフ理論

問題方針行と列を分けて考える

グリッドの問題は行と列を分けて考えることができるかを最初に考えます。この問題も行と列を分けて考えることができます。\( i \) 行 \( j \) 列のマスを \( c(i, j) \) とします。ここで ...

AtCoder, 動的計画法

問題方針動的計画法

今の状態が次の状態に影響するような問題は、動的計画法を使って解くことができます。

\( d_i \) を \( i \) 段目までの移動方法とします。初期値として、\( d_0 = 1 \) とします。ま ...

AtCoder, 数学

問題方針排他的論理和の性質\( \mathrm{XOR} \) を \(\oplus\) で表すとします。

まず排他的論理和の性質として次の二つがあります。

\( 0 \oplus x \ = x \)
\( x \opl ...

AtCoder, 実装

問題方針得られる数列の候補

\( N \) 回の操作で得られる数列の候補を考えます。\( i \) 回目の操作で \( j = i \) としたときに得られる数列は、\( 1, 2, \cdots, N \) となります。よって、\( ...

AtCoder, 数学

問題方針拡張ユークリッドの互除法

\( d = 10^9 + 7 \) とします。

\

上記を満たすような \( R \) をどのように求めるかですが、次の方程式を考えます。

\

ここで、 ...

AtCoder, 数学

問題方針\( p \) を計算するある人があるの色に投票する確率は色によって変わらないので、この確率を \( a \) とすると、\となります。色 \( i \) に \( r_i \) 票集まる確率が \( p \) なので、どのくらい票 ...

AtCoder, 探索

問題方針題意

良いグリッドであるときのマスの状況は、必ず \( 3 \) 色に塗り分けられています。ここで次の集合を考えます。マス \( (i, j) \) に対して、 \( G_k\) は \( i + j \mod 3 = k\) ...

AtCoder, 実装, 整列

問題方針操作の順序

操作 A, B を先に行い、残りの操作で C, D を行います。操作 C, D では負の価値の宝石を絶対値の大きい順に筒に詰めていきます。最後にまとめて宝石を戻すということです。

全探索

制約が緩いので全探 ...

AtCoder, 整列

問題方針

複数の順序があるデータに対する整列は、独自クラスを作成し、順序を定義すると標準ライブラリでソートができます。

コード提出したコード構造体に順序を持たせる (C++)クラスに順序を持たせる (Python)

AtCoder, ビット全探索, 実装, 探索

問題方針ビット全探索

制約を見ずにこの問題を解こうとすると、ドツボに嵌るかもしれません。スイッチの数と電球の数は最大でも \( 10 \) なので、全探索を考えます。スイッチの状態は on/off の \( 2 \) 通りなので、ビット ...