[AOJ] No. 0386 ワープ装置
\( d(i) \) を文字 \( i \) の出口への行き方の数として、動的計画法を行います。初期値は \( d(s_0) = 1\) とします。更新式は、\( d(s_i) \leftarrow d(s_i) + d(t_ ...
[AOJ] No. 0385 ボゾソート
数列の要素を交換するたびに全ての要素が昇順に調べるのは効率が悪いので別の方法を考えます。昇順に整列させたときの数列と元の数列の要素が異なるものの数を \( t \) とします。交換を行う前に、\( t = 0 \) であれば、 ...
[AOJ] No. 0384 デュードニー数
各桁の和の最大値は最大でも \( 72 \) なので、\( y \) を決め打ちして考えます。条件を満たす \( y \) について、\( x \) の桁和が \( y \) になるかどうかを調べます。
コード#incl ...
[AOJ] No. 0363 積み荷の配置
\( i \) 列目に荷物が置けるかどうかは \( i – 1 \) 列目と \( i \) 列目を調べれば良いので、動的計画法を行います。各列の状態は荷物か置けるマスがあるかどうかの \( 2 \) 通りであり ...
[AOJ] No. 0361 電線
まず初めに、重複する点を許すと、縦方向の電線と \( x + 1 \) 回交わり、横方向の電線と \( y + 1 \) 回交わることになります。また、必ず端点で \( 2 \) 回縦方向と横方向の電線に交わるので、その分除外 ...
[AOJ] No. 0411 矢印
空白のマスを〇で表すとします。”→←〇〇” という状態で ”〇→←〇” と矢印を動かしても点数に変化はありません。また、”→→←〇〇” という状態では、”〇→→←〇” と動かすと点数が \( 1 \) 増えます。
...
[AOJ] No. 0410 アカベコ20
参加するメンバーの組み合わせは \( 2^{N} – 1\) 通りあるので、ビット全探索を行います。周期が同じメンバーが増えても必ず同じ公演に参加することになるので、参加するメンバーの組み合わせが増えることはありま ...
[AtCoder] ABC 147 D – Xor Sum 4
整数 \( A, B\) を \( 2 \) 進数表記で下位から \( i\) ビット目を \( a_i, \ b_i \) と表します。例えば、\( A = a_1a_2a_3 \) , \( B = b_ ...
[AtCoder] ABC 147 C – HonestOrUnkind2
ある人は正直者か不親切な人かの \( 2 \) 通りなので、全体で \( 2^N \) のパターンがあります。なので、ビット全探索を行います。人 \( i \) が正直者としたとき、その証言が現在のビットの状態と同 ...
[AOJ] No. 0409 床
タイルの増加数に着目すると、\( 1^2, 2^2, 3^2, 5^2, 8^2, \cdots \) と増加しているので、\( x \) 方向と \( y \) 方向にタイルの辺がフィボナッチ数ずつ増えているこ ...