AtCoder, 累積和

問題方針各ビットごとに着目

整数 \( A, B\) を \( 2 \) 進数表記で下位から \( i\) ビット目を \( a_i, \ b_i \) と表します。例えば、\( A = a_1a_2a_3 \) , \( B = b_ ...

AtCoder, ビット全探索, 探索

問題方針ビット全探索

ある人は正直者か不親切な人かの \( 2 \) 通りなので、全体で \( 2^N \) のパターンがあります。なので、ビット全探索を行います。人 \( i \) が正直者としたとき、その証言が現在のビットの状態と同 ...

AOJ, 数学

問題方針タイルの増加数

タイルの増加数に着目すると、\( 1^2, 2^2, 3^2, 5^2, 8^2, \cdots \) と増加しているので、\( x \) 方向と \( y \) 方向にタイルの辺がフィボナッチ数ずつ増えているこ ...

yukicoder, 動的計画法

問題方針大きさが異なっている隣り合う餅をずんだ餅にする場合

この場合、大きさが小さい餅が消えてしまうので適切ではありません。例えば、\( A = (1, 2, 3, 4, 5) \) の配列において、\( 1 \) 番目と \( 2 \ ...

yukicoder, 数学

問題方針

\( X, Y \) を \( 2 \) 進数で表現したときの \( i \) 番目のビットを \( x_i, y_i \) とします。同様に \( A, B \) についても \( a_i, b_i \) とします。条件より ...

yukicoder, データ構造

問題方針

カンニングされた人がカンニングを行っていないかどうかを調べます。これはセットを使って実現することができます。

コード

 

AtCoder, データ構造, 全探索, 探索

問題方針

長さが \( N \) の文字列から \( 3 \) 文字取り出すことを考えると、計算量は \( {}_{N} \mathrm{ C }_{3}\) となってしまうので、別の方法を考えます。考えられる文字列は \( 1000 ...

AtCoder, 動的計画法

問題方針

動的計画法を行い、\( X \) を作れるかどうかを調べます。\( i \) 円が作れるとき、\( i + 100 \) 円も作れるというような方針で実装します。

コード

 

yukicoder, 文字列

問題方針

順列に関する問題です。ライブラリの prev_permutation() を利用しましょう。

コード

 

AtCoder, グラフ理論

問題方針

トポロジカルソートを利用するみたいです。

コード