今年の振り返り2020

この記事はcoins20 Advent Calendar 2020の2日目の記事ですが、12/3 に投稿されました。

adventar.org

自分についての振り返りをするだけの記事です。

去年までのこと

大学に合格した。

1月

年越しの瞬間は中学校の友達とお寺に行っていた。
https://twitter.com/public_yusuke/status/1212025625256480773

1/2 は箱根駅伝筑波大学が26年ぶりに出場する日だったので見に行った。
https://twitter.com/public_yusuke/status/1212518746192891905

PCK 本選の成績書が来た。
https://twitter.com/public_yusuke/status/1217648304365830149

2月

弐寺のコントローラを自作した。

3月

一般入試に合格した人が 3/7 からツイッターで合格ツイートをし始めたので捕捉していた。その3日後には Minecraft を一緒にやっていた。

WORD 編集部の部屋に興味があったので、3/13 に初めて大学に行く。確かその日はつけめん・まぜそばむじゃきに先輩と行った。

コロナ禍におけるコミュニティ

3/8 に coins20 のための Discord サーバーが建つ。その後、有志の手によってcoins20 であることを証明できた人のみがサーバーで十分な権限を与えられるような環境が整備される。これのおかげでコロナ禍の中でもオタクとのコミュニケーションができるようになってとても良かった。
また、プライベートな Scrapbox に履修の方法や科目の内容などを有志がまとめてくれた。これのおかげで、何か大学に関連して気になることがあればそこを覗けばだいたい載っているという状況ができた。

4月

オンライン授業

大学のオンライン授業が始まった。レポートを LaTeX組版して提出しても良いというところに最初は大変嬉しさを感じた(字を書くよりもキーボードを叩いた方が楽かつ体裁が良くなる)。SATySFi でレポートを書いてみたりもした(有志によるテンプレ)。
朝起きなくて済むというのは予想以上に楽だったし、授業動画を好きなタイミングで見直したりできるのは普通に嬉しかった。

coins20 のオタクに影響されて C コンパイラを書いてみたくなったので D 言語で途中まで実装した(ポインタの加算と減算までで更新が止まっている……)。

5月

某最大勢力の日本人向け Mastodon インスタンスの運営が終わるかもみたいな話が一瞬流れて、エェ~あのインスタンスの人間が外に流出したらカオスなことになるじゃん……と心配してたけど、確か社長が女装してる会社?に移管されてそうならなくなったと聞き安心した記憶がある*1

情報科学類には情報科学特別演習という、自分でやりたいテーマに関連する分野を専門としている教員の方にアドバイザとして9ヶ月ぐらい面倒をみてもらうことができる科目がある。私はここで「自作 SAT ソルバーの制作」をテーマとした。理由としては、それなりに大きいプログラムを書いてみる経験や、英語の論文を読解して実装に落としてみる経験をしてみたかったとか、数学と計算機が関係しあうようなものに挑戦してみたかったという気持ち他2件があったため*2

大学に申請を出すと G Suite for Education*3 のアカウントが貰えることを知り、その日に手続きをした。それからはこいつをヘビーに利用させてもらっている。

6月

Oculus Rift S を購入した。VRChat に連日ログインすることもあったが、基本的には Beat Saber にドハマリし、今も一週間に一度以上は継続してプレイしている。VRChat で日本人に話しかけるのはちょっと苦手だったので、英語で別の国の人と会話することが多かったかも*4。VRC 沼にはハマらなかったものの仮想空間であれこれ触ったり動いたりするのは楽しかった。

7月

同級生に SKK を布教した覚えがある。

SAT ソルバーをバグらせまくっててこの頃がまあまあ大変だった。

coins20LT

誰かが LT やりたくない?と話したので、7月中旬ごろに内輪での LT 大会が開かれた。自分は LT で発表したことがなかったので良い機会だと思って SAT ソルバーの DPLL アルゴリズムについてまとめて話した。
ちなみに LT は Lightning Talk の略であるが、ここではどの発表も20分ぐらいの長さだった。ライトニングって何だっけ……。という気持ちにもなるが、銘々の興味について熱心に話す会として中身のある発表がたくさん聞けて楽しかった。
ちなみに今でも月イチぐらいのペースで開催されていて、すでに5回も開催されている。

8月

coins20 Discord が過疎る。

Bob's 系の MOD が導入された Factorio 鯖を建てて友達と一日中遊んだりした。ロケットを待機時間なしで連続して飛ばせるようになった途端飽きた。

大学のオープンキャンパス(夏の大学説明会)がオンラインで開催されたので質問に答える係として参加した。

午後10時から4時間半ぐらい Beat Saber を連続プレイした日があった(何?)。

春ABC モジュールの期末試験が終わり、様々な科目の成績が発表された。いい感じでよかった。

9月

3年前の coins のオープンキャンパスのときに前で喋っていた先輩に会い、初めて大学にある研究室に足を運んだ。その後に情報科学特別演習でお世話になっている教員の研究室にも行ったりした。Thinkpad と HHKB が好きな人が多いんだなと思った。

video2asciis というものを作った。これで手元にある好きな動画を変換してみたら楽しかった。詳細はこちら
github.com

10月

録画鯖を Raspberry Pi で構築した。

度重なる生活習慣の崩壊によりついに自律神経が壊れ、2週間ぐらい体調が悪い状況が続いた*5

11月

19歳になった。たくさんのオタクにプレゼントを頂き、今では自分のアパートで新しいサーバーや RTX1200 が動いていたり、BS アンテナが置いてあったりする。他にも技術書や野菜ジュース、ポッキー、DEOCO、火打ち石と火吹き棒、新書、気象計測キット、チャイナドレス、猫耳なども貰った。お返しを考えないとね……。
ここでCoq/SSReflect/MathCompによる定理証明を貰い、定理証明に興味が出た。以前にも Coq を少しだけ触ったことがあるが証明図との対応などは全然わかっていなかったので諸々の概念を理解しながら実践を続けた。久々に夢中になれるものを見つけられた。

情報科学類誌 WORD で SAT ソルバーについての記事を書いた*6。WORD に寄稿することが大学に入る前からの夢だったので嬉しかった。

12月

これを記述しているのが 12/3 で、まだ何も起きていない。

まとめ

コロナ禍の中でもたくさんの人々とやりとりができて刺激的な一年だった。高校までとは違ってコンピュータをカタカタするのが大好きな人ばかりが集まっているために変な文脈を共有できることが多くて楽しかった。また、自分が深く掘り下げたことのなかった分野に詳しい人もいて、そういった方々の影響を受けて本格的に始めたこともいくつかあった。大学っていいな!

最後に、coins20 の人はぜひ下記のアドベントカレンダーに参加しようね!
adventar.org

*1:そんなこともあったね~

*2:また別記事で詳しく書いたりするかもしれない

*3:無制限ドライブがいつまでも続くのか最近ちょっと心配です……

*4:非日常感を味わいたかった

*5:病院に行ったところ某ウイルスとは関係なく本当に自律神経失調症による症状だったとわかっている

*6:もうちょっとしたら公開されると思う

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

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;

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

続きを読む

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

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

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

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


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

動機

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

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

前準備

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

続きを読む

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

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

  • なぜ推薦入試を受けたか
    • AC入試
  • 推薦、受けるぞっ!
    • 評定平均が0.1足りねえ!
  • 当日
    • 筆記試験
    • 面接
    • 試験終了後
  • 結果発表
  • まとめ

なぜ推薦入試を受けたか

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

AC入試

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

推薦、受けるぞっ!

そもそも筑波大学に行きたかったのは、

続きを読む