狠狠撸

プログラミングコンテスト
という名の
オンラインゲームがあるらしい
＼ガチャはないよ！／

@kakkun61

姫路 IT 系勉強会 Vol. 6 @kakkun61 1/82

自己紹介
● 岡本和樹
● @kakkun61
●
23 歳
● 大阪府立大学 4 回生
●
へなちょこ競技プログラマー


競技プログラミングって
だいたいこんなん
● 大きく 2 つに分けると
● 正解のあるプログラムを速く書く
●
正解の簡単に求まらない問題の答えので
きるだけよいものを求めるプログラムを
書く


競技プログラミングって
だいたいこんなん
● 正解のあるプログラムを早く書く
● こっちを中心に解説していきますん


正解のあるプログラムを速く書く
● をやってるコンテストは
● TopCoder Single Round Match (SRM)
●
AtCoder Regular Contest (ARC)
● CodeChef Short Contest
●
CodeForces
●
Google Code Jam
●
ACM ICPC
● など

正解のあるプログラムを速く書く
● TopCoder Single Round Match (SRM)
● AtCoder Regular Contest (ARC)
●
ACM ICPC
● ぐらいしか参加したことないのでこれら
を題材に


ARC #3
● AtCoder 社
● 慶應大学
●
高橋直大
● @chokudai

●
http://atcoder.com

ARC #3
● A 問題 GPA 計算
● プログラミング初心者向けの問題
●
問題文の通りにコードを書けばいい
● 手元のコンピューターで問題を見ていた
だいた方が見やすいと思う
●
http://atcoder.jp/


ARC #3 A 問題 GPA 計算
● 高橋君はアメリカに留学しようと考えて
おり、成績表を提出することになりまし
た。
● アメリカ留学の成績表には、学力を測る
指標である GPA を表記する必要がありま
す。


● GPA とは各単位に対する評価 (A,B,C,D,F)
を点数に換算して平均した値で、点数へ
の換算は以下のようになります。
● A 評価 → 4 点
● B 評価 → 3 点
● C 評価 → 2 点
● D 評価 → 1 点
● F 評価 → 0 点


● 全て F 評価だった場合は、 GPA は 0 にな
ります。
● 高橋君の各単位に対する評価をもとに GPA
を求めなさい。


● 入力
● 入力は以下の形式で標準入力から与えられる。
● N
● r1r2…rN
● 1 行目は、単位の総数を表す整数
N(1≦N≦100) が与えられる。
● 2 行目には、単位に対する評価を表す N 文字
の文字列が与えられる。
● i 文字目の文字 ri は A, B, C, D, F のいず
れかである。

● 出力
● 入力として与えられた単位の評価をもと
にした GPA を標準出力に 1 行で出力せ
よ。
●
誤差は絶対誤差あるいは相対誤差の少な
くとも片方が 10-9 以下であれば許容す
る。
● なお、最後には改行を出力せよ。


といった感じの問題
● A-D, F を 1-4, 0 に変換し、平均を求
めるだけ
● プログラマーなら誰でもできるはず


● 一応、僕の解答


● え？ Haskell 分からない？


● しかたないので Java で
● main メソッドの中だけ示します


Haskell やってみない？
● Haskell の方が文字大きくなかった？


● つまりそっちの方が書く量少ないってこ
とだよね
● Java の変数の i とか、和が代入されて
ない途中の sum とか要らないよね
●
本当にやりたいことを無駄なく書いてる
のは Haskell じゃない？


● もしここで
● 「今まで C ファミリーの言語でやって
きたから」とか
●
「 Haskell のコードなんか気持ち悪い」
● ってだけで
●
Haskell を避けるならそれってつま
り……


● 老害？


● もちろん Haskell が苦手とするところ
は多々あるので、それを知っての上でな
らいいのですが


● このまま Haskell やってもいいのです
が、
● この後、実用関数型言語の希望の星
Scala のセッションがあるのでそちらに
委ねましょう
●
（自分のコードあんまりポイントフリー
化できてないし）


● でも、実際、
● 新言語習得のときの練習にプログラミン
グコンテストの簡単な問題は有用だと思
う
●
他の人の解答が見られるので、
● 「なるほどこう書けば綺麗なのか」
●
っていうのが多々ある


SRM 543 EllysXors
● 素直に解くとダメな問題
● 僕は素直に解いて撃墜されました
●
撃墜については後ほど


SRM 543 EllysXors
● Problem Statement
● XOR problems became very popular in
TopCoder recently. (If you do not know
the bitwise operation XOR, see the
Notes section for an explanation.)
That's why Elly decided to invent one
of her own. Fortunately for you, the
one she came up with is quite simple.
You are given two longs L and R. She
wants you to find the XOR of all
numbers between L and R, inclusive.

SRM 543 EllysXors
● 要点だけ日本語に訳すと、
● L と R を与えるから、
● L ⊕L+1 ⊕... ⊕R を求めよ

1 ≦ L, R ≦ 4,000,000,000
●
ただし、

L ≦R
●

●


SRM 543 EllysXors
● 単純に実装を考えると、
● 再帰もしくはループでしょう


SRM 543 EllysXors
● しかし、
● 再帰
●
Stack Overflow (Java)
● ループ
●
最大の計算量時に制限時間超過
● Time Limit Exceeded (TLE)


SRM 543 EllysXors
● 実はこの問題、数学的に簡単にできて、
● どんな入力が来ても一定時間で計算でき
ます
●
計算量 O(1) オーダー 1


SRM 543 EllysXors
● ちなみに再帰もしくはループの実装だと
計算量は、 2 つの数の差に比例するの
で、
● O(N)


SRM 543 EllysXors
●
他にも 2 乗に比例するなら、 O(N2)
● クイックソートなどなら、 O(NlogN)


SRM 543 EllysXors
● 話を戻して、数学的に簡単にするとはど
うするのか？
● ちょびっと話がややこしくなります


SRM 543 EllysXors
● まず
● 1 ⊕1 = 0
● 2 ⊕2 = 0
● n ⊕n = 0


SRM 543 EllysXors
● なので
● ellysXors(l, r)
● = l ⊕l+1 ⊕... ⊕r
● = 1 ⊕2 ⊕... ⊕l-1
● ⊕1 ⊕2 ⊕... ⊕l-1 ⊕l ⊕l+1 ⊕... ⊕r


SRM 543 EllysXors
● ここで
● foldXor(n)
● = 1 ⊕2 ⊕... ⊕n
●
とおくと、
● ellysXors(l, r)
● = foldXor(l) ⊕foldXor(r)


SRM 543 EllysXors

(n)10 (n)2 foldXor(n) n を使って
って
1 1 1 1
2 10 11 n+1
3 11 0 0
4 100 100 n
5 101 1 1
6 110 111 n+1
7 111 0 0
8 1000 1000 n
9 1001 1 1


SRM 543 EllysXors

(n)10 (n)2 foldXor(n) n を使って
って
1 1 1 1
2 10 11 n+1
3 11 0 0
4 100 100 n
5 101 1 1
6 110 111 n+1
7 111 0 0
8 1000 1000 n
9 1001 1 1

姫路 IT 系勉強会 Vol. 6 @kakkun61
4 つごとに周期 42/82

SRM 543 EllysXors
● この周期を使うと
● foldXor(n)
● = 1 (n ≡ 1 mod. 4 のき)
と
● = n + 1 (n ≡ 2 mod. 4 のき)
と
● = 0 (n ≡ 3 mod. 4 のき)
と
● = n (n ≡ 4 mod. 4 のき)
と
● ellysXors(l, r)
● = foldXor(l) ⊕foldXor(r)


SRM 543 EllysXors
● よって
● ellysXor(l, r) は定数時間 O(1) で求
まる


ルール説明 ARC
● AtCoder Regular Contest #1, #2, #3 に
もとづいて解説
● コンテスト通してのルールの記述が見当
たらないので今後変わるかも
●
ARC #3 のチュートリアル
http://arc003.contest.atcoder.jp/tutorial


ルール説明 ARC
● AtCoder Regular Contest
● 時間 90 分
●
4問
● 難易度順に A-D


ルール説明 ARC
● 使用可能言語 ● C# (Mono 2.10.5)

● PHP (PHP 5.3.6)
● C (GCC4.4.6)
● Python (2.7.2)
●
C++ (G++4.6.3)
● Perl (5.12.4)
● C++ (GCC4.4.6)
● Ruby (1.9.2)
●
C++11 (GCC 4.6.1)
● Haskell (GHC 7.0.3)
●
C (GCC4.6.3) ● Pascal (fpc 2.4.4)
●
D (DMD 2.058) ● JavaScript

● Java (OpenJDK 1.6.0) (Node 0.6.12)

ルール説明 ARC
● Web でテキスト入力欄に書いて提出
● Main.( 拡張子 ) として保存されるの
で、 Java などの場合 Main クラスにす
る
●
通常のプログラムと同じエントリーポイ
ントから起動される
● 入力および出力は標準入力?標準出力


ルール説明 ARC
● コンテストの流れ
● コンテスト開始 10 分後までに参加登録
●
好きな問題を開く


ルール説明 ARC
● 解けたら、提出ページでソースコードを
貼り付け提出
● 提出するとすぐにシステムがテストを始
める
●
結果タブから現在の結果が得られる
● 結果は次の通り


ルール説明 ARC
● AC: Accepted
● WA: Wrong Answer
●
TLE: Time Limit Exceeded
● MLE: Memory Limit Exceeded
●
CE: Compile Error
●
RE: Runtime Error
●
OLE: Output Limit Exceeded
● IE: ?

ルール説明 ARC
● 順位付け
● 各問 100 点で 400 点満点
●
同点の場合は最終正解提出時間の早さで
比べる
● 誤答ペナルティは 1 回につき 15 分
●
ただし、その問題に正解した場合のみ


ルール説明 ARC
● コンテスト終了後は全員の解答が見られ
るようになるので、それで復習してくだ
さい


ルール説明 SRM
● TopCoder Single Round Match
● 時間 95 分
●
コーディング 75 分
● 休憩 5 分
● チャレンジ 15 分
●
3問
●
チャレンジが特徴的


ルール説明 SRM
● コンテストはアリーナと呼ばれる Java
Applet のアプリを使用
● メンバーは Rating と呼ばれるレベルを
持っていて、 Rating ごとに次のように
色分けされる


ルール説明 SRM
● メンバーは Rating と呼ばれるレベルを
持っていて、 Rating ごとに色分けされ
る


ルール説明 SRM
● 初参加白
● 0-899 灰
●
900-1199 緑
● 1200-1499 青
●
1500-2199 黄
●
2200-2999 赤
●
3000- 赤地に白点ターゲットと呼ばれる


ルール説明 SRM
● 初参加白
● 0-899 灰 ←僕ココしょぼい
●
900-1199 緑
● 1200-1499 青
●
1500-2199 黄
●
2200-2999 赤
●
3000- 赤地に白点ターゲットと呼ばれる


ルール説明 SRM
● Rating の上位?下位で Div. 1, Div. 2
に分かれ、問題セットが異なる


ルール説明 SRM
● 初参加白
● 0-899 灰
●
900-1199 緑 ↑ Div. 2
● 1200-1499 青 ↓ Div. 1
●
1500-2199 黄
●
2200-2999 赤
●
3000- ターゲット


ルール説明 SRM
● 問題は 3 問あり、それぞれ点数が異なる
● Easy 250pts, Normal 500pts, Hard
1000pts
●
各々の問題を開いてから提出するまでの
経過時間で得点が決まる
● 250pts の問題なら、開いて即刻提出すれ
ば 250pts もらえるということ


ルール説明 SRM
● コーディング (coding phase) 75 分
● 問題を解いて提出
● 提出してもまだ採点されない
●
休憩 (intermission) 5 分


ルール説明 SRM
● 撃墜 (challenge phase) 15 分
● このフェーズになると全員の解答が公開
される
●
他の人の解答を見て、間違ってると気付
いたのがあったら、チャレンジを行なう
ことができる


ルール説明 SRM
● 撃墜 (challenge phase) 15 分
● チャレンジとは
●
ある問題にこの入力値を与えれば不正解
を出す? TLE になるなどの入力値を作る
● 提出し実際不正解を出すなどするとチャ
レンジ成功となり 50 点加算、相手の得点
0点
●
失敗した場合は 25 点減点


ルール説明 SRM
● システムテスト (system test)
● 運営の用意した入力セットでテストされ
無事通ると点を得られる
●
結果に応じて Rating が上下する


ルール説明
● ここまでが、ルール説明で
● 次からアルゴリズム入門


アルゴリズム入門
● アルゴリズムの比較的理
解しやすいものを取り上
げよう
● ここからの内容は→見な
がら書いた
●
プログラミングコンテス
トするならこの本は必携


アルゴリズム入門
● プログラミングコンテス
トチャレンジブック
● 著者は東大生 3 人
●
秋葉拓哉
● 岩田陽一
● 北川宜稔
●
通称、蟻本
●
世界と戦うことを目標に
書いてあるので初級編で
かなりお腹いっぱい

再帰とメモ化
● フィボナッチ数列を計算する関数を再帰
で


再帰とメモ化
● 単純な再帰だとかなり遅い


再帰とメモ化

fib(10)

fib(9) fib(8)

fib(8) fib(7)

fib(7)

fib(6)

再帰とメモ化

fib(10) 同じ計算がいくつもある

fib(9) fib(8)

fib(8) fib(7)

fib(7)

fib(6)

再帰とメモ化
● 1 度計算したものを保存しておく
● すでに計算したかチェックしてしてある
ならそれを返す
●
これをメモ化という


再帰とメモ化
● コードで書くと


深さ優先探索 Depth First Search
● 問題
● 整数 a1, a2, ... an が与えられます。そ
の中からいくつか選び、その和をちょう
ど k にすることができるかを判定しな
さい。
● ただし、
● 1 ≦ n ≦ 20
● -108 ≦ ai, k ≦ 108


● 例えば
● n = 4
● a = {1, 2, 4, 7}
●
このとき状態を表す木は次のようになる


i=0
a = {1, 2, 4, 7} sum = 0
+1
i=1 i=1
sum = 0 sum = 1
+2
i=2 i=1
sum = 0 sum = 2
+4
i=3 i=3
sum = 2 sum = 6

姫路 IT 系勉強会 Vol. 6 @kakkun61
+7 79/82

● コードで表すと


なんと
● ARC #4 今日 21 時
● SRM 546 今日 25 時
●
参加するしかない！


狠狠撸

姫路 IT 系勉強会 Vol.6 プログラミングコンテストという名のオンラインゲームがあるらしい

More Related Content

姫路 IT 系勉強会 Vol.6 プログラミングコンテストという名のオンラインゲームがあるらしい