2020-04-19

AtCoder Beginner Contest 163の解説

A - Circle Pond

入力: $R$
出力: 半径 $R$ の円の周長
制約: $1 \le R \le 100$
求めるものは、 $2 \pi R$ です。

auto R = readAs!real;
writeln(2*R*PI);

感想: "%.4f" とかしなくても大丈夫です。

B - Homework

入力:
$N\ M$
$A_1\ \dots\ A_M$
出力: 高橋君が遊ぶことのできる日数、または、'-1'
制約:

$1 \le N \le 10^6$
$1 \le M \le 10^4$
$1 \le A_i \le 10^4$

複数の宿題を同日にすることはできないので、全ての宿題を終わらせるのに必要な日数は $\displaystyle{S}=\sum_{{i}}{A}_{{i}}$ です。
したがって、 $N - S$ が非負ならその値、負なら $-1$ が答えです。

auto ip = readAs!(int[]), N = ip[0], M = ip[1];
auto A = readAs!(int[]);
auto S = A.sum;
if(N - S < 0) writeln(-1);
else writeln(N-S);

感想: やるだけ。

C - management

入力:
$N$
$A_2\ \dots\ A_N$
出力: 各社員に直属する部下の人数
制約:

$2 \le N \le 2 \times 10^5$
$1 \le A_i \le i$

m[社員A] = 社員Aの直属の部下の配列として考えます。

auto N = ri;
auto A = readAs!(int[]);
int[][] m = new int[][](N);
foreach(i, v; A) {
	m[v-1] ~= i.to!int;
}
foreach(i; 0..N) {
	m[i].length.writeln;
}

感想: C問題にしては簡単？

D - Sum of Large Numbers

入力: $N\ K$
出力: 条件を満たすものの個数 $\mod (10^9+7)$
制約:

$1 \le N \le 2 \times 10^5$
$1 \le K \le N+1$
入力は全て整数

まず、 $10^{100}$ について考えてみます。 $N$ の最大値は $2 \times 10^5$ であるから、1からNの整数の総和の最大値は $\displaystyle\frac{1}{{2}}\cdot{\left({2}\cdot{10}⁵\right)}\cdot{\left({2}\cdot{10}^{5}+{1}\right)}={20000000000}+{100000}\stackrel{\sim}{=}{10}^{{{10.3010321671}\ldots}}<{10}^{{{100}}}$ です。したがって、 $10^{100}$ に対して、選んだ整数の総和が影響しないことがわかります。
また、 $X = 10^{100}$ とおくと、 $k$ 個の数を選ぶときの和としてあり得るものは $\displaystyle{k}\times{X}+\square$ で表されます。したがって、これらより「それぞれの $k$ で作れる和は、他の $k$ の値のときと被ることはない」といえます。
これ以降は、 $10^{100}$ のことを無視します。

$\displaystyle{S}{\left({n}\right)}=\frac{1}{{2}}\cdot{n}\cdot{\left({n}+{1}\right)}$ とします。
$k$ 個の数を選ぶとき、その和としてあり得るものの最小値は、 $S(k-1)$ です。
$k$ 個の数を選ぶとき、その和としてあり得るものの最大値は、 $S(N) - S(N-k)$ です。
したがって、 $k$ 個の数を選ぶとき、その和としてあり得るものの個数は、 $\displaystyle{S}{\left({N}\right)}-{S}{\left({N}-{k}\right)}-{\left({S}{\left({k}-{1}\right)}-{1}\right)}$ です。
実装上は、 $K \le k \le N$ でこれらの値を求め、最後に $k = N+1$ の分の $1$ を答えに足します。

auto ip = readAs!(int[]), N = ip[0], K = ip[1];

long su(ulong n) {
	return n * (n + 1) / 2;
}

long res;
const long MOD = 1000000007;
foreach(k; K..N+1) {
	auto m = su(N) - su(N-k) - su(k-1);
	res += m+1;
	res %= MOD;
}
(res+1).writeln;

感想: 添字ゲームに時間をかけすぎた。

A: Submission #12082896 - AtCoder Beginner Contest 163
B: Submission #12082483 - AtCoder Beginner Contest 163
C: Submission #12092478 - AtCoder Beginner Contest 163
D: Submission #12130748 - AtCoder Beginner Contest 163

2020-03-29

AtCoder Beginner Contest 160の解説

A - Coffee

入力: $S$
出力: $S$ がcoffeeに似ている場合は 'Yes' を、そうでない場合は 'No' を
制約: $S$ は長さ $6$ の英小文字からなる文字列

素直に実装。

auto S = readln.chomp;
if(S[2] == S[3] && S[4] == S[5]) writeln("Yes");
else writeln("No");

感想: かんたん

B - Golden Coins

入力: $X$
出力: 嬉しさの最大値
制約:

$0 \le X \le 10^9$
$X$ は整数

できるだけ500円玉に両替し、余ったお金をできるだけ5円玉に両替します。

auto X = readln.chomp.to!int;
ulong res;
while(X >= 500) {
	res += 1000;
	X -= 500;
}
res += (X / 5) * 5;
res.writeln;

感想: 割り算と余りをうまく使えば一行でも解けますね。

2020-03-01

AtCoder Beginner Contest 157の解説

A - Duplex Printing

入力: $N$
出力: 必要な最小の紙の枚数
制約:

$N$ は整数
$1 \le N \le 100$

$\displaystyle{\left\lceil{\frac{N}{{2}}}\right\rceil}$ ですね。（2で割って切り上げ）

ceil(N.to!float / 2).writeln;

ちなみに、

writeln((N+1)/2)

でもいけると思います。
感想: 切り上げ時は浮動小数点数に変換させることを忘れないように。

B - Bingo

入力:
$\displaystyle{A}_{{{1},{1}}}\ {A}_{{{1},{2}}}\ {A}_{{{1},{3}}}$
$\displaystyle{A}_{{{2},{1}}}\ {A}_{{{2},{2}}}\ {A}_{{{2},{3}}}$
$\displaystyle{A}_{{{3},{1}}}\ {A}_{{{3},{2}}}\ {A}_{{{3},{3}}}$
$N$
$b_1$
$\vdots$
$b_N$
出力: ビンゴが達成されているならば 'Yes' を、そうでないならば 'No'
制約:

入力は全て整数
$\displaystyle{1}\le{A}_{{{i},{j}}}\le{100}$
$\displaystyle{A}_{{{i}_{{i}},{j}_{{1}}}}\ne{A}_{{{i}_{{2}},{j}_{{2}}}}\ {\left({\left({i}_{{1}},{j}_{{1}}\right)}\ne{\left({i}_{{2}},{j}_{{2}}\right)}\right)}$
$1 \le N \le 10$
$1 \le b_i \le 100$
$\displaystyle{b}_{{i}}\ne{b}_{{j}}\ {\left({i}\ne{j}\right)}$

ビンゴカードの数字の羅列を一次元配列に入れることを考えてみました。

0 1 2
3 4 5
6 7 8

のように添字を対応させました。
すると、ビンゴであるためには縦、横または斜めの列に穴が開いていればよく、これらの列は
[0,1,2],[3,4,5],[6,7,8],[0,3,6],[1,4,7],[2,5,8],[0,4,8],[2,4,6]
で表すことができます。

auto arr2 = new bool[](9);
foreach(i; 0..N) {
	auto b = ri;
	foreach(j; 0..9) {
		if(A[j] == b) arr2[j] = true;
	}
}
auto arr = [
	[0,1,2],
	[3,4,5],
	[6,7,8],
	[0,3,6],
	[1,4,7],
	[2,5,8],
	[0,4,8],
	[2,4,6]
];
foreach(v; arr) {
	bool flag = true;
	foreach(k; v) {
		if(!arr2[k]) flag = false;
	}
	if(flag) {
		writeln("Yes");
		return;
	}
}
writeln("No");

感想: 実装をちょっとだけ頑張る問題で、ABC向きだったと思います。

C - Guess The Number

入力:
$N\ M$
$s_1\ c_1$
$\vdots$
$s_M\ c_M$
出力: 条件を満たす最小の整数が存在するならそれを、存在しないならば '-1'
制約:

入力は全て整数
$1 \le N \le 3$
$0 \le M \le 5$
$1 \le s_i \le N$
$0 \le c_i \le 9$

制約より、全探索で十分高速に解けます。したがって、0から999までの整数を下から検証していって、条件を満たす整数があればそれを出力して終了するプログラムを作ることを考えます。なければ '-1' を出力です。
0から999までの検証する整数を文字列に変換したものを $S$ とします。
一つ目の条件「十進表記で丁度 $N$ 桁である。」は、文字列 $S$ の長さから簡単に確認できます。
二つ目の条件「左から数えて $s_i$ 桁目は $c_i$ である。 $(i = 1, 2, \dots, M)$ 」は、文字列 $S$ の $s_i - 1$ 番目の文字が $c_i$ であるか調べればよいです。(0-indexed)

int[] S, C;
foreach(i; 0..M) {
	auto ip2 = readAs!(int[]), s = ip2[0], c = ip2[1];
	S ~= s;
	C ~= c;
}
foreach(i; 0..(10 ^^ (N))) {
	auto st = i.to!string;
	if(st.length != N) continue; // 一つ目の条件
	bool flag = true;
	foreach(k; 0..M) { // 二つ目の条件
		if(!(st[S[k]-1] - '0' == C[k])) flag = false;
	}
	if(flag) {
		writeln(i);
		return;
	}
}
writeln(-1);

感想: 全探索するだけですが、苦戦していた方が多かったようでした。制約をよく読んで簡単に考えられると良かったかもしれません。

D - Friend Suggestions

入力:
$N\ M\ K$
$A_1\ B_1$
$\vdots$
$A_M\ B_M$
$C_1\ D_1$
$\vdots$
$C_K\ D_K$
出力: 人 $i = 1, 2, \dots, N$ にとっての友達候補の数
制約:

入力は全て整数
$2 \le N \le 10^5$
$0 \le M \le 10^5$
$0 \le K \le 10^5$
$1 \le A_i, B_i \le N$
$A_i \ne B_i$
$1 \le C_i, D_i \le N$
$C_i \ne D_i$
友達関係かつブロック関係であることはない
一つの友達関係、またはブロック関係が重複して入力に表れることはない

「友達候補」とは、

自分自身は友達候補にならない
ブロック関係にある人同士ではない
友達関係にある人同士ではない
人 $A$ さんと $B$ さんがいたとき、 $A$ さんの友達の友達の……の友達が $B$ さんである

……と定義されます。（厳密な定義は問題文を読んでください）

入力例3をノートに描いてみると、人 $i$ にとっての友達候補の数は、

(人 i が友達経由で繋がっている人たちの数)
- (人 i が友達経由で繋がっている人たちの中で友達関係にある人の数)
- (人 i が友達経由で繋がっている人たちの中でブロック関係にある人の数)
- (自分自身の数(つまり 1))

で求められることがわかります。人を頂点、友達関係を辺とした無向グラフを考えると、これは

(頂点 i の連結成分の大きさ)
- (頂点 i の次数)
- (頂点 i と同じ連結成分に含まれている頂点 j で、頂点 i と頂点 j がブロック関係にあるような j の数)
- 1

と言い換えられます。「連結成分の大きさ」や、「同じ連結成分に含まれているか」を高速に判定するため、UnionFindを用いました。

auto friendUF = new UnionFind!int(N);
int[][] farr = new int[][](N, 0); // farr[i]: 頂点 i と友達関係にある頂点の配列
int[][] barr = new int[][](N, 0); // barr[i]: 頂点 i とブロック関係にある頂点の配列

foreach(i; 0..M) {
	auto ip2 = readAs!(int[]), A = ip2[0], B = ip2[1];
	friendUF.unite(A-1, B-1);
	farr[A-1] ~= B-1;
	farr[B-1] ~= A-1;
}
foreach(i; 0..K) {
	auto ip3 = readAs!(int[]), C = ip3[0], D = ip3[1];
	barr[C-1] ~= D-1;
	barr[D-1] ~= C-1;
}

ulong[] res;
foreach(i; 0..N) {
	auto n = farr[i].length;
	auto tmp = friendUF.size(i) - n;
	foreach(v; barr[i]) {
		if(friendUF.same(v, i)) tmp--;
	}
	res ~= (tmp - 1);
}
writefln("%(%d %)", res);

感想: UnionFind の良い練習問題では？と思いました。

A: Submission #10426662 - AtCoder Beginner Contest 157
B: Submission #10431636 - AtCoder Beginner Contest 157
C: Submission #10435013 - AtCoder Beginner Contest 157
D: Submission #10448653 - AtCoder Beginner Contest 157

2020-03-01

AtCoder Beginner Contest 015のC問題「高橋くんのバグ探し」

C - 高橋くんのバグ探し

入力:
$N\ K$
$\displaystyle{T}_{{{1},{1}}}\ {T}_{{{1},{2}}}\ \ldots{T}_{{{1},{K}}}$
$\displaystyle{T}_{{{2},{1}}}\ {T}_{{{2},{2}}}\ \ldots{T}_{{{2},{K}}}$
$\displaystyle\vdots$
$\displaystyle{T}_{{{N},{1}}}\ {T}_{{{N},{2}}}\ \ldots{T}_{{{N},{K}}}$
出力: 条件を満たすなら 'Found' 、そうでなければ 'Nothing'
制約:
$1 \le N \le 5$
$1 \le K \le 5$
$\displaystyle{0}\le{T}_{{{i},{j}}}\le{127}$

入力の下 $N$ 行のそれぞれから、整数を一つずつ選びます。選ばれた整数全ての排他的論理和(XOR)の値が $0$ になるような組があったら 'Found' 、そうでなければ 'Nothing' を出力します。

この問題で難しいのは、各行から整数を選んでいくところです。簡単に考えられる方法としては、 $N$ 重ループを書くことで全探索することが挙げられますが、 $N = 1, 2, 3, 4, 5$ それぞれの場合について実装するのは大変です（仮に $N = 100$ のときも動くプログラムのことを考えると、私は正気を保ちつつコードを書ける自信がありません）。このような場合、再帰関数を実装するのが正攻法です。
ここでは、「配列を受け取り、その長さが $N$ より小さいときは配列に $\displaystyle{0},\ {1},\ \ldots,\ {K}-{1}$ のいずれかを追加する。そうでないときは、その配列を用いて排他的論理和の値の判定を行い、 XOR が 0 になる組があれば true を返す」関数を考えます。
一つの関数を実装することで、 $K^N$ 通りの整数の組を検証できているところがポイントです。

なお、D言語では arr ~ elem で「配列 arr の末尾に要素 elem を追加した配列」を得ることができます。
また、 foreach(i, v; arr) では i に添字、 v に arr[i] が代入されています。

void main() {
	/* 入力 */
	auto ip = readAs!(int[]), N = ip[0], K = ip[1];
	auto T = readMatrix!int(N, K);

	bool check(int[] arr) {
		if(arr.length < N) {
			foreach(i; 0..K) {
				if(check(arr ~ i)) return true;
			}
			return false;
		}
		int tmp = 0;
		foreach(i, v; arr) {
			tmp ^= T[i][v];
		}
		return tmp == 0;
	}

	if(check([])) writeln("Found");
	else writeln("Nothing");
}

一つでもXORが 0 になる組がある場合は 'Found' になることに注意して実装します。
一文にまとめると「再帰関数を書いて深さ優先探索」です。

感想: AtCoder Problems の Recommendations から一問解いてみました。Difficulty は 1172 となっていますが、現在のABCで出題したらきっと茶パフォ程度になるのかな〜と思います。

解答: Submission #10405209 - AtCoder Beginner Contest 015

2020-02-02

弐寺とBMS練習のための7鍵コントローラーを作った

弐寺のコントローラー、高いんですよね。自作しましょう。
本当は皿を付ける予定で、5鍵コンも配置場所も用意してあるのですが、面倒なのでまだやっていません。このため、タイトルは7鍵コントローラーと書いています。

ゲーセンじゃん pic.twitter.com/EGZBYcxlnO
— public_yusuke (@public_yusuke) January 26, 2020

動機
前準備
- 材料調達
制作開始！
- 台に穴開ける
- ボタンを付ける
- はんだ付けする
- プログラムを書く
- 台に足をつける
完成
感想
追記(2020/02/04) バネ切りについて

動機

まず自宅学習期間なるものが高校にはあって、これは受験生が様々な大学の試験に挑戦する期間です。私は推薦入試で合格したので、この期間は全て暇な時間になってしまいました。そのため、大学に入る前に何かやっておきたいな〜と思って取り組んでみました。

なお、私は本家SP5段の人です。皿複合が難しすぎるだろ、あのゲーム……。45クレで5段に合格し、そこからこれ書いてる時点で累計86クレやったんですが、全く希望の光は見えません。皿を回せる人間になりたいね。

前準備

めんどくさかった。だいたい7500円ぐらいで全部調達した。

2019-12-23

筑波大学情報学群情報科学類令和元年度公募推薦受験記

こんにちは、p(rivate|ublic)_yusukeです。せっかくの機会であることも考え受験記を書くことにしました。合格したので。

なぜ推薦入試を受けたか
- AC入試
推薦、受けるぞっ！
- 評定平均が0.1足りねえ！
当日
- 筆記試験
- 面接
- 試験終了後
結果発表
まとめ
開示について（2021/03/10 19:12 追記）

なぜ推薦入試を受けたか

模試の帰りに本屋に寄ったとき、推薦入試の赤本が置いてありました。たまたまそれを読んだときに英語と数学の融合問題が出題されていた（しかも全然難しくない！）ことがわかり、自分に合っているなと思い挑戦しました。2018年度はcountable infinityに関する英文が載っていて、趣味で勉強していた内容がそのまま出ていたためかなりモチベが出たことも一つの理由です。

AC入試

実は以前、AC入試（アドミッションセンター入試、いわゆるAOのようなもの）を受けていたのですが、そこでは一次の書類選考で落とされてしまいました。文字数自由の自己推薦書はうまい具合にまとめられたのですが、志願理由書の押しが弱かったのかなと思っています。またそのときはパソコン甲子園本選出場も決まっていなかったので、実績が足りなかったことも可能性として挙げられます。