2018-06-03

AtCoder Beginner Contest 098の解説

A - Add Sub Mul

入力: $A\;B\quad(A,B \in \mathbb{Z};\, -1000 \le A, B \le 1000)$
出力: $A+B$ , $A-B$ , $A\times B$ の中で最大の値

writeln(max(A+B, A-B, A*B));

感想: はい

B - Cut and Count

入力:
$N\quad (2 \le N \le 100)$
$S\quad (|S| = N)$
出力: Sを一箇所で切断してできた２つの文字列 $X, Y$ のどちらにも含まれている文字の種類数の最大値

「どちらにも含まれている」 -> "setIntersection"

ulong res;
foreach(i; 0..N) {
	auto X = S.dup; // sort()が作用してしまうのでコピーする
	auto a = X[0..i].sort().uniq.array; // 部分列に含まれる文字を取得
	auto b = X[i..$].sort().uniq.array; // (sortで揃えてuniqで隣り合う同要素を一つにする)
	int tmp = setIntersection(a,  b).array.length.to!int; // 文字の種類数
	res = max(res, tmp);
}
writeln(res);

感想: B問題にしては難しい気がする

C - Attention

入力:
$N\quad (2 \le N \le 3\times 10^5)$
$S\quad (|S| = N)$ $S_i$ は 'E' または 'W'
出力: 向く方向を変える人数の最小値

各地点でリーダーを決めて、向く方向を変える人数をforループで数え上げるとTLEします。(サンプルだけ通ってsubtaskは通らない)
ここで、累積和を使います。用意すべき配列は、「i番目含め左から今までのWの個数の配列」です。

auto A = new int[](N);

// i番目含め左から今までのWの個数
A[0] = S[0] == 'W';
foreach(i; 1..N) A[i] = S[i] == 'W' ? A[i-1]+1 : A[i-1];

// i番目含め左から今までのEの個数
// WでないならEがそこにあるため、余事象の考え方が使えます。
auto C = (int n) {
	return n+1 - A[n];
};

foreach(i; 0..N) {
	ulong tmp;
	tmp += C(N-1) - C(i); // リーダーより右でEを向いている人の数
	tmp += i < 1 ? 0 : A[i-1]; // リーダーより左でWを向いている人の数
	res = min(res, tmp);
}
res.writeln;

先に累積和の配列を生成することで、このようなTLEを解消できます。

感想: 累積和全然やってないオタクだったのでコンテスト中に解けず。頭が回らなかった。

D - Xor Sum 2

入力:
$N\quad (1 \le N \le 2 \times 10^5)$
$A_1 \, A_2 \, \ldots \, A_N\quad (A_i \in \mathbb{Z};\, 0 \le A_i \le 2^20)$
出力: $A_l \, {\rm xor} \, A_{l+1} \, {\rm xor} \, \ldots {\rm xor} \, A_r = A_l + A_{l+1} + \ldots + A_r$ を満たす整数 $l, r\, (1 \le l \le r \le N)$ の組の個数

しゃくとり法を使います。

foreach(l; 0..N) {
	// 尺取り法(l: left, r: right)
	// 題意(和とxorが等しい)を満たすなら
	while(r < N && (total + A[r] == (xor_sum ^ A[r]))) {
		total += A[r];
		xor_sum ^= A[r];
		r += 1; // ひとつ右に進める
	}
	res += r - l; // 区間長をたす(一回前までうまくいっていたので)

	// 区間の左端をひとつ右に進めるので、そのぶん(A[i])をなかったことにする
	// 逆演算すればよい。足し算の反対は引き算、xorの反対はxor
	total -= A[l];
	xor_sum ^= A[l];
}
writeln(res);

ある区間 $A = [l, r)$ で条件を満たしているなら、 $\forall a \forall b([a, b))\, (a, b \in A)$ でも条件を満たします。

感想: コンテスト中にたどり着かなかった。しゃくとり法やったことなかった。知らない・理解していないアルゴリズムとか考え方はまだまだたくさんあるので、精進は大事だなあって思った。

A: Submission #2561733 - AtCoder Beginner Contest 098
B: Submission #2564967 - AtCoder Beginner Contest 098
C: Submission #2604714 - AtCoder Beginner Contest 098
D: Submission #2573473 - AtCoder Beginner Contest 098

2018-05-13

AtCoder Beginner Contest 097の解説

お疲れ様でした！

A - Colorful Transceivers

入力: $a\;b\;c\;d\quad(a,b,c,d \in \mathbb{Z};\, 1 \le a, b, c, d \le 100)$

出力: 会話可能なら"Yes", そうでないなら"No"

直接的にaさんとcさんが会話可能…abs(a-c) ≦ d

間接的にaさんとcさんが会話可能…abs(a-b) ≦ d ∧ abs(b-c) ≦ d

この2つのどちらかが成り立つならば会話可能である。

writeln((abs(a - c <= d) || ( abs(a - b) <= d && abs(b - c) <= d) ? "Yes" : "No");

感想: はい

B - Exponential

入力: $X\quad(X \in \mathbb{Z};\, 1 \le X \le 1000)$

出力: X以下の最大のべき乗数( $1^3, 6^4, 2^9$ のような、指数が2以上の数)

まず、1000以下のべき乗数すべてを含むリストを生成する。

処理としては、「まず、与えられた数(2 ≦ a ≦ 1000)を2乗して1000以下ならその数をリストにぶち込み、3乗して1000以下ならその数をリストにぶち込み、4乗して1000以下なら…」というようにしていき、1000より大きな数になったら次の数に移る。これを2から1000までやると欲しいリストの生成が終わる。

int[] arr;
arr ~= 1; // 1をforeachのところに入れると無限ループします＼(^o^)／
foreach(i; 2..1001) {
	auto a = i;
	auto b = a; // aにaをかけていくので、bに最初のaの値を保存する
	auto k = 2; // 指数

	a *= a; // 二乗する
	while(a <= 1000) {
		arr ~= a; // 1000以下のべき乗数であるから、リストに追加する
		k++; // 指数を1増やす
		a = b^^k; // bのk乗をaに代入する
	}
}

[1, 4, 8, 9, 16, 25, 27, 32, 36, 49, 64, 81, 100, 121, 125, 128, 144, 169, 196, 216, 225, 243, 256, 289, 324, 343, 361, 400, 441, 484, 512, 529, 576, 625, 676, 729, 784, 841, 900, 961, 1000] が欲しいリストです。
後は、Xがリストに入っていたなら、その値を出力し、そうでないならXをデクリメントしてもう一度チェックすれば良いです。

auto X = readln.chomp.to!int;
while(true) {
	if(arr.canFind(X)) {
		X.writeln;
		return;
	}
	X--;
}

感想: リストを生成するとき、a^^2を繰り返すだけの処理を最初記述し、それに気づかず1WA。かなしみ。

C - K-th Substring

入力: $s\quad(1 \le |s| \le 5000)$
$K\,\bf(1 \le K \le 5)$

s は異なるsubstringをK個以上持つ

部分点: $|s| \le 50$ なデータセットに正解したら200点/300点がもらえる

$K\,\bf(1 \le K \le 5)$ 。何度でも書きます。 $K\,\bf(1 \le K \le 5)$ 。この問題はかなり容易な思考で解くことができて、単純に考えうるsubstringたちをリストに入れてsortしてuniqueしてK番目を出力すればいい(""を考慮するとK番目)。赤黒木を使っておけば、最後にsort&uniqueする必要すらないんですが、これだけでは部分点しかもらえません。

auto s = readln.chomp, K = readln.chomp.to!int;
auto rbt = new RedBlackTree!string("");
foreach(i; 0..s.length) {
	foreach(j; i..s.length+1) {
		rbt.insert(s[i..j]);
	}
}
rbt.array[K].writeln;

本当に何度でも書きますけど $K\,\bf(1 \le K \le 5)$ 、ですからね。つまり5文字以下のsubstringだけ考えておけばいいので、さっきのコードのinsert部の前に

if(j - i > 5) continue;

を入れるだけでACできてしまいます。
感想: 気づかなかった自分がかなしい。

Cの 1 ≦ K ≦ 5 pic.twitter.com/605ij3SnFp
— public_yusuke (@public_yusuke) 2018年5月12日

D - Equals

入力: $N \, M\, (2 \le N \le 10^5; \, 1 \le M \le 10^5)$
$p_1 \, p_2 \, \ldots \, p_N$ ( $p$ は $1$ から $N$ までの整数を並び替えた順列)
$x_1 \, y_1$
$x_2 \, y_2$
$\vdots$
$x_M \, y_M$
なお、これらの制約は

$1 \le x_j, y_j \le N$
$x_j \neq y_j$
$i \neq j \Rightarrow \{x_i, y_i\} \neq \{x_j, y_j\}$
入力は全て整数

さて、これはUnion Findの典型的な問題らしいです（コンテスト中に解けなかった）。そのため、まずはUnion Findがどのようなものか見ていきましょう。

Union find(素集合データ構造) from AtCoder Inc.

www.slideshare.net

どうやら、 $a \sim b, b \sim c \Rightarrow a \sim c$ であることを取り扱えるデータ構造になっているようです。これを使えば、 $p_i = i$ まで持っていけるかどうかを判断できます。操作は何度でもして良いというところがポイントです。
gist.github.com
これを用意しておきます。
そして、 $x_i - 1$ と $y_i - 1$ をuniteします。これで、どれとどれが交換可能なのかが記録されます。
次に、 $p_i - 1$ と $i$ が交換可能かを判定し、可能ならカウントをインクリメントします。最後にカウントを出力すれば終わりです。

auto uf = new UnionFind!int(N);
foreach(_; 0..M) {
	auto ip2 = readln.split.to!(int[]);
	uf.unite(ip2[0]-1, ip2[1]-1);
}
int res;
foreach(i; 0..N) {
	if(uf.same(p[i]-1, i) res++;
}
res.writeln;

感想: Union Findを知らなかった。すっごく便利でびっくりした。

A: Submission #2494881 - AtCoder Beginner Contest 097
B: Submission #2497541 - AtCoder Beginner Contest 097
C: Submission #2504417 - AtCoder Beginner Contest 097
D: Submission #2505891 - AtCoder Beginner Contest 097

TeXを使ってみたり、はてな記法でSyntax Highlightをさせてみたりしました。すごく便利。便利は正義。

2018-05-13

ことえりのユーザ辞書をGoogle日本語入力用に変換するPythonのスクリプトを作成した

僕「ことえりのユーザ辞書をエクスポートしてGoogle日本語入力にインポートしよう。便利になるに違いない！」

f:id:private_yusuke:20180513154630p:plain

ﾎﾟﾁｯ

f:id:private_yusuke:20180513154716p:plain

は？？？？？キレそう！！！

ということでPython3でスクリプトを組んでみました。

ことえりの辞書をGoogle日本語入力用に変換するPythonスクリプト

使い方はスクリプト内にコメントしてあります。これで今日から快適な辞書ライフを過ごせる。

2018-05-05

AtCoder Beginner Contest 096の解説

お疲れ様でした！

A - Day of Takahashi

入力: a b (a, b ∈ ℤ; 1 ≦ a ≦ 12; 1 ≦ b ≦ 31)

出力: 1月1日からa月b日までの「高橋」の日数

「高橋」…月と日の数が等しい日

まず、a-1月までの「高橋」は確実に含まれるので、

tmp += a-1;

また、bがa以上ならば、a月の「高橋」も含まれるので、

if(b >= a) tmp++;

最後に出力

writeln(tmp);

感想: 1WAした。落ち着いて考えることで、上のような方針が立つ。

B - Maximum Sum

入力: A B C K (A, B, C, K ∈ ℤ; 1 ≦ A, B, C ≦ 50; 1 ≦ K ≦ 10)

出力: K回の操作を終えた後の黒板上の整数の合計としてありうる最大の値

最大の値をとるとき、A, B, Cのうち最も大きい値のみを操作し続けることがわかる。よって

int r = max(A, B, C) * 2 ^^ K;

また、max(A, B, C)をA+B+Cから引いた値、すなわち操作しなかった2つの値についても合計に加えるため

int s = A + B + C - max(A, B, C);

最後に操作後の黒板の整数の合計を出力

writeln(r + s);

感想: 落ち着いて考えることで、上のような方針が立つ。

C - Grid Repainting 2

入力: H W (H, W ∈ ℤ; 1 ≦ H, W ≦ 50)

s(1,1)s(1,2)s(1,3)...s(1,W)

s(2,1)s(2,2)s(2,3)...s(2,W)

…

s(H,1)s(H,2)s(H,3)...s(H,W)

なお ∀i∀j(s(i,j) = '#' ∨ s(i,j) = '.') (1 ≦ i ≦ H, 1 ≦ j ≦ W)

出力: 目標達成が可能なら"Yes", そうでないなら"No"

まずsを2次元配列として読み取る。

'#'に着目する。('.'は初期状態としてすべてのマスに配置されているので、着目しない。)

'#'の近傍4マスに'#'が存在しないならば、すなわち目標を達成することは不可能であることがわかる。よって、'#'を探し、もし存在したら、そこの近傍4マスを探索し、その4マスのどこにも'#'が存在しないならば"No"を即座に出力して終了すればよい。そして、もしすべてのマスが条件を満たしているならば、"Yes"を出力して終了すればよい。解答例は下にまとめてある。

感想: こういう「近傍nマス」みたいなことをするプログラムを書くのに慣れてきた。マインスイーパーとか実装するときよく使う。これにDFS組み合わせたりすると面白くなる。

D - Five, Five Everywhere

入力: N (N ∈ ℤ; 5 ≦ N ≦ 55)

出力: 長さNの数列a_1, a_2, ..., a_Nを出力する。

ただし…

a_i(1 ≦ i ≦ N) は 55,555 以下の素数
i ≠ j ⇔ a_i ≠ a_j
数列aからどのような異なる5個の整数の組み合わせを選んでも、合計が合成数になる

条件を満たす数列が複数個あるなら、どれを出力してもよい。

まず2から1381までの素数を含んだリストを用意する。エラトステネスの篩とかで。

ここで、10n + 1(a ∈ ℤ+)な形をしている素数に着目する。それぞれ異なる5個の素数を、10a+1, 10b+1, 10c+1, 10d+1, 10e+1とおくと、合計は

10(a+b+c+d+e)+5 = 5(2a+2b+2c+2d+2e+1)

となる。ここで、2a+2b+2c+2d+2e+1が2以上であることは明らかなので、10n+1な形をしている素数を55個集めておけば、この問題は解くことが可能である。そのような素数は

11 31 41 61 71 101 131 151 181 ...

と続く。

つまり、一度素数列を生成した後、文字列に変換して一桁目を取得してそれが'1'なら列に入れる、といったfilterの操作をしておいて、そのリストの0個目からN-1個目の値を出力するなどすればよい。

なお、10n+1だけでなく、10n+3, 10n+7の形をした素数列を出力することでも解ける。証明は省略。10n+3の形が一番コストが低いかも？(1303まで用意すれば十分だから)

追記: 想定解の、「5で割って1あまる素数の列」は上の10n+1の形の素数列と全く同じ列を生成する。5(2k+1)+1 = 10k+6 = 2(5k+3)で、商が奇数のときは素数ではないので、結局同じものになる。10n+3, 10n+7の形をした素数列についてもAtCoderで提出をしてACを確認した。

感想: 数学な問題は普段数ⅡBの問題を解くときとかにも使える考え方が適用できたりして面白い。最初「素数列生成してそのまま出せばいいだろ〜ｗ」みたいな甘い考えをしていたら普通にWAされた。A問題と合わせて10分のペナルティがprivate_yusukeを襲ったのであった。

A: https://beta.atcoder.jp/contests/abc096/submissions/2460648

B: https://beta.atcoder.jp/contests/abc096/submissions/2459724

C: https://beta.atcoder.jp/contests/abc096/submissions/2461606

D: https://beta.atcoder.jp/contests/abc096/submissions/2463242

2018-04-27

Suicaインターネットサービスは無記名式Suica不対応、モバイルSuicaもダメ

Suicaインターネットサービス + Amazonでピピっと支払いをしてみたかったので、いろいろ検証しました。

PaSoRiはRC-S380、IE11、iPhone 7 Plus(日本仕様)

結果はこちらです。

①無記名式Suicaは非対応

②記名式Suicaは対応

③モバイルSuicaは移行元が無記名式あるいは記名式にかかわらず非対応

①②はSuicaインターネットサービスのサイトで対応カードとして確認可能でした（①については無知のまま発券機で発行した）。

③については、もちろんSuicaインターネットサービスの対応カードに表記されていない。「じゃあ記名式SuicaをApple Payに追加したら使えるのかな？」と思って検証してみたが、「ご指定のカードではSuicaインターネットサービスをご利用いただけません。」というメッセージを返された。どうやら"FeliCa Mobile"（モバイルSuica）は追加できないようだ。そりゃぁ、モバイルSuica側ですでにSuicaインターネットサービスと同等の支払い機能を持っているんだから、当然のことなんだろう。

2018-03-29

AtCoder Beginner Contest 088 のC問題

ABC088のCを解いてて、解説を見てみると自分と解法が異なったのでメモ

とりあえず問題文の引用(一部改変)

3 × 3 のグリッドがあります. 上から i 番目で左から j 番目のマスを ( i , j ) で表すとき, マス ( i , j ) には数 c_(i,j) が書かれています. 高橋君によると, 整数 a_1 , a_2 , a_3 , b_1 , b_2 , b_3 の値が決まっており, マス ( i , j ) には数 a_i + b_j が書かれているらしいです. 高橋君の情報が正しいか判定しなさい.

さて、問題文より、c_(i,j) = a_i + b_jだから、

c_(1, 1) = a_1 + b_1

c_(2, 1) = a_2 + b_1

c_(1, 2) = a_1 + b_2

c_(2, 2) = a_2 + b_2 したがって

c_(1, 1) = c_(1, 2) + c_(2, 1) - c_(2, 2) が成り立つ。さらにいえば、

c_(n, m) = c_(n, m+1) + c_(n+1, m) - c_(n + 1, m + 1) … ① が成り立つので、

c_(1, 1), c_(2, 1), c_(1, 2), c_(2, 2)を左辺のそれとしてそれぞれ①の考え方を当てはめればOK。その4通りが成り立っていればYes、そうでなければNo

下がD言語での記述の例。

Submission #2276608 - AtCoder Beginner Contest 088

D問題をD言語で解けるようになる日が待ち遠しい。