2018-01-22

COLOCON -Colopl programming contest 2018- C すぬけそだて――ごはん――

競技プログラミング AtCoder

https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c

問題概要

$A$ 以上 $B$ 以下の整数を0個以上選ぶ。
選んだ整数のうちすべての整数が互いに素であるように選ぶとき、何通りの選び方があるか。

制約
$1 \le A \le B \le 10^{18}$
$B - A \le 35$

解法

$B - A \le 35$ より、それぞれの整数が35以下のどの素数を素因数に持つかについて考えればよい。
35以下の素数の数は11個しかないので、bitで情報を持つことができる。

dp[ $i$ ][ $j$ ] := $i$ 番目の整数までみて、選んだ整数の素因数の状態が $j$ であるときの場合の数

というDP配列をつくればよい。

計算量は $O( N \times 2^p )$ ( $p$ は $B - A$ 以下の素数の数) になり十分間に合う。

（解説には全探索って書いてあったけどよくわからなかった）

Submission #2006870 - COLOCON -Colopl programming contest 2018-

Submission #2006886 - COLOCON -Colopl programming contest 2018-
（↑bit演算使ったら簡潔なコードがかけるよって教えてもらった）

2018-01-20

ABC065/ARC076 D Built?

競技プログラミング AtCoder

D - Built?

問題概要

$N$ 個の街があり、 $i$ 番目の街は座標 $( x_i , y_i )$ にある。
座標 $(a, b)$ にある街と座標 $(c, d)$ にある街の間に道をつくるのに、コストが $min(|a-c|, |b-d|)$ 円かかる。
任意の2つの街の間を道を通って行き来できるようにするための最低コストを求めよ。

制約
$1 \le N \le 10^5$
$0 \le x_i, y_i \le 10^9$

解法

3つの街が $(a, b), (c, d), (e, f)$ にあるとする。
$a < c < e$ かつ $b < d < f$ のとき、 $(a, b)$ と $(c, d)$ の間、 $(c, d)$ と $(e, f)$ の間の2つの道を作るならば、 $( a, b)$ と $(e, f)$ の間に道を作る必要はない。
このことから、 $x$ 座標または $y$ 座標が最も近い街同士だけの辺を考えれば良いことがわかる。

また、任意の2つの街を行き来できるというのは、街を頂点、道を辺としたグラフが連結であり、連結グラフの辺のコストを最小化するのは、グラフの最小全域木を構成するということになる。

よって解法は

$x$ 座標でソートして隣り合う街に辺をはる
$y$ 座標でソートして隣り合う街に辺をはる
最小全域木を求め、コストを出力する

辺は高々 $2(N-1)$ 本しかないので、計算量は $O(NlogN)$ になる。

Submission #1994769 - AtCoder Regular Contest 076

2018-01-20

CODE FESTIVAL 2017 Final B Palindrome-phobia

競技プログラミング AtCoder

B - Palindrome-phobia

問題概要

'a', 'b', 'c' の3種類の文字からなる文字列 $S$ が与えられる。
文字列 $S$ を自由に並び替えて、部分文字列に2文字以上の回文を含まないようにできるかどうか判定せよ。

制約
$1 \le |S| \le 10^5$

解法

2文字以上の回文が含まれないとき、並べ替えた文字列は
…abcabcabc…
または
…acbacbacb…
のどちらかになる。
なので、各文字が含まれる個数を計算し、最も多く含まれる文字の文字数と最も少なく含まれる文字の文字数の差が1以下であるかを調べればよい。

Submission #1992543 - CODE FESTIVAL 2017 Final (Parallel)

2018-01-19

DDCC2016 予選 C ロト2

競技プログラミング AtCoder

C - ロト2

問題概要

$N$ 個の整数があり、 $i$ 番目の整数は $A_i$ である。

$A_i \times A_j$ が $K$ の倍数となるような $i$ と $j$ の組み合わせ $( i , j )$ が何通りあるか求めよ。

制約
$2 \le N \le 200000$
$1 \le A_i \le 10^9$
$1 \le K \le 10^9$

解法

積が $K$ の倍数になればいいのだから、それぞれの $A_i$ において必要な情報は、 $K$ の約数のうちどれが含まれているか。
よって、それぞれの $A_i$ について、 $gcd(A_i , K)$ を求める。
あとはそれらを2つかけて $K$ の倍数にできるかを判定して数え上げればいい。

ってことまで自力で思いついて、具体的な方法が思い浮かばなかった。ので解説を見た。

$1 \le K \le 10^9$ だから、 $K$ の約数の個数は高々1500個くらいらしい。よって、連想配列か何かに $gcd(A_i , K)$ を記録していって、2重ループで全探索すれば良い。

連想配列は滅多に使わないので、範囲forというものを初めて知った。
範囲for文 - cpprefjp C++日本語リファレンス

Submission #1988558 - AtCoder Grand Contest 013

2018-01-18

AGC013 Hamiltonish Path

競技プログラミング AtCoder

B - Hamiltonish Path

問題概要

$N$ 頂点 $M$ 辺の、連結な単純無向グラフが与えられる。頂点には $1$ から $N$ までの番号がついており、辺には $1$ から $M$ までの番号がついている。辺 $i$ は、頂点 $A_i$ と頂点 $B _i$ を結んでいる。次の条件を満たすパスを $1$ つ見つけて出力する（あり得る答えのうちどれを出力しても良い）。

2個以上の頂点を通る
同じ頂点を2度以上通らない
パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる

制約
$2 \le N \le 10^5$
$1 \le M \le 10^5$
$1 \le A_i < B_i \le N$

解法

条件3の「パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる」が具体的にどういうことかについて考えてみる。
パスの少なくとも一方の端点と直接辺で結ばれている頂点がパスに含まれていないという状態は、パスの端点からその頂点に対して、パスを伸ばすことができるということを意味する。つまり、条件3が言いたいことは、あるパスがあったときに、条件2を満たした上で、そのパスをできるだけ長く伸ばしたものを出力しないといけないということ。

よって解法の方針は

好きな頂点を選んで、そこから辿れる頂点をパスに含まれる頂点として配列などに入れておき、辿れなくなったら順に出力する

となる。
計算量は、各頂点についてパスの端点として追加される回数が高々1回であり、端点から辺で結ばれている頂点がパスに含まれているかを調べるので、 $O(N+M)$ 。

Submission #1988558 - AtCoder Grand Contest 013

2018-01-17

ABC080 D Recording

競技プログラミング AtCoder

D - Recording

問題概要

$N$ 個のテレビ番組を録画したい。
テレビが受信できるチャンネルが $C$ 個あり、1から $C$ までの番号がついている。
録画したいテレビ番組のうち、 $i$ 個目のテレビ番組は、時刻 $s_i$ から時刻 $t_i$ までチャンネル $c_i$ で放送される（時刻 $s_i$ を含み時刻 $t_i$ を含まない）。同じチャンネルで複数のテレビ番組が同時に放送されることはない。
また、録画機は、あるチャンネルの時刻 $S$ から時刻 $T$ までを録画するとき、時刻 $S − 0.5$ から時刻 $T$ までの間、他のチャンネルの録画に使うことができない(ただし時刻 $S − 0.5$ を含み時刻 $T$ を含まない）。
必要な録画機の最小個数を求めよ。

制約
$1 \le N \le 10^5$
$1 \le C \le 30$
$1 \le s_i < t_i \le 10^5$
$1 \le c_i \le C$

解法

はじめは $C$ と $c_i$ を無視してimos法したら解けるんじゃないかと思ったけど、2ケースWA。

いろいろ考えてるうちに、
2 1
1 2 1
2 3 1
のケースでダメなことがわかる。
この例でいくと、時刻1から時刻3までを録画したいから、時刻0.5から時刻3までを1つの録画機で録画したいけど、「時刻0.5から時刻2」「時刻1.5から時刻3」の2つを録画することになって、2個の録画機が必要という答えが出てしまう。
つまりチャンネルの情報は不要じゃなかった。

ということで、
v[ $i$ ][ $j$ ] := チャンネル $i$ で時刻 $j$ に録画機を使う
という配列を作って、各チャンネルでimos法をする。
このときは、開始時刻を $S - 0.5$ ではなく $S$ と考えてimos法をして、あとから録画開始時刻を1だけ早める（これで、同じチャンネルで連続して録画するときに重複をなくせる）。

あとは各時刻について、いくつのチャンネルで録画機が必要かを計算する。
計算量は $O(NC)$ 。

Submission #1986276 - AtCoder Beginner Contest 080

2018-01-15

ABC076 D AtCoder Express

競技プログラミング AtCoder

小数きらい

D - AtCoder Express

問題概要

次のような列車を運行する。

走行開始時と走行終了時には列車は止まっていなければならない。
列車の走行時間は $t_1 + t_2 + … + t_N$ 秒である。
最初の $t_1$ 秒間は列車は速度 $v_1 m/s$ 以内で走行しなければならない。また次の $t_2$ 秒間は列車は速度 $v_2 m/s$ 以内で走行しなければならない。次の $t_3$ 秒間、またそれ以降も同様である。
最後の $t_N$ 秒間は列車は速度 $v_N m/s$ 以内で走行しなければならない。
列車の性能上、加速度は $\pm 1 m/s^2$ 以内でなければならない。