2018-01-27

ARC027 B 大事な数なのでZ回書きまLた。

問題概要

2つの文字列が与えられる。同じアルファベットは同じ数字を表し、異なるアルファベットは異なる数字を表す場合と同じ数字を表す場合がある。2つの文字列が同じ $N$ 桁の数を表すとき、その数は何通りあるか。

制約
$1 \le N \le 18$

解法

アルファベットをUnion Findを使って管理する。

各桁の文字において、両方共が数字の場合は無視して良い。
片方が数字の場合は、もう片方のアルファベットは数字が固定されるため、そのアルファベットのとりうる値は1通りしかないので、アルファベットに使われることのないある数（numとする）を用意して、その数にuniteする。
両方がアルファベットの場合は、それらのアルファベットは同じ数字を表すため、uniteする。

あとは、片方の文字列を最初から見て、そのアルファベットがnumにつながっていたら（すでにuniteしていたら）、その桁のとりうる数字は1通りしかないので何もしない。numにつながっていなかったら（uniteされてなくて親が違ったら）、そのアルファベットは10通り（文字列の先頭ならば9通り）の数字をとるので、答えにかけあわせる。そしてそのアルファベットは値を決めたとして、numにuniteする。

Submission #2019412 - AtCoder Regular Contest 027

2018-01-24

ARC085 / ABC078 C HSI

競技プログラミング AtCoder

C - HSI

問題概要

プログラミングコンテストの 'YES' か 'NO' で答える問題でTLEした。
テストケースは $N$ ケースあり、そのうち $M$ ケースでTLEしていた。
そこで、 $M$ ケースではそれぞれ実行に $1900$ ms かかって $\frac{1}{2}$ の確率で正解し，残りの $N - M$ ケースではそれぞれ実行に $100$ ms かかって必ず正解するプログラムへ書き換えた。
一度ですべてのケースに正解するまで提出を繰り返したときの、プログラムの実行時間の総和の期待値を求めよ。

制約
$1 \le N \le 100$
$1 \le M \le min(N, 5)$

解法

この問題の答えを $y$ msとすると、あるケースで不正解だった場合、それ以降の提出の実行時間の総和の期待値は $y$ msになる。
よって、1回の提出での実行時間の総和を $x$ ms、すべてのケースに正解する確率を $p$ とすると、
$y = x + (1 - p)y$
という式が成り立ち、この式を整理すると、この問題の答え $y$ は
$y = \frac{x}{p}$
になる。

ここで、
$x = 1900M + 100(N - M)$
$p = \frac{1}{2^M}$
であるので、代入すると
$y = ( 1900M + 100(N - M) )2^M$
となる。

Submission #2012637 - AtCoder Regular Contest 085

2018-01-23

ARC087 / ABC082 D FT Robot

競技プログラミング AtCoder

D - FT Robot

問題概要

2次元平面の原点にロボットが置かれていて、はじめは $x$ 軸の正の方向を向いている。
'F', 'T' のみからなる文字列 $s$ が命令として与えられ、先頭から順に実行される。

'F' : 今向いている向きに1すすむ
'T' : 時計回りまたは反時計回りの好きな方向に90度だけ向きを変える

すべての命令を実行した後にロボットが座標 $(x, y)$ にいることができるか判定せよ。

制約
$1 \le | s | \le 8000$
$| x | , | y | \le | s |$

解法

命令Tは90度だけ向きを変えることができるから、命令Tを区切りとして分割した時、 $i$ 番目(1-indexed)の区間は $i$ が奇数なら $x$ 座標の向きの移動、 $i$ が偶数なら $y$ 座標の向きの移動になる。
よって、 $x$ 座標の移動と $y$ 座標の移動は別々に考えてよい。

$dp_x [i][j] :=$ $i$ 番目の $x$ 軸方向の移動をした後に $x$ 座標が $j$ かどうか
$dp_y [i][j] :=$ $i$ 番目の $y$ 軸方向の移動をした後に $y$ 座標が $j$ かどうか

という2つのDPを行い、最終的に座標 $(x, y)$ にいるかを判定すればよい。
DPの計算量は $O(| s | ^2)$ なので十分間に合う。

Submission #2009622 - AtCoder Regular Contest 087
（配列aに分割して入れていく必要はないということに通ってから気づいた）

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$ 座標が最も近い街同士だけの辺を考えれば良いことがわかる。