2018-08-17

CODE FESTIVAL 2016 Grand Final C - Cheating Nim

競技プログラミング AtCoder

C - Cheating Nim

問題概要

2人でNimをする。
はじめに $N$ 個の山があり、 $i$ 番目の山には石が $a_i$ 個ある。
ゲームが始まる前に、それぞれの山から石を0個または1個取り除く。
後手が必ず勝つために取り除く石の数の最小値を求めよ。

制約

$1 \le N \le 10^5$
$2 \le a_i \le 10^9$

解法

Nimで後手が勝つためには、すべての山の石の個数のxorが0でなければならない。
よって、この問題は、「それぞれの山から石を0個または1個取り除いて全体のxorを0にするときの取り除く最小の個数を求める」問題に帰着する。

はじめ、すべての山の石の個数のxorが $x$ で、石が $a_i$ 個ある山から石を1個取り除いた時、全体のxorは $x$ xor $a_i$ xor $(a_i - 1)$ になる。
ここで、 $a_i$ xor $(a_i - 1)$ は $2^k - 1$ と表せるので、全体のxorは $x$ xor $( 2^k - 1 )$ となる。
つまり、この操作において、全体のxorは下位 $k-1$ ビットのみが変更されることがわかる。

よって、 $x$ の上位ビットから順番に見ていき、 $x$ の $k$ ビット目が1だったら、 $a_i$ xor $(a_i - 1)$ が $2^{k+1} - 1$ となる山から石を1個取り除けばよい。

最終的に $x$ が0になれば取り除いた個数を出力し、 $x$ が0にならなければ-1を出力する。

$a_i \le 10^9$ より $x$ は高々32ビット程度なので、各ビットについて石を取り除く山を $O(N)$ で調べても十分間に合う。

Submission #3024566 - CODE FESTIVAL 2016 Grand Final(Parallel)

2018-08-06

「みんなのプロコン 2018」決勝 A - Uncommon

競技プログラミング AtCoder

A - Uncommon

問題概要

$N$ 個の異なる整数 $a_1 , … , a_N$ と整数 $M$ が与えられる。
$1$ 以上 $M$ 以下のそれぞれの整数 $i$ について、 $a_1 , … , a_N$ のうち $i$ と互いに素であるものの個数を求めよ。

制約

$1 \le N, M \le 10^5$
$1 \le a_i \le 10^5$

解法

ある数 $X$ について、 $a_1 , … , a_N$ のうち $X$ と互いに素であるものの個数を求めるとき、愚直に1つずつ試して $O(N)$ でやると全体で $O(N^2)$ となりTLEする。
よって、互いに素であるものをまとめて計算することを考える。
6と互いに素なものは2の倍数でも3の倍数でもないものであるということを考えると、 $X$ と互いに素であるものは、 $X$ の約数の倍数を全体から引いたものであると考えられる。
前計算として、
f[ $i$ ] := $a_1 , … , a_N$ のうち $i$ の倍数であるものの個数
を求めてあげることで、包除原理を使って $X$ と互いに素であるものの個数は高速に求めることができる。

Submission #2959906 - 「みんなのプロコン 2018」決勝

2018-07-20

Codeforces Round 498(Div.3) E. Military Problem

競技プログラミング Codeforces

Problem - E - Codeforces

問題概要

$N$ 頂点の根付き木が与えられる。根は1である。
ある頂点が命令を与えられると、自分の子のうちまだ命令が与えられていない1つの頂点（複数あれば頂点番号が最も小さい頂点）に命令を与える。命令が葉まで伝搬すると、自分の子のうちまだ命令が与えられていない1つの頂点（複数あれば頂点番号が最も小さい頂点）に命令を与えることを繰り返す。

$q$ 個のクエリが与えられる。 $i$ 番目のクエリでは頂点 $u_i$ に命令を与えた時に $k_i$ 番目に命令が伝えられる頂点を答える。

制約

$1 \le N, q \le 2 \times 10^5$

解法

事前に頂点0からDFSをして、命令が伝わる順番を計算しておく。このとき、ある頂点に命令が伝わる順番を記録しておくことによって、各クエリに $O(1)$ で答えることができる。
全体の計算量は $O(q)$

Submission #40441251 - Codeforces

2018-07-20

Codeforces Round 498(Div.3) D. Two Strings Swaps

競技プログラミング Codeforces

Problem - D - Codeforces

問題概要

長さ $N$ の2つの文字列a,bが与えられる。文字列はともに小文字のアルファベットから構成される。
はじめに、好きな回数だけ以下の置換操作を行うことができる。

$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ を任意のアルファベットに置換する

その後、以下の3つの操作を繰り返して文字列a,bを等しくしたい。

$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $b_i$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $a_{n-i+1}$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $b_i$ と $b_{n-i+1}$ を入れ替える

最初の置換操作の回数の最小値を求めよ。

制約

$1 \le N \le 10^5$

解法

$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $b_i$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $a_i$ と $a_{n-i+1}$ を入れ替える
$1 \le i \le N$ となる $i$ を一つ選び、 $b_i$ と $b_{n-i+1}$ を入れ替える

の3つの操作をすることによって、{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }を自由に入れ替えることができる。
また、 $i \neq j$ のとき、{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }と{ $a_j$ , $a_{n-j+1}$ , $b_j$ , $b_{n-j+1}$ }は独立している。
よって、 $1 \le i \le \frac{N}{2}$ について置換操作の回数を計算して足し合わせればよい。

{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }の4つの文字が全て等しければ置換操作はしなくてよい。
また、{ $a_i$ , $a_{n-i+1}$ , $b_i$ , $b_{n-i+1}$ }に2つの等しい文字が含まれているときも置換操作はしなくてよい。

そうでないとき、 $a_i$ と $a_{n-i+1}$ の片方だけを置換すればいいか、両方とも置換する必要があるかを調べればよい。