Go to Qiita Advent Calendar 2024 Top
LoginSignup
35
38

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

フューチャーAdvent Calendar 2018

Day 13
@tutuz(Tsuji Daishiro)inフューチャー株式会社

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

Last updated at Posted at 2018-12-12

はじめに

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

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

競技プログラミングは、与えられた課題をプログラミングで解決し、その正確さや速さを競う競技です。

コンテストの種類

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

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

Kaggleのようなデータ分析のコンテストは上記の表でいうと「データマイニング」に該当し、ISUCONのようなコンテストは「サーバインフラ」のようなコンテスト、SECCONのようなコンテストは「セキュリティ」のコンテスト、CodinGameのようなコンテストは「ゲームAI」のコンテストに該当するでしょう。私が参加しているのは、いわゆる「アルゴリズム」のコンテストに該当します。「アルゴリズム」のようなコンテストは参加しやすいのが魅力とも言えます。易しいという意味ではありません。

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

さて「アルゴリズム」に分類されるコンテストといっても国内外問わず様々なコンテストが開かれています。「アルゴリズム」の中でも1~数日かけてコンテストが行われるマラソンという形式のコンテストもありますが、今回は割愛します。なお、先日弊社で行われた 「HACK TO THE FUTURE」はマラソン形式のコンテストです。

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

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

何が面白いの？

与えられた課題に対して制限時間内に回答しなければなりません。そして、多くの参加者とプログラミングの実力を競い合うことになります。問題解決が好きで、誰かと競い合うことが好きであれば競技プログラミングは面白いと思います。

実際にいくつか問題を見てみましょう。
簡単な問題から難しい問題までいろいろな難易度の問題があります。

CODE THANKS FESTIVAL 2018：Colored Balls

(実行時間制限: 2 sec / メモリ制限: 1024 MB)

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

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

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

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

\left\{
\begin{array}{ll}
A + 3B = X \\
3A + B = Y
\end{array}
\right.

$A$、$B$ についてそれぞれ解くと、$A = \displaystyle \frac{-X+3Y}{8}$、$B = \displaystyle \frac{3X-Y}{8}$ となります。よって$A, B$ が非負の整数解を持つ時 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)

古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？
あみだくじを行うときは、まず $N$ 本の平行な縦線を引く。次に、$M$ 本の横線をその中に引いていく。それぞれの横線は隣り合う $2$ 本の縦線を結ぶように引かなければならず、$2$ 本以上の横線がまったく同じ高さにあってはいけない。ここでは、上から $i(1 \le i \le M)$ 番目にある横線が、左から $A_{i}(1 \le A_{i} < N)$ 番目の縦線と $A_{i} + 1$ 番目の縦線を結んでいるとしよう。
$N=5,M=7,A={1,4,3,4,2,3,1}$ の場合のあみだくじを以下に示す。くじを引くときは、縦線を $1$ 本選び、その上端から線を下っていく。途中で横線に遭遇したときには必ず曲がらなければならず、また縦線を上向きに辿ってはいけない。たとえばこのあみだくじで左から $4$ 番目の縦線から始めてくじを引くと、左から$3$ 番目の縦線に辿り着く。

4-1.png

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

4-2.png

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

制約

$2 \le N \le 10^5 $
$0 \le M \le 2 \times 10^5 $
$1 \le D \le 10^9 $

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

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

(i) $D=1 \ (,\ N \le 10^5)$ の場合
まずは一番簡単な $D=1$ (あみだくじが $1$ つ)の場合について考えてみます。これはあみだくじの横棒に対応する数列の値を用いて、はじめる状態のデータをswapさせるだけでよいです。
これは計算量 $O(N+M)$ で実現できます。

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();
	}
}

次に $D > 1$ の場合について考えてみます。

(ii) $D \le 1000 \ (,\ N \le 10^5)$ 程度の場合

$D=1$ の場合は簡単に求められました。$1$回のあみだくじの結果を $\sigma$ としておきます。

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

\sigma = 

{\begin{pmatrix}
0 & 1 & 2 & 3 & 4\\
4 & 1 & 3 & 0 & 2
\end{pmatrix}
}

となります。例えば $0$ 番目の列は $4$ 番目に移動し、$2$ 番目の列は $3$ 番目に移動することを意味します。
$1$ 番目の列は $1$ 番目に移動するので、変化はありません。(問題文は1-indexed なので $\{1,2,3,4,5\}$ となっていますが、便宜上 $\{0,1,2,3,4\}$ としておきます。

さて、$D \ (\le 1000)$ 個のあみだくじが縦に並んでいる場合ですが、これははじめの状態のデータ ${\{0 ,1, 2, 3, 4\}}$ に対して $\sigma$ を $D$ 回適応させれば、求める解答が得られます。計算量は $O(DN+M)$ です。

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)
$2 \le N \le 10^5 $
$0 \le M \le 2 \times 10^5 $
$1 \le D \le 10^9 $

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

(iii) $1 \le D \le 10^9 \ (,\ N \le 10^5)$ の場合

(ii) のように単純にあみだくじの結果を $D$ 回用いる方法では制約内で答えを用いることはできませんでした。

さて、データに対してあみだくじ $\sigma$ を $1$ 回適応して答えを求めることはすでにできました。
$\sigma$ を $1$ 回適応した結果がわかれば、$\sigma$ を $2$ 回適応した結果も高速に求められます。
$\sigma$ を $2$ 回適応した結果がわかれば、$\sigma$ を $4$ 回適応した結果も高速に求められます。
$\sigma$ を $4$ 回適応した結果がわかれば、$\sigma$ を $8$ 回適応した結果も高速に求められます。
$\cdots$

このように考えると
$\sigma$ を $2^{k}$ 回適応した結果がわかれば、$\sigma$ を $2^{k+1}$ 回適応した結果も高速に求められます。
このようにしてあらかじめ $2^{k} \ (0 \le k \le logD)$ 回あみだくじを適応した結果を求めておきます。これは計算量 $O(logD)$ です。

また、$D$ は $2$ 進数で表すことができます。例えば $10_{(10)}=111011100110101100101000000000_{(2)}$ です。
あみだくじを $D$ 回適応することは $2$ 進数表示したときに $k$ ビット目が $1$ であるビットについて $\sum 2^{k}$ 回あみだくじを適応することと同値です。
$D=10^9$ であれば $2^{29} + 2^{28} + 2^{27} + 2^{25} + \cdots + 2^{9}$ 回適応することになります。
$2^{k}$ 回適応した結果は求めることができたので、答えを得ることができました。
全体の計算量 $O(NlogD+M)$ です。

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全探索
  • グラフ
  • 動的計画法
  • $\cdots$

問題を解くための方法を学べる

コンテストで問題を解くにあたっては以下を実施します。

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

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

おわりに

問題例を通じて、競技プログラミングの簡単な紹介と、競技プログラミングの面白みを伝えることを試みました。少しでも競技プログラミングの面白さが伝われば幸いです！

35
38
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
35
38

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?