終点枕崎

プログラミングとvimと音楽と地理

ABCに初参加した - 僕と競プロ

11/4の AtCoder Beginner Contest (ABC)に参加してきました。ABCはAtCoderが主催するプログラミングコンテストで、100分で4問、主に競プロ初心者を対象としています。

A問題

マス目の数が 2 x 3 で固定だったのでナイーブに実装しました。

#include <cstdio>
#include <cstdlib>

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repr(i, a, b) for(int i = (a); i >= (b); i--)
#define range(x) begin(x), end(x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int iinf = 1 << 29;
const ll linf = 1l << 61;

int main(int argc, char* argv[])
{
	char a[2][4];
	rep(i, 0, 2)
	{
		scanf("%s", a[i]);
	}
	if(a[0][0] == a[1][2] && a[1][1] == a[0][1] && a[0][2] == a[1][0])
	{
		printf("YES\n");
	}
	else
	{
		printf("NO\n");
	}
	return 0;
}

B問題

pow 使ってときました。模範解答は線形探索してたので、この解き方はちょっとずるかったかも。usingしてるのに、std::powとか頭悪いことしてます。

#include <cstdio>
#include <cmath>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

int main(int argc, char* argv[])
{
	ll N;
	scanf("%lld", &N);
	ll s = std::pow(N, 0.5);
	printf("%lld", s * s);
	return 0;
}

C問題

サイズの小さい順にソートして、累積和 + 動的計画法 でときました。ソートを除けばO(n)。
解説は中段を走査 + 上段・下段を2分探索で解いてました。よく考えたら祭壇の段数は3段で固定なので、別に難しいこと考える必要なかったんですね...。頭が硬いです。

#define rep(i, a, b) for(int i = (a); i < (b); i++)
#define repr(i, a, b) for(int i = (a); i >= (b); i--)
#define range(x) begin(x), end(x)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;

const int iinf = 1 << 29;
const ll linf = 1l << 61;

int N;
int size[3][100800];
// i + 1 段目 j 番目のパーツを一番上にして、i + 1 段目、...、3段目のピースを使ってできる祭壇の種類の数を今 comb[i][j] とする。
// ただしcomb[i][0] = 0 (i = 0, 1, 2), comb[2][j] = 1 (j = 1, 2, ..., N)
// sum[i][j] = comb[i][0] + comb[i][1] + ... + comb[i][j] と定義する。
// size[i][j] < size[i + 1][k] を満たす最小のkをk(i, j)とすると、(満たすkがない時k(i, j) = N + 1)
// comb[i][j] = comb[i + 1][k(i, j)] + comb[i + 1][k(i, j) + 1] + ... + comb[i + 1][N] = sum[i + 1][N] - sum[i + 1][k(i, j) - 1]
// sum[i][j] = sum[i][j - 1] + comb[i][j]
// が成り立ち、結果
// sum[i][j] = sum[i][j - 1] + (sum[i + 1][N] - sum[i + 1][k(i, j) - 1])
// この漸化式を解いていけば良い(sum[0][N]が答えになる)
ll sum[3][100800];

int main(int argc, char* argv[])
{
	scanf("%d", &N);
	rep(j, 0, 3)
	{
		size[j][0] = 0;
		for(int i = 1; i <= N; i++)
		{
			scanf("%d", &size[j][i]);
		}
		sort(size[j] + 1, size[j] + N + 1);
	}

	for(int i = 2; i >= 0; i--)
	{
		int k = 1;
		sum[i][0] = 0;
		for(int j = 1; j <= N; j++)
		{
			if(i == 2)
			{
				sum[i][j] = j;
			}
			else
			{
				while(k <= N && size[i][j] >= size[i + 1][k]) k++;
				sum[i][j] = sum[i][j - 1] + (sum[i + 1][N] - sum[i + 1][k - 1]);
			}
		}
	}
	printf("%lld\n", sum[0][N]);

	return 0;
}

sumとsizeの添え字を1つずらしたせいで色々バグらせましたがなんとかAC。ただ、この解法なら任意の段数でも効率よく解けるはず。

D問題

意味不明でした。解説を見ても意味不明。グラフの問題に帰結させてる?01BFSってなんですか。

感想

楽しかったですが、C問題で、中段を中心に探索するのを思いつけなかったのが最大の心残りです。まだまだ頭が硬いですね...。

僕と競プロ

美談でもなく、競プロとの出会い、JOIが僕の人生に大きな影響を与えました。いずれ話したいなと思っていたことでしたが、今回この場を借りて語ろうと思います。



話は2年前のちょうどこの頃、高校2年の秋まで遡ります。地方の自称進学校でゴミみたいな成績に甘んじていた頃のことです。

中学生の時趣味でCを書いていたので、その惰性で高校でも細々とプログラミングをしていました。そのことを知った情報科目の教師が、JOI予選に出ることを勧めてきました。面白そうだったので参加することにしましたが、競技プログラミングというという単語を初めて聞いたレベルだったので全く期待はしていませんでした。

しかしなぜだか予選を突破してしまい、本選に出ることになりました。当時とても喜びましたが、その後すぐに、本選には進学校のパソコン部で鍛え上げられた強者がわらわら居るということを知って、戦意喪失。その代わり、プロと一度だけでも話してみたい、そう思うようになりました。

そして本選当日。案の定1完で敗退。夜の自己紹介で、約90人の前で「蟻本昨日買いました(本当)」という盛大なギャグをかましたところ「ひっでえなあww」という正直なコメントをもらったのをよく覚えています。そして、その懇親会で出会った情報のプロたちに圧倒されました。自分の遥か上には、頭が良くてかつ魅力的な人がたくさん居るということを、この時初めて知ったわけです。



しかしここで一つ、心の変化がありました。

「勉強は面白い。この人たちと一緒に勉強したい。いい大学に行きたい。」そう思うようになりました。それが、僕が受験勉強を続ける大きなモチベーションになったということは言うまでもありません。裏を返せば、もしもこの人たちに出会わなければ、僕は今の大学に進学していなかっただろうし、大学で勉強などほとんどしなかったことでしょう。



そしてもう一つ、考え方の変化がありました。

それまで僕は、プログラミングができることをあまり人に知られたくありませんでした。そう思っていた理由は今考えるとよくわかりませんが、多分変な奴だと思われたくなかったんだと思います。なので、学校でJOIについて表彰されることになった時、卑屈にも当時の僕はそれを拒否しました。当時の僕にとっては、表彰は全校生徒の前で腹踊りをすることに等しかったのです。しかしながら、先生に「いいから、いいから」と押し切られ、表彰されることになりました。

当日、なぜか自分はトリ。すでに帰りたさ度MAX。そのうち、とうとう僕の番が回ってきました。穴があったら入りたい。

校長「右は何たらかんたら〜〜〜代読。おめでとう。」
校長「みなさん何の事だか分からないと思うので、ちょっと情報オリンピックについて簡単に説明してください。」 え、説明しろなんて聞いてないんだが
僕 「えー...、与えられた問題をプログラムを組んで解く能力を競う、えっと...まあニッチな大会です。」 ちょっとウケた。よかった。
校長「えーみなさんよく分からないと思いますが、彼は灘や開成の生徒たちに混じって戦ってきました。これは非常に名誉なことです。どうぞ拍手を送ってください。」

友人曰く、僕の表彰が一番拍手が大きかったそうです。思ってもみませんでした。みんな「?」みたいな顔をしながらまばらな拍手が起こるのが関の山だと思っていました。

その後、友達やクラスメイト、先生から賞賛を受けて、「プログラミングは胸を張って言える特技の一つなんだ」と気づかされました。自分の好きな事、得意なことを知ってもらうのに、後ろめたさを感じる必要はないのです。それ以来、プログラミングに限らず、自分の特技や趣味を知ってもらうことに抵抗感を持たなくなりました。この考え方の変化は、僕にとって大きなプラスとなりました。それまでと比べて、胸のつかえが取れた気がしました。

本選を通して、僕が競プロ初心者以上の何かになれたかと言えばなれなかったのですが、その代わりに大きな刺激を受けることができました。本選に出場できたことを本当に幸福に思います。



現在、僕は大学で競技プログラミングの自主ゼミに参加し、競プロを一から学んでいます。他にも数学の自主ゼミにも楽しく参加させてもらっています。一緒に勉強できる仲間がいるということは素晴らしいことです。しかし、2年前もし考え方を変えていなかったら、一緒に学ぶ仲間を作ろうともせず、一人細々と趣味に興じていたことでしょう。自分よりも遥か上の存在を知って、刺激を受ける。これが何事においても向上の近道となるわけですね。