AtCoder Beginner Contest 126の解説

A - Changing a Character

入力:
 N\ K
 S
出力: 新しくできた S
制約:

  •  1 \le N \le 50
  •  1 \le K \le N
  •  Sは'A', 'B', 'C'からなる長さ Nの文字列

A, B, Cをそれぞれa, b, cに変換する関数を作ってあげればよいです。

void main() {
	auto ip = readAs!(int[]), N = ip[0], K = ip[1];
	auto S = rs;
	writeln(S[0..K-1] ~ f(S[K-1]) ~ S[K..$]);
}
 
char f(char x) {
	switch (x) {
		case 'A': return 'a';
		case 'B': return 'b';
		case 'C': return 'c';
		default: return '1';
	}
}

こんな手間をかけなくても、標準ライブラリに入力された文字列に含まれる大文字を小文字に変換する関数が用意されていると思いますので、思いつく人はそちらを使うと良いと思います。

感想: 調べるのがめんどくさかったのでfを実装してしまった。

B - YYMM or MMYY

入力:  S
出力: 'YYMM', 'MMYY', 'AMBIGUOUS' , 'NA' のいずれか
制約:

  •  Sは長さ 4の数字列

Sを"○○××"と表わしたとします。
"○○"が1から12の数字なら'MMYY'の可能性があります。
"××"が1から12の数字なら'YYMM'の可能性があります。

どちらの可能性もあるならば'AMBIGUOUS'、どちらの可能性もないならば'NA'となります。

int i = S[0..2].to!int;
int j = S[2..$].to!int;
bool YYMM = j <= 12 && 1 <= j;
bool MMYY = i <= 12 && 1 <= i;
if(YYMM && MMYY) writeln("AMBIGUOUS");
else if(YYMM) writeln("YYMM");
else if(MMYY) writeln("MMYY");
else writeln("NA"); 

感想: タイピングゲーム

C - Dice and Coin

入力:  N\ K
出力: すぬけ君が勝つ確率
制約:

  •  1 \le N \le 10^5
  •  1 \le K \le 10^5

問題文より、 N面サイコロからは、 1 \le i \le Nであるような iそれぞれの数字が出ます。
したがって、出た目が iのときを考えます。

条件より、勝つためにはコインの表を出し続けることが必要です。では、何回コインの表を出せば勝てるのでしょうか?

これを考えると、 \displaystyle{i}\cdot{2}^{j}\ge{K}をみたす最小のjだけコインの表を出せばいいことがわかります。
両辺の、底が2の対数をとると
 \displaystyle{{\log}_{{2}}{\left({i}\cdot{2}^{j}\right)}}\ge{{\log}_{{2}}{K}}
 \displaystyle{{\log}_{{2}}{\left({i}\right)}}+{{\log}_{{2}}{\left({2}^{j}\right)}}\ge{{\log}_{{2}}{\left({K}\right)}}
 \displaystyle{{\log}_{{2}}{\left({i}\right)}}+{j}\ge{{\log}_{{2}}{\left({K}\right)}}
 \displaystyle{j}\ge{{\log}_{{2}}{\left({K}\right)}}-{{\log}_{{2}}{\left({i}\right)}}
したがって、これを満たす最小のjの値は  \displaystyle{j}=\text{ceil}{\left({{\log}_{{2}}{\left({K}\right)}}-{{\log}_{{2}}{\left({i}\right)}}\right)} です。

ただし、 K \le iであるような場合に注意する必要があります。なぜなら、この場合はコインを振る前にすでにすぬけ君は勝利しているからです。

double p = 0;
foreach(i; 1..N+1) {
	auto j = ceil(log2(K) - log2(i));
	if(i >= K) j = 0;
	double tmp = 1./N * pow(1/2., j);
	p += tmp;
	//tmp.writeln;
}
writefln("%.10f", p);

感想: 式変形を考察用紙でするのが楽しかった。i >= Kであるときに注意。

D - Even Relation

入力:
 N
 u_1\ v_1\  w_1
 u_2\ v_2\  w_2
 \vdots
 u_{N-1}\ v_{N-1}\  w_{N-1}
出力: 条件を満たす塗り分け方
制約:

  • 入力は全て整数である。
  •  1 \le N \le 10^5
  •  1 \le u_i < v_i \le N
  •  1 \le w_i \le 10^9

与えられるグラフがであることに着目しましょう。このような場合は、DFSやBFSによる探索がしやすいです。
一度探索した頂点はもう一度検証しないように注意しましょう。

最初に訪れる頂点はvisitableとします。

ある頂点 Pに着目するとき、隣りあった頂点 Qについて、 PQ間の距離を dとおくと
i)  Pがvisitableである かつ dが偶数 ->  Qはvisitableである
ii)  Pがvisitableである かつ dが奇数 ->  Qはvisitableでない
iii) Pがvisitableでない かつ dが偶数 ->  Qはvisitableでない
iv)  Pがvisitableでない かつ dが奇数 ->  Qはvisitableである

というふうに考えると、visitableであるか否かを参考にしてグラフの色分けをすることができます。

alias Pair = Tuple!(int, "u", int, "v", int, "w");
Pair[] pairs;
Pair[][long] next;
foreach(i; 0..N-1) {
	auto ip = readAs!(int[]), u = ip[0], v = ip[1], w = ip[2];
	pairs ~= Pair(u-1, v-1, w);
	pairs ~= Pair(v-1, u-1, w);
	next[u-1] ~= Pair(u-1, v-1, w);
	next[v-1] ~= Pair(v-1, u-1, w);
}
auto visitable = new bool[](N);
auto visited = new bool[](N);
visitable[0] = true;
long[] queue = [0];

while(queue != []) {
	long i = queue.front;
	queue.popFront;
	if(visited[i]) continue;
	visited[i] = true;
	//i.writeln;
	
	foreach(v; next.get(i, [])) {
		//v.writeln;
		if(((visitable[i] ? 0 : 1) + v.w) % 2 == 0) visitable[v.v] = true;
		else visitable[v.v] = false;
		if(!visited[v.v]) queue ~= v.v;
	}
}
//visitable.writeln;
visitable.map!(i => i ? 0 : 1).each!writeln;

感想: 実装もうちょっとどうにかなりそう

E - 1 or 2

入力:
 N\ M
 X_1\ Y_1\ Z_1
 X_2\ Y_2\ Z_2
 \vdots
 X_M\ Y_M\ Z_M
出力: 必要なコストの最小値
制約:

  • 入力は全て整数である。
  •  2 \le N \le 10^5
  •  1 \le M \le 10^5
  •  1 \le X_i < Y_i \le N
  •  1 \le Z_i \le 100
  •  (X_i, Y_i)の組は互いに異なる。
  • 与えられる入力には矛盾がない(すなわち、条件を満たす A_1, A_2, \dots, A_Nが存在する)。

入力では A_{X_i} + A_{Y_i} + Z_iは偶数である、という情報が与えられる。

ここで、2つの整数 A, Bについて考えてみる。
i)  Aが奇数で Bも奇数のとき  A+Bは偶数
ii)  Aが奇数で Bが偶数のとき  A+Bは奇数
iii)  Aが偶数で Bが奇数のとき  A+Bは奇数
iv)  Aが偶数で Bが偶数のとき  A+Bは偶数

入力で与えられる Z_iには何の意味もない。
ここで注目したいのが、 A,Bのどちらかの偶奇がわかれば、もう片方の偶奇もわかるということ。
だから、 A,B,Cのような3つの整数があったとき、入力でそれぞれつながっているような情報が与えられたならば(例えば A+B B+Cの情報とか、 A+C A+Bの情報など)その塊のうちのどれか一つの数の偶奇が判明すればドミノ倒しのように他の整数の偶奇も判明する。

したがって、与えられる X_i, Y_iの組をグラフの辺と考えて、そのグラフの中にある連結成分の数がそのまま答えになる。
これは、UnionFindやDFSなどが有効に利用できる。この解答ではUnionFindを使うことにする。

auto ip = readAs!(int[]), N = ip[0], M = ip[1];
auto uf = new UnionFind!long(N);
foreach(i; 0..M) {
	auto ip2 = readAs!(int[]), X = ip2[0], Y = ip2[1], Z = ip2[2];
	uf.unite(X-1, Y-1);
}
N.iota.map!(i => uf.root(i) == i).sum.writeln;

UnionFindを使うとき、連結成分の数は、頂点の番号と、その頂点の根の番号が一致する場合の数に等しい。

感想: 終了2分前にこの解法に気づいたが、UFでの連結成分の数え方を知らなかったので提出できなかった。

A: Submission #5448688 - AtCoder Beginner Contest 126
B: Submission #5450291 - AtCoder Beginner Contest 126
C: Submission #5457149 - AtCoder Beginner Contest 126
D: Submission #5468811 - AtCoder Beginner Contest 126
E: Submission #5481438 - AtCoder Beginner Contest 126

AtCoder Beginner Contest 125の解説

A - Biscuit Generator

入力:  A\ B\ C
出力: ビスケットの合計枚数
制約:

  •  1 \le A, B, T \le 20
  •  A, B, T \in \mathbb{N}

 T+0.5秒後まで生産するとありますが、この 0.5は無視してよいです。
 A, 2A, 3A秒後にビスケットが生産されるということは、 A秒毎に B枚のビスケットができるということなので、私たちがよく知っている「道のり=速さ×時間」の要領で答えを求めることができます。求める答えは、
 \displaystyle{\left\lfloor{\frac{T}{{A}}}\right\rfloor}\cdot{B}
になります。

auto ip = readAs!(int[]), A = ip[0], B = ip[1], T = ip[2];
writeln((T / A * B));

感想: ごくふつうのA問題でした。

B - Resale

入力:
 N
 V_1\ V_2\ \cdots\ V_N
 C_1\ C_2\ \cdots\ C_N
出力:  X - Yの最大値
制約:

  •  1 \le N \le 20
  •  1 \le C_i, V_i \le 50
  • 入力は全て整数

 i番目の宝石を手に入れるとき、 +V_iの価値と -C_iのコストを得るため、最終的にはその宝石について V_i - C_iの価値を得ることができます(答えは \displaystyle{X}-{Y}=\sum_{{i}}{\left({V}_{{i}}-{C}_{{i}}\right)}ですから、価値とコストを同一視できます)。

したがって、 V_i - C_i > 0のとき、その宝石を取るのが得です。そのような宝石を全て取れば、最大値を求めることができました。

int res = 0;
foreach(i; 0..N) {
	if(V[i] - C[i] > 0) res += V[i] - C[i];
}
res.writeln;

感想: 実装をミスって少し時間がかかってしまった。

C - GCD on Blackboard

入力:
 N
 A_1\ A_2\ \cdots\ A_N
出力: 書き換えた後の N個の整数のGCDの最大値
制約:

  •  2 \le N \le 10^5
  •  1 \le A_i \le 10^9
  • 入力は全て整数

ある整数を好きな整数に書き換えられるということは、 N個の整数 A_1, A_2, \cdots, A_N全体のGCDをとるとき、その整数についてだけGCDの演算をしないようにすることと同等です。
したがって、 N個の整数それぞれについて、それ以外の整数のGCDをとったときの最大値を求める問題だと言い換えることができます。

そこで、 N個それぞれについてループを回して、それ以外の N-1個の整数のGCDをとってあげればわかる…というような解法は O(N^2 \log A)となりTLEします。(今回の問いの中心です)

ここでGCDという演算がどのような性質を持つのか考えてみると、これは結合法則交換法則が成り立ちます。したがって、 i番目の整数以外のGCDは \displaystyle \gcd{{\left( \gcd{{\left({A}_{{1}},{A}_{{2}},\ldots,{A}_{{{i}-{1}}}\right)}}, \gcd{{\left({A}_{{{i}+{1}}},{A}_{{{i}+{2}}},\ldots,{A}_{{N}}\right)}}\right)}}として求めてもよいことがわかります。ゆえに、前処理として
 \displaystyle{L}_{{i}}={\left\lbrace\begin{matrix}{A}_{{0}}&{\quad\text{if}\quad}{i}={0}\\ \gcd{{\left({L}_{{{i}-{1}}},{A}_{{i}}\right)}}&\text{otherwise}\end{matrix}\right.}

 \displaystyle{R}_{{i}}={\left\lbrace\begin{matrix}{A}_{{{N}-{1}}}&{\quad\text{if}\quad}{i}={N}-{1}\\ \gcd{{\left({R}_{{{i}+{1}}},{A}_{{i}}\right)}}&\text{otherwise}\end{matrix}\right.}

とすると(0-indexed)、 \displaystyle \gcd{{\left({L}_{{{i}-{1}}},{R}_{{{i}+{1}}}\right)}}の最大値を求めればよいことになり、時間計算量は O(N \log A_1 + N \log A_N)とすることができました。

なお、よくある累積和については、元 aに対して必ず逆元 -aが存在するため一つの配列で考えることができますが、GCDという演算においては逆元を考えることができないので、 L, Rとして両方から累積GCDを考える必要がありました。

auto L = new int[](N);
auto R = new int[](N);

L.front = A.front;
R.back = A.back;
foreach(i; 1..N) {
	L[i] = gcd(L[i-1], A[i]);
}
foreach_reverse(i; 0..N-1) {
	R[i] = gcd(R[i+1], A[i]);
}
ulong res;
foreach(i; 0..N) {
	if(i == 0) { res = R[1]; continue; }
	if(i == N-1) { res = max(res, L[N-2]); continue; }
	res = max(res, gcd(L[i-1], R[i+1]));
}
res.writeln;

感想: これは300点の中でもかなり難しい方だと思う(実装は大変ではないが、考察が大変)

D - Flipping Signs

入力:
 N
 A_1\ A_2\ \cdots\ A_N
出力:  \displaystyle{\sum_{{{i}={1}}}^{{N}}}{B}_{{i}}の最大値
制約:

  •  2 \le N \le 10^5
  •  -10^9 \le A_i \le 10^9
  • 入力は全て整数

この問題の操作は、となりあった整数の正負を反転するものですが、f:id:private_yusuke:20190428110528p:plain
このように操作を繰りかえすことで任意の2つの整数の正負を反転させることができます。

したがって、整数列の中の偶数の数を kとすると、 kが偶数の場合は全て正にすることができるので \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}が答えになります。
一方、 kが奇数の場合はどのようにしても1つの整数が負のままとなるので、 \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}-{2}\cdot\min{\left|{A}_{{i}}\right|}を出力すればよいです。

なお、奇数の場合に2回引き算をするのは、 \displaystyle\sum_{{i}}{\left|{A}_{{i}}\right|}の部分で \displaystyle\min{\left|{A}_{{i}}\right|}を足してしまっている分を引かなければならないからです。

ulong cnt = A.count!(i => i < 0);
ulong res = A.map!(i => i.abs).sum;
if(cnt % 2) res -= A.map!(i => i.abs).reduce!min * 2;
res.writeln;

感想: 気づけばすぐに解けそうだった。操作をうまく用いるとどんなことができるか、というところに着目することが大事な問題だった。

A: Submission #5138695 - AtCoder Beginner Contest 125
B: Submission #5140509 - AtCoder Beginner Contest 125
C: Submission #5164574 - AtCoder Beginner Contest 125
D: Submission #5163895 - AtCoder Beginner Contest 125

AtCoder Beginner Contest 122の解説

A - Double Helix

入力:  b
出力: 塩基  b と対になる塩基
制約:

  •  b は文字 'A', 'C', 'G', 'T' のいずれかである。

サンプルに全ての答えが書いてありますね…

switch(b) {
	case "A": writeln("T"); break;
	case "T": writeln("A"); break;
	case "G": writeln("C"); break;
	case "C": writeln("G"); break;
	default: break;
}

感想: かなりA問題らしい問題で好き

B - ATCoder

入力:  S
出力:  Sの部分文字列のうち最長のACGT文字列の長さ
制約:

  •  1 \le |S| \le 10

部分文字列の意味を考えて実装します。

ulong res;
ulong tmp;
foreach(i; S) {
	if(i == 'A' || i == 'T' || i == 'C' || i == 'G') {
		tmp++;
	} else {
		res = max(res, tmp);
		tmp = 0;
	}
}
res = max(res, tmp);
res.writeln;

感想: ループ後のmaxをとる処理を忘れて1WA…とてもかなしい凡ミスをした。

C - GeT AC

入力:
 N\ Q
 S
 l_1\ r_1
 \vdots
 l_Q\ r_Q
出力:  S の先頭から  l_i 文字目から  r_i 文字目までの部分文字列の中に含まれる 'AC' の数
制約:

  •  2 \le N \le 10^5
  •  1 \le Q \le 10^5
  •  |S| = N
  •  1 \le l_i < r_i \le N
  •  S はACGT文字列

 Q 個のクエリが与えられるので、毎回 'AC' を数えていると O(NQ)となりTLEします。

したがって、「先に 'AC' が出てくる回数を数えておいて、各クエリで記憶しておいた回数を使おう!」という方針を考えます。俗にいう累積和です。

arr[i] を「左から  i 番目までの  S に出現した 'AC' の数」とします。

foreach(i; 0..S.length-1) {
	if(S[i] == 'A' && S[i+1] == 'C') {
		arr[i+1] = arr[i] + 1;
	} else arr[i+1] = arr[i];
}

そして、  S l から  r までの 'AC' の数は「arr[r] - arr[l]」で求めることができました。

auto arr = new int[](N);
foreach(i; 0..S.length-1) {
	if(S[i] == 'A' && S[i+1] == 'C') {
		arr[i+1] = arr[i] + 1;
	} else arr[i+1] = arr[i];
}

foreach(i; 0..Q) {
	auto ip2 = readAs!(int[]), l = ip2[0]-1, r = ip2[1]-1;
	writeln(arr[r] - arr[l]);
}

感想: まさに「累積和をやれ」と言わんばかりの問題でした。

D - We Like AGC

入力:  N
出力: 条件を満たす文字列の数を  10^9+7 で割った余り
制約:

  •  3 \le N \le 100

条件を満たさない文字列は、"."を任意の文字として

  • AGC.
  • GAC.
  • ACG.

  • A.GC
  • AG.C
  • .AGC
  • .GAC
  • .ACG

の形で表すことができます。

愚直に全探索すると  O(4^N) になって間に合わないので、DPで  O(N) にします。

dp[n][t1][t2][t3] を「0-indexedでn-4, n-3, n-2番目の文字がt1, t2, t3と並ぶような、長さnの条件を満たす文字列の数」とします。

[t1, t2, t3]が条件を満たさない文字列になるときはdp[n][t1][t2][t3]==0ですから、その場合はすぐにcontinueします。(上で挙げた条件を満たさない文字列の前半ですね!)

そのあと、上で挙げた条件を満たさない文字列の後半にあたるところも同様にします。

条件を満たす文字列のときは、[t1, t2, t3, a]の並びが大丈夫であることがわかっているので、 dp[n+1][t2][t3][a] += dp[n][t1][t2][t3] として遷移を書きます。( 10^9 + 7で割ることを忘れずに)

最終的な答えは、dp[N]の内側にある値の総和になります。

auto dp = new long[][][][](N+1, 4, 4, 4);
dp[0][3][3][3] = 1;

foreach(n; 0..N) foreach(t1; 0..4) foreach(t2; 0..4) foreach(t3; 0..4) {
	if(dp[n][t1][t2][t3] == 0) continue;
	foreach(a; 0..4) {
		char c1 = t1.t, c2 = t2.t, c3 = t3.t, c4 = a.t;
		if([c1, c3, c4] == "AGC") continue;
		if([c1, c2, c4] == "AGC") continue;
		if([c2, c3, c4] == "AGC") continue;
		if([c2, c3, c4] == "GAC") continue;
		if([c2, c3, c4] == "ACG") continue;
		dp[n+1][t2][t3][a] += dp[n][t1][t2][t3];
		dp[n+1][t2][t3][a] %= MOD;
	}
}
long res;
foreach(t1; 0..4) foreach(t2; 0..4) foreach(t3; 0..4) {
	res += dp[N][t1][t2][t3];
	res %= MOD;
}
res.writeln;

感想: これDPだろということだけわかって、その後は椅子を温めた。

A: Submission #4685262 - AtCoder Beginner Contest 122
B: Submission #4688713 - AtCoder Beginner Contest 122
C: Submission #4687776 - AtCoder Beginner Contest 122
D: Submission #4710256 - AtCoder Beginner Contest 122

AtCoder水色になるまでにやったこと

先日のAtCoder Beginner Contest 118で、晴れて水色になることができたので、例によって色が変動したときに執筆されるタイプの記事を書いてみることにします。

灰色のとき

正直なところあまり記憶がありません。初回はABC069、C++で2完(perf: 397)したようです。
真面目に参加しはじめたのは2018年4月ごろからでした。

初回はC++で参加していたようですが、それより後はDを主に使っています。

「蟻本を買いなさい」という天の声が青い鳥を通じて聞こえたので、この頃にバイブルを買いました。しかし、真面目に読まないで「うっわマジでこんな難しいことをやるの??人間こわすぎでしょ」とか思ってた記憶があります。

  • 基本的な文法
  • stdin/stdout の扱い方、入力文字列のparse
  • 配列の使い方

これらの知識を持っていました。今ではhttps://atcoder.jp/contests/APG4bを利用することで上3つよりも多くの基礎を身につけられるようになっているので、初心者の方はぜひ活用してほしいです。

茶色のとき

ABC096でD - Five, Five Everywhereを解いて茶色になりました。茶色の期間は一番短くて、3回のコンテスト分だけでした。灰色のときと、実力はさほど変わっていなかったように思います。

茶色になってから始めたことは、自分が解説できそうな問題はブログで記事にしてみることと、Twitterの界隈に入りこんでみるということでした。記事として一度まとめてみることで、将来似た問題に遭遇したときに対処できる可能性が上がります。また、界隈において強い人が書いた記事や知見、思考、あるいはクソなぞなぞを目にすることで、柔軟な思考ができるようになりました(ほんまか?)。

このとき、競プロにおいて必要な早解き力をつけることを意識していました。レーティングは順位が高ければ高いほど、良い値がつきます。そのため、一秒でも早くコードを書きサンプルをテストすることを頑張りました。

  • A, Bの早解き
  • 整数
  • DFS, BFS
  • set(redBlackTree)
  • map, filterとかそういう数学チックな関数(早解きするとき役立つ)

緑色のとき

沼。今までに参加したコンテストの10~37回、すなわち28回は緑色として出ていました。日付にして6/3〜2/15の期間です。これがとても長くて、心が折れそうになりました。0完太陽をhighestでキメて2ヶ月ぐらい停滞したりね(とてもつらかった)。

しかしながら、停滞による忍耐力はかなりついた気がします(Getting Over Itをプレイしているときと、停滞しているときの気持ちがとても似ていた)。

0完太陽をキメた頃に部長として競プロを布教していたら、ある一人の同校erが始めてくれたので、この人に追いつかれないようにしないと…!というモチベが新たに生まれていたりしました。また、水色への憧れも諦めきれなかったので、それも合わせて高3になる前には絶対なるぞ〜〜と意気があがっていました。やっぱりメンタルは大事だなあという学びを得ました。

整数問題を得意にしたくて、マスター・オブ・整数を購入して解いてみたり、強い人の生態を知りたくて競プロキャンプに参加しました。東工大のOCでも競プロerに会ってみたり。でもこの人たちが僕を抜かしていったので、けっこう精神的ダメージを受けました。あと簡単なミスで通せなかったときなどは、次の日がとても憂鬱だったりしました。しかし諦めたくなかったのでなんとか続けました。
やっているうちに、競プロは経験と知識を頼りにいろんなやり方を考えるのが大事だということがよくわかりました。

あと、色には関係ないですが情報オリンピックの予選に参加してみたのも印象深いです。残念ながら本選には行けませんでしたが、競プロをやっていたお陰でそこそこの点数を取ることができました。

  • 基本的にCまで解く。Dは解けたら解く
  • 再帰
  • 簡単なDP
  • 二分探索
  • エラトステネスのふるい
  • ワーシャルフロイド
  • writerの傾向をつかむ(コラ)
  • map, filter, each, reduce, all, any, groupなどを使いこなす(脳内で考える手続きを言語化するのに役立つ関数たちだと思います)
  • コンテスト中ぐらい自信をもって取り組むこと!
  • 楽しむこと!!

つらいことばっかり書いてしまったんですが、それ以外にもたくさん学ぶことがありました。「数学なんで学んでも将来使わないじゃん」と言う人はたまにいますが、実用例を知ることができた気がしますし、また理数科の課題研究では競プロで得た計算量などの知識を大いに生かして、発表会で優秀賞を受賞することもできました。体育が苦手な自分にとっては、今までの中で一番自分の成果につながった「競技」だといえます(卓球が一応できます)(←非本質情報です)。

まとめ

競プロは解けるときは楽しいし解けないときは楽しくない
だから解けるようになるために精進するのも大事だし、あまり追いすぎて疲れないように程々にやることも必要だと思いました。
もうすぐで高3なので一度休止して受験勉強を頑張ろうと思います。皆さんも程々に。楽しめる範囲で友達と競プロ、あの子と競プロ、部活で競プロをしましょう。

「みんなのプロコン 2019」の解説

A - Anti-Adjacency

入力:  N\ K
出力:  1以上 N以下の異なる整数を、差が 1の整数をともに選ばないように K個選ぶことができるなら'YES'、そうでないなら'NO'
制約:

  •  1 \le N, K \le 100
  •  N, K \in \mathbb{Z}

この問題の一番難しいところは、'Yes'ではなくて'YES'と出力するところです(間違いないね)

… 差が1の整数を選んではいけないので、間をはさみながら整数を選んでいくイメージです。
入力例1では、1以上3以下の異なる整数を、差が1の整数をともに選ばないように選べるか(つまり1,2とか2,3ではなく、1,3のように選べるか)と聞いていますが、これは可能です。

しかしながら、入力例2では不可能になります(どうあがいても、1,2,3,4,5の並びしかない)

 1,2,3,\cdots,Nと続くなかでこの条件を満たして選べる整数の数の限界は \displaystyle{\left\lfloor{\frac{{{N}+{1}}}{{2}}}\right\rfloor}です。

writeln((N + 1) / 2 >= K ? "YES" : "NO");

感想: 'Yes'と'YES'の統一を、どうかお願いします、AtCoder様…(1WA)

B - Path

入力:
 a_1\ b_1
 a_2\ b_2
 a_3\ b_3
出力: すべての道をちょうど1回ずつ通ることですべての街を訪れることが可能ならば'YES'、そうでないなら'NO'
制約:

  •  1 \le a_i, b_i \le 4(1 \le i \le 3)
  •  a_i \ne b_i(1 \le i \le 3)
  • 同じ街の対の間を結ぶ道は複数存在しない
  • どの2つの街の間も、道を何本か通ることで行き来することができる

3つの道の様子を追ってみると、始点と終点の番号が1回、それ以外の点は2回だけ出力に現れればよいことがわかります。
これを満たすかどうかを判定すればよいです。

int[] arr;
foreach(_; 0..3) {
	auto ip = readAs!(int[]), a = ip[0], b = ip[1];
	arr ~= a; arr ~= b;
}
arr.sort();
auto a = arr.group();
auto b = a.map!(i => i[1]);
if(b.count(2) == 2 && b.count(1) == 2) {
	writeln("YES");
} else writeln("NO");

感想: 割と面倒なコードを書いてしまった

C - When I hit my pocket...

入力: K\ A\ B
出力:  K回の操作の後、すぬけ君が持っているビスケットの枚数の最大値
制約:

  •  1 \le K, A, B \le 10^9
  •  K, A, B \in \mathbb{Z}

まず、操作の中で「1枚増やす」というものがあります。
また、「A枚のビスケットを1円に交換する」「1円をB枚のビスケットに交換する」という操作もあります。

ここで、  K+1 < Aのとき、下二つの操作には関与できないので、すぬけ君はビスケットを叩き続けることしかできません。よって、出力は K+1となります。
そうでないとき、まずポケットを A-1回叩いてビスケットを A枚にし、次にビスケット A枚を 1円に交換し、 1円をビスケット B枚に交換することを考えます。

この「ビスケット A枚から 1円  \rightarrow  1円からビスケット B枚」という交換術は、2回の操作が必要です。したがって、この交換術での増分が2以下のとき、わざわざこんなことをする必要もなく、またしてもすぬけ君はビスケットを叩き続けるほうが良いことがわかります。よって出力は K+1になります。
そうでないとき、この交換術では B-A枚ずつ増えていくので、残りの操作回数の偶奇に注意してコードを書きます。(2回ずつの操作をセットとして考えるので、1回あまったらビスケットを最後に叩く)

auto ip = readAs!(long[]), K = ip[0], A = ip[1], B = ip[2];
// ulongだとB-Aでオーバーフローすることがあるので注意
if(K+1 < A || B - A <= 2) {
	writeln(K+1);
	return;
}
K -= A-1;
writeln((B-A) * (K/2) + K%2 + A);

感想: コンテスト中はもっと無駄にwhile使ったりして頑張ってた \displaystyle{O}{\left( \log{{K}}\right)}的解法だったけど、実際数学なので O(1)で解けたなあというお気持ち

D - Ears

入力:
 L
 A_1
 \vdots
 A_L
出力: 必要な操作の回数の最小値
制約:

  •  1 \le L \le 2 \times 10^5
  •  0 \le A_i \le 10^9(1 \le i \le L)
  •  L, A_1, \cdots, A_L \in \mathbb{Z}

コンテスト中に解けなかったので、公式解説の解法を書きます。
数直線上を散歩することについて考えます。
座標 Sで散歩を開始し、座標 Tで終了したとし、また散歩中に訪れた左端の座標を D、右端を Uとすると、

  1.  i \le D 散歩にこない
  2.  D < i \le S 散歩にくる。偶数個の石を得る(0でない)
  3.  S < i \le T 散歩にくる。奇数個の石を得る
  4.  T < i \le U 散歩にくる。偶数個の石を得る(0でない)
  5.  U < i 散歩にこない

の5つの区間が考えられます。(0でない、とするところが0だったら前後との区間の区別ができないので、こういう制約をつけます)

ここで、いい感じにそれぞれの区間の切れ目を全探索すればいけそうって感じますが、それをすると制約からしてTLEは不可避です。したがってDPすることを考えます(DはDPのD)

dp[i][j] を、「マス i以前まで考えた状態で、マス iを含む区間 jになっているときの操作回数の最小値」とします。

また、cost(i, j)を「マス i区間 jに含まれると考えたときにプラスされる操作回数」とします。

そうすると、
 j \le kとして
dp[i+1][k] = min(dp[i+1][k], dp[i][j] + calc(i, k))
という遷移を考えることができます。

最後のマス L区間0〜4のいずれかに含まれるので、出力はdp[L].reduce!minです。

ulong[] A;

ulong cost(ulong i, ulong j) {
	switch(j) {
		case 0, 4:
			return A[i];
		case 1, 3:
			return A[i] == 0 ? 2 : A[i] % 2;
		case 2:
			return (A[i] + 1) % 2;
		default: return 0;
	}
}

void main() {
	auto L = ri;
	A = L.iota.map!(i => readAs!ulong).array;
	auto dp = new ulong[][](L+1, 5);
	foreach(ref v; dp) v[] = INF;
	dp[0][0] = 0;
	foreach(i; 0..L) foreach(j; 0..5) foreach(k; j..5) {
		dp[i+1][k] = min(dp[i+1][k], dp[i][j] + cost(i, k));
	}
	dp[L].reduce!min.writeln;
}

感想: DP難しいけど、理解した後ならよくわかった。

A: Submission #4204208 - Yahoo Programming Contest 2019
B: Submission #4206354 - Yahoo Programming Contest 2019
C: Submission #4251750 - Yahoo Programming Contest 2019
C(コンテスト中): Submission #4212040 - Yahoo Programming Contest 2019
D: Submission #4251409 - Yahoo Programming Contest 2019

AtCoder Beginner Contest 117の解説

A - Entrance Examination

入力:  T\ X
出力: 世界Aで実際に進んでいる時間(絶対誤差と相対誤差は 10^{-3}以下である必要がある)
制約:
 1 \le T \le 100
 1 \le X \le 100

サンプルでエスパーしましょう(は?)

writefln("%.6f", T / X);

感想: エスパー

B - Polygon

入力:
 N
 L_1\ L_2\ \ldots L_N
出力:  N角形が描けるなら'Yes'、そうでないなら'No'
制約:
 3 \le N \le 10
 1 \le L_i \le 100

問題文に定理が書かれているので、これを参考にして実装します。
具体的には、 L_1, L_2, \ldots, L_Nの総和をとり、一番長い辺の長さをそこから引いたものが、一番長い辺より真に大きいなら'Yes'、そうでないなら'No'と出力すればよいです。

if(L.reduce!max < L.sum - L.reduce!max) {
	writeln("Yes");
} else writeln("No");

感想: 定理が書かれてなかったら、めっちゃ点数上がってそうな気がした。

C - Streamline

入力:
 N\ M
 X_1\ X_2\ \ldots\ X_M
出力: 目的を達成するまでに移動を行う回数の最小値
制約:
 1 \le N \le 10^5
 1 \le M \le 10^5
 -10^5 \le X_i \le 10^5
 \displaystyle\forall{i},{j}{\left({\left({i}\ne{j}\right)}\Rightarrow{\left({X}_{{i}}\ne{X}_{{j}}\right)}\right)}

移動と言っているので、まずXをソートし、 \displaystyle{i}{\left({0}\le{i}<{N}-{1}\right)}について \displaystyle{X}_{{{i}+{1}}}-{X}_{{i}}な数列を考えたくなります。
 N \ge Mのときは、 N個のコマによって M個の座標に訪れてしまうことが可能なので、この場合は0と出力すればよいです。

そうでないときは、1個以上のコマを移動する必要があります。

このとき、考えた数列について、大きい順から N要素の総和をとり、 Xの最大値と最小値の差からその総和を引けば、求める操作回数がわかります。

X.sort();
auto arr = new int[](M-1);
foreach(i; 0..M-1) arr[i] = abs(X[i+1] - X[i]);
//X.writeln;
//arr.writeln;
arr.sort!"a > b"();
long tmp;
if(N >= M) {
	writeln(0);
	return;
}
foreach(i; arr[0..N-1]) {
	tmp += i;
}
//tmp.writeln;
writeln(abs(X.reduce!max - X.reduce!min) - tmp);

感想: こういう問題、入力例から何となく解法を考えるのが大事な気がする

D - XXOR

入力:
 N\ K
 A_1\ A_2\ \ldots\ A_N
出力:  fの最大値
制約:
 1 \le N \le 10^5
 0 \le K \le 10^{12}
 0 \le A_i \le 10^{12}

公式解説を読めばわかりますが、難しいので、1から理解した自分が書いてみます。

まず、これは質問ですが、 30213 40214はどちらが大きいでしょうか?
当然 40214ですが、あなたはどのようにして大小を比較したでしょうか。
きっと、5桁目が 3 < 4だからすぐにわかったのだろうと思います。

では、 (10101)_2 (11010)_2は、どちらが大きいでしょうか?
これは (11010)_2ですね。5桁目はどちらも 1なのでまだ大小が確定していませんが、4桁目を見ると 0 < 1より大小が確定します。公式解説では、このことを小難しい書きかたで表わしています。(雰囲気はこんな感じなはず)

この問題では、 X \le Kなる Xについて \displaystyle f{{\left({X}\right)}}=\sum_{{i}}{\left({X}\ \text{ xor }\ {A}_{{i}}\right)}としています。

 X \le Kなので、この条件を満たしている状態を考えて、 Xの値を考えてみます。

 X = Kのとき、特に何も考えず f(K)を求めてみるとよいです。
そうでないとき、Kの2進法表記を考えてみます。
 X < Kが確定するのは、XとKの二進法表記を上から見ていって、あるところで 0 < 1となるときです。
そのため、Kの二進法表記でそこが 1であるとき、そこをXの二進法表記で 0とすることを考えます。そこの桁を i桁目とします。
このとき、Xは iより上の桁はKと等しく、 iより下の桁は貪欲に選ぶことができます。
したがって、下のようなコードを書くことになります。なお、 c_i i桁目が 1である Aの要素の個数を表わしています。

auto c = new ulong[](64);
foreach(v; A) foreach(i; v.bitsSet) c[i]++;
ulong res;
if(K == 0) {
	writeln(A.sum);
	return;
}
// X < K のとき
foreach(i; 0..K.log2.ceil.to!ulong) {
	// Kの二進法表記でi桁目が1でなければcontinue(X < Kにしたいので)
	if(!(K & (1UL << i))) continue;
	ulong X = K;
	X &= ~(1UL << i); // Xのi桁目を0にする(i桁目でX < Kを確定させたいので)
	foreach(j; 0..i) {
		if(c[j] > N-c[j]) { // その桁を1にしてxorしたほうが都合がよいのか
			X &= ~(1UL << j);
		} else X |= (1UL << j);
	}
	ulong tmp;
	foreach(v; A) {
		tmp += v ^ X;
	}
	res = max(res, tmp);
}
ulong tmp;
foreach(v; A) { // X = K のとき
	tmp += v ^ K;
}
res = max(res, tmp);
res.writeln;

感想: これを理解したつもりでコードを書くと、X = Kの場合を忘れていてWAを連発したりした。
本番では嘘解法(上から貪欲に決めるとAC)が通るようになっていたのだが、シフト演算に慣れていないせいで1 << aと書いてしまい、1UL << aと書けばパフォ1600だったのに俺は何をオーバーフローさせてんだ…いやでもこれ嘘だしなあ…という微妙な気持ちになった。(どちらかというとレート上昇を逃したのが悔しい)
後日、しっかり本当の解法を理解しようと努めることによって、桁を上から見ることについて少しはわかったのではないかと思う(桁DPで解く方法についても今後考えたい)

A: Submission #4152674 - AtCoder Beginner Contest 117
B: Submission #4153387 - AtCoder Beginner Contest 117
C: Submission #4158140 - AtCoder Beginner Contest 117
D: Submission #4184409 - AtCoder Beginner Contest 117
D(別解法): Submission #4183962 - AtCoder Beginner Contest 117
D(嘘解法): Submission #4167642 - AtCoder Beginner Contest 117

AISing Programming Contest 2019の解説

A - Bulletin Board

入力:
 N
 H
 W
出力: 貼り出す場所の選び方の場合の数
制約:
 \displaystyle{H},{W},{N}\in\mathbb{Z}
 \displaystyle{1}\le{H},{W}\le{N}\le{100}

f:id:private_yusuke:20190112231330p:plain
Aの絵

writeln(max(0, N - H + 1) * max(0, N - W + 1));

感想: これ最初戸惑った。解説は絵を描きたかっただけ。

B - Contests

入力:
 N
 A\ B
 \displaystyle{P}_{{1}}\ {P}_{{2}}\ \ldots\ {P}_{{N}}
 \displaystyle{N},{A},{B},{P}_{{1}},{P}_{{2}},\ldots,{P}_{{N}}\in\mathbb{Z}
出力: コンテストを実施できる最大の回数
制約:
 \displaystyle{3}\le{N}\le{100}
 \displaystyle{1}\le{P}_{{i}}\le{20}\ {\left({1}\le{i}\le{N}\right)}
 \displaystyle{1}\le{A}<{B}<{20}

問題文より、与えられた問題は3つのパターンに分類することができます。

  •  \displaystyle{P}_{{i}}\le{A}
  •  \displaystyle{A}+{1}\le{P}_{{i}}\le{B}
  •  \displaystyle{B}+{1}\le{P}_{{i}}

一度のコンテストでは、それぞれの分け方から一問ずつ出題されるため、どんどん消費されていきます。
したがって、一番最初に消費しきってしまうグループの値を出力すればよいです。

ulong a = P.filter!(i => i <= A).array.length;
ulong b = P.filter!(i => A+1 <= i && i <= B).array.length;
ulong c = P.filter!(i => i >= B + 1).array.length;
writeln(min(a, b, c));

感想: なぜか問題を読むのに時間がかかった。風呂上がって髪を乾かした後、もう20秒しかない状態でコンテストに参加したので、10分ぐらい上裸だった。そんな状況でACできたので自分を称えたい(は?)

C - Alternating Path

入力:
 H\ W
 S_1
 S_2
 \vdots
 S_H
出力: 条件を満たすものの個数
制約:
 \displaystyle{1}\le{H},{W}\le{400}
 \displaystyle{\left|{S}_{{i}}\right|}={W}\ {\left({1}\le{i}\le{H}\right)}
 \displaystyle{i}\ {\left({1}\le{i}\le{H}\right)}に対して、文字列 S_iは文字'#'と文字'.'だけからなる。

まず、愚直に全探索することを考えてみる( \displaystyle{\left({a},{b}\right)}\to{\left({c},{d}\right)}の移動を、すべての a,b,c,dについて考える)と、 \displaystyle\text{O}{\left({W}^{2}{H}^{2}\right)} \displaystyle{400}^{4}={25600000000}となり、 \displaystyle{{\log}_{{10}}{\left({25600000000}\right)}}\approx{10.4082399653}なので間に合いません。
したがって、どうにか計算量を落としたい気持ちになります。
ここで、入力例 1を画像にしてみると、こんな感じになります。

f:id:private_yusuke:20190112233125p:plain
Bの絵1

それぞれの'#'から、隣りあった'.'に行けることは問題文からわかります。
問われているのは、'#'から'.'に行ける場合の数です。

f:id:private_yusuke:20190112233615p:plain
Bの絵2

例えば、こういうふうに \displaystyle{\left({1},{2}\right)}\to{\left({3},{3}\right)}と行くことができます。

f:id:private_yusuke:20190112235228p:plain
Bの絵3

こうやって見ると、通うことのできる範囲にある'#'と'.'の個数をかけ算すればよくね?ということに気づきます。これは考えてみるとわかります。
よって、まずは'#'のあるところの座標から探索することにします。
そして、それぞれ問題文の条件を満たすようにDFSで探索し、通うことのできる範囲をしらみつぶしに調べます。その間に計算した座標については訪問済みフラグを立てておき、次は計算をしないように管理します(これで計算量が減ります)。
こうすることで、 \displaystyle\text{O}{\left({H}{W}\right)}で計算が終わります。よってTLEを防ぐことができました。

int[] dy = [1, 0, -1, 0], dx = [0, 1, 0, -1];
Pair[] stack;
foreach(i, iv; S) foreach(j, jv; iv) {
	if(jv == '#') stack ~= Pair(i, j);
}
ulong res;
bool[][] done = new bool[][](H, W);

//ulong res2;
while(stack != []) {
	auto p = stack.front;
	stack.popFront;
	if(done[p.y][p.x]) continue; // 計算量が減るポイント
	Pair[] stack2;
	stack2 ~= Pair(p.y, p.x);
	ulong wh, bl;
	
	while(stack2 != []) {
		auto p2 = stack2.front;
		stack2.popFront;

		foreach(k; 0..4) { //周囲4マスを探索します
			auto ry = p2.y + dy[k];
			auto rx = p2.x + dx[k];
			if(0 <= ry && ry < H && 0 <= rx && rx < W && S[ry][rx] != S[p2.y][p2.x] && !done[ry][rx]) {
				if(S[ry][rx] == '.') { res++; wh++; }
				else bl++;
				stack2 ~= Pair(ry, rx);
				done[ry][rx] = true;
			}
		}
		done[p2.y][p2.x] = true;
	}
	res += wh * bl; // 通える範囲にある'#'と'.'の個数の積をとり答に加算する
}
res.writeln;

感想: この発想が出て30分は、結局 \displaystyle\text{O}{\left({H}^{2}{W}^{2}\right)}になってしまう別のコードを書いてしまい、学校の競プロerに抜かされてしまった。悔しい。でも解けたのでオッケーです