プログラミングコンテストとアルゴリズム 2024/05/22 技術勉強会発表資料
774 Views
June 14, 24
スライド概要
プログラミングコンテストは、プログラミングスキルを競う大会です。いくつかの種類がありますが、今回は競技プログラミングについて紹介します。
ベガシステム技術勉強会の発表資料です。
ベガシステムは、創業1990年、30年以上続くIT企業です。 お客様との対話を大切にし、新たな価値を創造し続けます。
関連スライド
各ページのテキスト
プログラミングコンテストと アルゴリズム 1
プログラミングコンテストとは コンテストサイトについて 競技プログラミングをやってみた感想 まとめ 参考資料一覧 2
プログラミングコンテストとは プログラミングコンテストとはプログラミングの能力や技術を競うコンテストのことで、 Wikipedia [1] によると、大別して 以下の5種類がある。 1. アルゴリズム、コンピュータサイエンス、数学に関係する問題を解く早さを競うもの 2. ソフトウェアやネットワークのセキュリティ上の問題点を見つけることを競うもの 3. ソースコードの小ささを競うもの 4. 人工知能(AI)を作って競うもの 5. 作品の評価を競うもの 今回はこの中でも 競技プログラミング と呼ばれることもある 1. のタイプのプログラミングコンテストについて紹介して いく。 3
競技プログラミングとは 競技プログラミングについて『アルゴリズムマスターによる競技プログラミング入門』では、職業プログラマの方に理解して もらいやすい説明として次のようなものが挙げられている。 審判団が提示した複数の要求仕様に対し、それぞれソースコードを書いて提出する。審判団が持ってい るユニットテストにすべて通れば正解となる。競技プログラミングではユニットテストに通ればどんな汚いコー ドもOK。ただし1つでもテストに落ちると時間ペナルティが課せられる。バグらせないためには見通しの良い コードでなければならない。結局、速く正確にシンプルに綺麗に書く必要がある。[2] 4
コンテストサイトについて 競技プログラミングのコンテストの多くはインターネット上で行われる。国内の主なコンテストサイトとしては以下のもの がある。アカウントを作れば無料で利用できる。 サイト名 Aizu Online Judge 3.0 説明 会津大学によるサイト。プログラムの基礎を学ぶことができるコースや学生向けのコン テストの過去問が多く公開されている。リアルタイムのコンテストはそれほど活発には 行われていない。AIによるレビュー機能が最近追加された(2024年2月)。 初心者から上級者まで幅広いレベルのコンテストが開催されている。毎週行われて AtCoder いるABC(AtCoder Beginner Contest)の参加者は10000人ほど。有志によ る問題復習支援サイト AtCoder Problems が便利。 5
コンテストサイトについて Aizu Online Judge AtCoder コンテスト頻度 少ない 多い(週1~2回) 提出したコード 非表示にできる 非表示にできない テストケースの入出力 確認できる 確認できない 解説・模範解答の有無 一部ある ある テーマ別のコース ある 少しある 6
コンテストサイトについて 「競技」プログラミングやプログラミング「コンテスト」という言葉が使われているが、必ずしも決まった時間のコンテストに 出場したり他の人と競い合ったりする必要はなく、自分のペースで問題を解いて学習することができる。 ただ、コンテストに参加すると 制限時間がある 間違えたときにペナルティが課せられる レーティングの変動がある などの要素が加わるため、より緊張感を持って問題に取り組むことができる。 7
コンテストサイトの利点 環境構築不要 多くの言語に対応している (参考: AtCoderで使える言語・ライブラリリスト) 他の人のコードを参考に学ぶことができる 実装の正しさがある程度保証される ▶ 初めてプログラミングに触れた頃、何もかもが手探りで相当な時間を無駄にしました。オンライン ジャッジシステムが登場し、新しい知識・技術の獲得から実装能力の体得に至るまでのサイクルは 劇的に縮まりました。[3] → 新しい言語を学ぶ際にもオンラインジャッジを利用することで、短期間でその言語の基本的な構文やライブラリを 習得することができる。 8
競技プログラミングをやってみた感想 計算量に対する理解が深まる → 実行時間制限があるため、適切なアルゴリズムを選ぶようになる 解き方がわかることと実装ができることは別 → ちゃんとコードを書くことが大事 アルゴリズムに関する知識が身につく プログラミング的な発想も必要 9
アルゴリズムに関する知識が身につく 競技プログラミングでよく出題される問題はアルゴリズムに関するものが多い。関連書籍 [3][4][5][6] の目次からは以下 のような言葉が取得できる(順不同)。 ・計算量 ・データ構造 ・ソート ・再帰関数 ・スタック ・キュー ・二分探索 ・全探索 ・累積和 ・貪欲法 ・動的計画法 ・グラフ ・深さ優先探索 ・幅優先探索 ・ダイクストラ法 ・最小全域木 ・分割統治法 ・ 数学 問題が解けなかったときに解説を見ると、自分の知らなかったアルゴリズムを使っていることがある。 問題を解こうとし ているときにはそのアルゴリズムが必要だと知らなかったのである。アルゴリズムについての知識があればこそ要不要の 判断が可能となる。 10
プログラミング的な発想も必要 プログラムはコンピュータが実行するため、人間的な考え方が最善とは限らない。 以下具体的な問題で説明する。 11
問題 A ～ I に 1 から 9 までの数字を 1 つずついれて等式を成立させよ。ただしアルファベット二文字を並べた表記 XY は X × 10 + Y を意味する。[7] C F + AB I + DE = 1 GH 12
問題 A ～ I に 1 から 9 までの数字を 1 つずついれて等式を成立させよ。ただしアルファベット二文字を並べた表記 XY は X × 10 + Y を意味する。[7] C F + AB I + DE = 1 GH 数学的な発想 不等式による評価を行う 素因数に注目して条件を加える などの考察を行い、解の候補を絞って答えを導く。 13
問題 A ～ I に 1 から 9 までの数字を 1 つずついれて等式を成立させよ。ただしアルファベット二文字を並べた表記 XY は X × 10 + Y を意味する。[7] C F + AB I + DE = 1 GH プログラミング的発想 すべての組み合わせを試す → A ～ I に対して、 1 から 9 までの数字を入れて、等式を満たすものを探す → たかだか 9! = 362880 通りなので、全探索してもさほど時間はかからない 14
問題
解答例
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include <bits/stdc++.h>
using namespace std;
int main() {
int a, b, c, d, e, f, g, h, i;
vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9};
do {
a = v[0]; b = v[1]; c = v[2]; d = v[3]; e = v[4]; f = v[5]; g = v[6]; h = v[7]; i = v[8];
int ab = 10 * a + b;
int de = 10 * d + e;
int gh = 10 * g + h;
if (c*de*gh + f*ab*gh + i*ab*de == ab*de*gh) {
printf("%d/%d + %d/%d + %d/%d = 1\n", c, ab, f, de, i, gh);
}
} while (next_permutation(v.begin(), v.end()));
return 0;
}
15
まとめ プログラミングコンテストサイトを上手に活用すればプログラムのスキルが向上しうる 「あのアルゴリズムを学んでおけばよかった」と思う瞬間はおそらく来ない → しかしそれはアルゴリズムを学ぶ必要がないことを意味しない → 自分の都合に合わせて学ぼう 16
参考資料一覧 [1] プログラミングコンテスト - Wikipedia 2024年5月22日閲覧 [2] YUHA 著. アルゴリズムマスターによる競技プログラミング入門, 技術評論社, 2014, コラム: 競技プロ グラミングと実務プログラミングの関連性は? [3] 渡部有隆 著. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造, マイナビ, 2015 [4] 大槻兼資 著ほか. プログラミングコンテストAtCoder入門 : アルゴリズム的思考力が身につく!, KADOKAWA, 2022 [5] 米田優峻 著. 競技プログラミングの鉄則 : アルゴリズム力と思考力を高める77の技術, マイナビ出版, 2022 [6] 秋葉拓哉, 岩田陽一, 北川宜稔 著. プログラミングコンテストチャレンジブック : 問題解決のアルゴリズ ム活用力とコーディングテクニックを鍛える. 第2版, マイナビ, 2012 17
参考資料一覧 [7] 芦ヶ原伸之 著. 超々難問数理パズル : 解けるものなら解いてごらん, 講談社, 2002, p.30 PUZZLE27 より、表記を変えて引用 18
参考URL一覧 AtCoder C++入門 AtCoder Programming Guide for beginners (APG4b) AtCoder Problems Aizu Online Judge 1.0 Aizu Online Judge 2.0 Aizu Online Judge 3.0 19