社会人からはじめる競技プログラミング

本記事は「珠玉のアドベントカレンダー記事をリバイバル公開します」企画のために、以前Qiitaに投稿した記事を一部ブラッシュアップしたものになります。

はじめに

本記事はフューチャー Advent Calendar 2018 の13日目の記事として書かれました。私は弊社に入ってから競技プログラミングなるものを知り、実際に初めてみて約1年が経ちました。競プロって何？競プロって聞いたことはあるけれどなんだかよくわからない…という方に、競技プログラミングの面白みを少しでも伝えられたらと思い、記事を書きました。

競技プログラミングって何？

決められた条件のもとで与えられた問題、課題をプログラミングを用いて解決し、その過程や結果を競うものを競技プログラミングといいます¹。

コンテストの種類

競技プログラミングといっても様々な分野のコンテストが開催されており、大きく以下の5つの分類のコンテストがあります。

(強くなるためのプログラミング -様々なプログラミングコンテストとそのはじめ方- より引用)

Kaggleのようなデータ分析のコンテストは上記の表でいうと「データマイニング」に該当し、ISUCONのようなコンテストは「サーバインフラ」のようなコンテスト、SECCONのようなコンテストは「セキュリティ」のコンテスト、CodinGameのようなコンテストは「ゲームAI」のコンテストに該当するでしょう。私が参加しているのは、いわゆる「アルゴリズム」のコンテストに該当します。「アルゴリズム」のコンテストは1回あたりにかかる所要時間が比較的短く、参加しやすいという特徴があります。

アルゴリズム系のコンテスト

「アルゴリズム」に分類されるコンテストは国内外で様々に開催されています。「アルゴリズム」の中でも1日あるいは数日かかって開催される「マラソン」という形式のコンテストも存在しますが、ここでは詳しくは触れません。なお、弊社で過去何回か行われている「HACK TO THE FUTURE ²」はマラソン形式のコンテストでした。

以下のようなサイトでコンテストは開催されています。おすすめは AtCoder です！

詳細は競技プログラミングを参照ください。

なぜ競技プログラミングは面白い？

コンテストにおいて、多数の参加者と自身のプログラミングの実力を比べることになります。問題解決やプログラミングが好きで、そして誰かと競い合うことが好きであれば、競技プログラミングは面白いと感じるでしょう。

ここでは AtCoder のコンテストに掲載された実際の問題をいくつか見てみましょう。

CODE THANKS FESTIVAL 2018：Colored Balls
(実行時間制限: 2 sec / メモリ制限: 1024 MB)

初め箱には赤い玉が個、青い玉が個入っています。
高橋君は以下の操作を繰り返して、箱を空にしたいです。
・赤い玉を個、青い玉を個箱から取り出す。
もしくは、
・赤い玉を個、青い玉を個箱から取り出す。
各操作ではこのつのいずれか好きな方を行うことができ、毎回同じ操作を行う必要はありません。
高橋君のために、箱を空にする方法があるかどうか判定してください。

箱を空にすることができる場合は Yes を、できない場合は No を出力せよ。

CODE THANKS FESTIVAL 2018(Parallel) B - Colored Ballsより引用

簡単な問題の例をあげてみました。
これは「赤い玉を個、青い玉を個箱から取り出す」操作を回、「赤い玉を個、青い玉を個箱から取り出す」操作を回実施したとすると、赤い玉と青い玉について以下の連立方程式が成り立ちます。

、についてそれぞれ解くと、、となります。よってが非負の整数解を持つ時 Yes そうでない場合は No となります。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		long x = in.nextLong(), y = in.nextLong();
		if ((-x + 3*y) % 8 == 0
				&& (3*x - y) % 8 == 0
				&& (-x + 3*y) / 8 >= 0
				&& (3*x - y) / 8 >= 0) {
			System.out.println("Yes");
		} else {
			System.out.println("No");
		}
		in.close();
	}
}

もう少し難しい問題を見てみましょう。いわゆる「あみだくじ」の問題です。
問題の題材としては NewsPicksでも取り上げられており、シンプルですが面白い問題です。

AtCoder Beginner Contest 013 D 阿弥陀
(実行時間制限: 4 sec / メモリ制限: 256 MB)

古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？
あみだくじを行うときは、まず本の平行な縦線を引く。次に、本の横線をその中に引いていく。それぞれの横線は隣り合う本の縦線を結ぶように引かなければならず、本以上の横線がまったく同じ高さにあってはいけない。ここでは、上から番目にある横線が、左から番目の縦線と番目の縦線を結んでいるとしよう。
の場合のあみだくじを以下に示す。くじを引くときは、縦線を本選び、その上端から線を下っていく。途中で横線に遭遇したときには必ず曲がらなければならず、また縦線を上向きに辿ってはいけない。たとえばこのあみだくじで左から番目の縦線から始めてくじを引くと、左から番目の縦線に辿り着く。

さて、ここまでは普通のあみだくじであるが、何かにつけビッグデータという言葉が騒がれる昨今である。あみだくじがこれから先生きのこるためには、あみだくじもビッグになってビッグデータに対抗していかなければならない。
そこで、あみだくじを縦に個つなげることで巨大なあみだくじを作ることを考えよう。たとえば、先ほど例に挙げたあみだくじを個つなげてみると以下のようになる。この場合、左から番目の縦線から始めてくじを引くと、辿り着く場所は左から番目の縦線になる。

こうして作った巨大あみだくじだが、あみだくじ本来の目的を果たせなければビッグになった意味もない。つまり、この巨大なあみだくじを使ってくじを引いた結果がどうなるかを効率よく計算できなければ、せっかく作った巨大あみだくじもただの落書きである。
そこで、を満たすすべての整数に対し、巨大あみだくじの左から番目の縦線を選んで線を辿っていったとき、最終的に下端で左から何番目の縦線に行き着くかを計算するプログラムを書いて欲しい。

制約

AtCoder Beginner Contest 013 D - 阿弥陀より引用

与えられている問題文が少し長いですが、いわゆる「あみだくじ」を実施したときにどこからどこにたどりつくか、を求める問題です。あみだくじがつないしは数個程度までは手で数えることも可能ですが、個もあると手動で数えることは不可能です。縦につながるあみだくじの数をから少しずつ増やして考えてみます。

(i) の場合
まずは一番簡単な (あみだくじがつ)の場合について考えてみます。これはあみだくじの横棒に対応する配列を用いて、初期状態のデータをswapさせるだけでよいです。
これは計算量で実現できます。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 標準入力からデータを受け取ります
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), m = in.nextInt(), d = in.nextInt();

		// あみだくじに対応する配列 {0, 1, 2, 3, 4} (0-indexed) としておきます
		int[] amida = new int[n];
		for (int i = 0; i < n; i++) {
			amida[i] = i;
		}
		for (int i = 0; i < m; i++) {
			int a = in.nextInt()-1;

			// あみだくじの横棒によって swap させます
			int tmp = amida[a];
			amida[a] = amida[a+1];
			amida[a+1] = tmp;
		}

		// 整形して答えを出力します。
		int[] ans = new int[n];
		for (int i = 0; i < n; i++) {
			ans[amida[i]] = i;
		}
		for (int i : ans) {
			System.out.println(i+1);
		}

		in.close();
	}
}

次にの場合について考えてみます。

(ii) 程度の場合

の場合は簡単に求められました。あみだくじを回実施する操作をとしておきます。

問題文で与えられている例であれば

となります。番目の列は番目に移動し、番目の列は番目に移動するので、変化はありません。番目の列は番目に移動することを意味します。なお問題文は1-indexed で記載されているためとなっていますが、便宜上としておきます。

さて、個のあみだくじが縦に並んでいる場合ですが、これは初期状態のデータに対してを回適用させれば、求める解答が得られます。計算量はです。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 標準入力からデータを受け取ります
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), m = in.nextInt(), d = in.nextInt();

		// あみだくじに対応する配列 {0, 1, 2, 3, 4} (0-indexed) としておきます
		int[] amida = new int[n];
		for (int i = 0; i < n; i++) {
			amida[i] = i;
		}
		for (int i = 0; i < m; i++) {
			int a = in.nextInt()-1;

			// あみだくじの横棒によって swap させます
			int swap = amida[a];
			amida[a] = amida[a+1];
			amida[a+1] = swap;
		}

		// あみだくじをはじめる状態 b = {0, 1, 2, 3, 4} からあみだくじを D 回繰り返し適用させます。
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			b[i] = i;
		}

		for (int i = 0; i < d; i++) {
			int[] tmp = new int[n];
			for (int j = 0; j < n; j++) {
				tmp[j] = amida[b[j]];
			}
			b = tmp.clone();
		}

		// 整形して答えを出力します。
		int[] ans = new int[n];
		for (int i = 0; i < n; i++) {
			ans[b[i]] = i;
		}
		for (int i : ans) {
			System.out.println(i+1);
		}

		in.close();
	}
}

さて、もともと与えられていた制約は

制約
(実行時間制限: 4 sec / メモリ制限: 256 MB)

でした。(ii) の実装の場合、計算量はでしたので程度となり、これは秒で処理することはできません。別の工夫が必要になります。

(iii) の場合

(ii) のような、あみだくじの結果を回繰り返し適用する方法では制約内で答えを計算できません。計算を高速化にダブリング³というアルゴリズムを適用することを考えてみます。

を回適用して答えを求めることはすでにできました。
を回適用した結果がわかれば、を回適用した結果も高速に求められます。
を回適用した結果がわかれば、を回適用した結果も高速に求められます。
を回適用した結果がわかれば、を回適用した結果も高速に求められます。

このように考えると
を回適用した結果がわかれば、を回適用した結果も高速に求められます。
このようにしてあらかじめ回あみだくじを適用した結果を求めておきます。これは計算量で実現できます。

また、は進数で表すことができます。例えばです。
あみだくじを回適用することは進数表示したときにビット目がであるビットについて回あみだくじを適用することと同値です。
であれば回適用することになります。
回適用した結果は求めることができたので、制約内で答えを計算できるようになりました。
全体の計算量です。

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		// 標準入力からデータを受け取ります
		Scanner in = new Scanner(System.in);
		int n = in.nextInt(), m = in.nextInt(), d = in.nextInt();

		// あみだくじに対応する配列 {0, 1, 2, 3, 4} (0-indexed) としておきます
		int[] amida = new int[n];
		for (int i = 0; i < n; i++) {
			amida[i] = i;
		}
		for (int i = 0; i < m; i++) {
			int a = in.nextInt()-1;

			// あみだくじの横棒によって swap させます
			int swap = amida[a];
			amida[a] = amida[a+1];
			amida[a+1] = swap;
		}

		// あみだくじをはじめる状態 {0, 1, 2, 3, 4} からあみだくじを 1 回適用させます
		int[][] next = new int[32][n];
		for (int i = 0; i < n; i++) {
			next[0][i] = amida[i];
		}

		// 2^k 回の適用した結果から 2^{k+1} 回適用した結果を求めておきます
		for (int k = 0; k < 31; k++) {
			for (int j = 0; j < n; j++) {
				next[k+1][j] = next[k][next[k][j]];
			}
		}

		// k ビット目が 1 であるビットについて 2^k 回あみだくじを適用させた結果に置き換えます
		int[] b = new int[n];
		for (int i = 0; i < n; i++) {
			int p = i;
			for (int j = 31; j >= 0; j--) {
				if ((d >> j & 1) == 1) {
					p = next[j][p];
				}
			}
			b[i] = p;
		}

		// 整形して答えを出力します。
		int[] ans = new int[n];
		for (int i = 0; i < n; i++) {
			ans[b[i]] = i;
		}
		for (int i : ans) {
			System.out.println(i+1);
		}

		in.close();

	}
}

何を学べる？

アルゴリズムの基礎を学べる

問題を解くにあたっては、基本的なアルゴリズムを理解し、具体的な問題に応用できるスキルが求められます。
競技プログラミングを取り組みながら、以下の内容を学べます。
(高度な内容は除いています)

計算量の概念
データ構造
再帰
全探索・幅優先探索・深さ優先探索・bit全探索
グラフ
動的計画法

問題解決の方法を学べる

問題を解くにあたっては、以下のような流れで進めることが一般的です。

問題を読む問題・制約を理解する考察する実装する提出するデバッグする提出する (正解するまで繰り返す)

上記の中で特に重要なのは 考察する ということです。解答の方針が決まらないまま実装しても、いたずらに時間を費やすだけで解が得られないことが多いです。考察の過程で「どのようにしたら問題を解くことができるか」を考えることが求められます。競技プログラミングを通じて、問題解決の方法を学べます。

おわりに

具体的な問題例を通じて、競技プログラミングの基本的な紹介と、その面白みを伝えることを試みました。競技プログラミングの面白さが、少しでもみなさんに伝わればと思います！