AtCoder

問題方針

\( A \) と \( B \) の公約数を考えるので、\( A \) と \( B \) の最大公約数を考えます。最大公約数を素因数の数が求める答えとなります。

コード#include <bits/stdc++ ...

問題方針

\( i \) 番目の生徒が教室に来た時の教室にいる生徒の人数が \( A_i \) なので、\( i \) 番目の生徒は \( A_i \) 番目に教室に来たことになります。よって、\( A_i \) について昇順に整列させ ...

問題方針チケットの使い方

チケットを一度に複数枚使うことと一枚ずつ使うことが同じであることを確認します。\( 2 \) の指数を用いて整数を表現することを考えます。例えば、\( 31 \) は、

\

と表現できま ...

問題方針

\( i \) 番目の人の正解数を \( p_i \) とすると、その人のポイントは、\( K + p_i – Q \) と表すことができます。よって、正解数の頻度を計算します。

コード#include &l ...

問題方針

幸福でない人に着目して考えます。幸福でない人の文字列は、”RL” または “LR” となっているので、同じ文字が連続する文字列は幸福である人を含んでいるので、\( S \) を圧 ...

問題方針

条件を具体的に書き出すと、

\

となり、\( A_1 \) と \( A_N \) は不等式の制約が一つであることが分かります。よって、\( A_1 = B_1 \), \( A_N = B_{N-1} ...

問題方針制約から考える

\( N = 10^9 \) と制約がきついので、計算量は \( O(\sqrt{N})\) や \( O(1) \) などが考えられます。また、こういった問題は、\( N = 1 \) から実際にシミュレーショ ...

問題方針シミュレーション

数列 \( H \) の先頭から実際にシミュレーションをしていきます。現在の最大の移動回数と現在の移動回数を保持しながら探索をします。

コード#include <bits/stdc++.h>u ...

問題方針転倒数

転倒数を求めるアルゴリズムはマージソートを利用したものや BIT を使ったものがありますが、今回はデータ数が小さいので、\( O(N^2)\) の計算量が間に合います。\( A \) の転倒数を \( s_1 \) とし ...

問題方針ビット全探索

派閥の組み合わせはビット列で表現できるので、ビット全探索を用いて最大の派閥に属する議員数を求めます。派閥が成り立つときその派閥のグラフは完全グラフになっている必要があります。完全グラフかどうかの確認は、人間関係を隣 ...