本記事は U-TOKYO AP Advent Calendar 2017の 9 日目の記事です。
競技プログラミングとは何ぞやという人のための記事です.
計数工学科の一部の人々の間で一大センセーションを巻き起こしている競技プログラミング(通称：競プロ)がどのようなものかを競技プログラミングにありそうな問題を交えて説明しようと試みました. アルゴリズム的な話ではなく, 競プロがどういう感じなのかが分かってもらえると嬉しいです. 理論とか実装とかの話が多い中コーヒーブレイク的な記事です.
執筆者: ホハム (@soiya_ksk)
問題A ????coder
競技プログラミングのサイトは日本だと Atcoder, yukicoder, AIDU ONLINE JUDGE(通称: AOJ) など, 海外では Topcoder, codeforces, HackerRank, CSAcademy などの様々なサイトがあります.
Atcoder は毎週土曜か日曜の夜9時ごろから2時間弱行われていて, 初心者向けのコンテストも行われているので非常におすすめです(何より日本語). 本日夜9時からもAtcoder Beginner Contest/Atcoder Regular Contestがありますよ！
プログラミングコンテストのサイトを立ち上げることにしたパチコ君はまずサイト名を考えることにしました. サイト名の案 $S$ が与えられるので,「"????coder"のように末尾が "coder" となるようなサイト名になっていれば, 競プロっぽい！」というパチコ君の直感にあうようなサイト名であるかを YES/NO で判定しましょう.
ただし, すでにある "Atcoder", "yukicoder", "Topcoder" という名前にするのは流石に怒られてしまうのでその場合も NO と判定してください.
実行時間制限 2sec メモリ制限 256MB
####制約
$S$は英字小文字大文字と数字からなる文字列です.
(文字列$S$の長さ) $\leq 10$
####入力
以下の形式で標準入力で与えられます.
$S$ `
####出力
末尾が"coder"になっていてかつ "Atcoder", "yukicoder", "topcoder" でない場合は "YES", そうでない場合は "NO" を出力してください.
####入力例1
pachicoder
####出力例1
YES
####入力例2
Coder
####出力例2
NO
末尾の "coder" は全て小文字でなければ "NO" です.
##問題B タイムリミット, メモリリミット
プログラミングコンテストでは, 与えられる全てのテストケースに対して正しい解答を出力するコードを制限時間内に提出しなければなりません.
正解と認められるためには正しい解答を出力するだけではなく, "コードの実行時間,使用メモリが制限以内である"ことが必要です.
競技プログラミングで使用される言語は C, C++, C#, Java, Python, Ruby などがよく用いられますが, C++ の場合は 1 sec で $10^7〜10^8$ くらいの演算ができると言われています.
例えば, 入力が $N\leq 4000$ なら O( $N^2$) のアルゴリズム（2重ループなど），$N\leq 200000$ なら O($N\log N $) のアルゴリズム （マージソートなど） を用いることができますが, 重いアルゴリズムだと実行時間の制限をオーバーしてしまいます.これを Time Limit Exceed といい, TLE と略されます.
一方, メモリ制限を超えてしまった場合は Memory Limit Exceed といい, MLE と略されます.大きすぎる配列を取ってしまうと MLE になることがあります.
パチコ君はコンテストサイトのジャッジを作りました。
その時, 実行制限時間 A[s], メモリ制限を B[MB] と設定しました。
操作 X の実行時間が1回につき C[ms] かかり, メモリ使用量が D[B] ずつ増えるとすると, 実行時間 A[s] 以下,メモリ使用量 B[MB] 以下の条件の下で, 操作 X は最大何回までできるでしょうか. (ただし操作 X は並列に行うことはできず, メモリを途中で解放することもないとする)
実行時間制限 2sec メモリ制限 256MB
####制約
$A,B,C,D$ は全て整数
$1 \leq A \leq 10$
$1 \leq B \leq 512$
$1 \leq C,D \leq 10^9$
####入力
以下の形式で標準入力で与えられます.
$A B C D$ `
####出力
操作 X を行える最大回数を出力してください.
####入力例1
2 256 1 1000
####出力例1
2000
X を2001回以上行うと TLE になります.
####入力例2
2 256 1 256000
####出力例2
1000
X を1001回以上行うと MLE になります.
####入力例3
2 256 1000000000 1000000000
####出力例3
0
この場合1回もできません.
##問題C バランスのとれたチーム作り
プログラミングコンテストの中には, チーム戦で行うものもあります. 例えば, International Collegiate Programming Contest （国際大学対抗プログラミングコンテスト, 通称: ICPC）では同じ大学(大学院)から3人1チームを作って参加することになっています.
また, Atcoder や Topcoder などのプログラミングコンテストサイトではコンテストの結果によってレーティングが計算されます. レーティングによってアカウント名に色がつきますが, 中でもレーティングは非常に高い人々のアカウントは赤色になり, レッドコーダーと呼ばれ崇められたりします.
パチコ君は1チーム2人の大会を主催することにしました.
$N$ 人が参加登録していて, 各人のレートは $r_1, r_2, ... ,r_N$ です.
2人のレートの和がチームによって大きく異なるとバランスが崩壊してしまうので, 主催者の権限でバランスのとれたチーム分けをしようと考えました.
チーム分けの結果, 2人のレートの和の最大値と最小値の差が最も小さくなるようにすることでバランスのとれたチーム分けにすることにしました. (2人のレートの和の最大値) $-$ (2人のレートの和の最小値)の最小値 を求めてください.
実行時間制限 2sec メモリ制限 256MB
####制約
$ 4\leq N \leq 200000$
$ N $ : 偶数
$ r_i$ : 整数 $(1\leq i \leq N)$
$0 \leq r_i \leq 10^9 $ $(1\leq i \leq N)$
####入力
以下の形式で標準入力で与えられます.
$N$
$r_1 r_2 ... r_N $ `
####出力
(2人のレートの和の最大値) $-$ (2人のレートの和の最小値)の最小値を返してください.
####入力例1
4
1200 2000 1000 4198
####出力例1
1998
1番目の人と2番目の人, 3番目の人と4番目の人を同じチームにしましょう.
####入力例2
4
2000 2000 2000 2000
####出力例2
0
####入力例3
10
83293 840123 480127 81321 742191 123091 92323 123920 149021 239102
####出力例3
648503
##問題D 穴あきカレンダー
現在, U-TOKYO AP Advent Calendar 2017が絶賛開催中です. どの記事も面白そうなのでぜひ読んでみてください.
パチコ君は"Pachico Advecnt Calender 20XX"を計画しました. パチコ君は何十年後先のクリスマスまでにも対応するように全部で$N$日間のアドベントカレンダーにしました.
が、誰も担当していない日が$K$日あることに気が付きました. それらは$p_1, p_2, ... , p_k$日目です.
そこで手当たり次第, 人に声をかけ記事を書かせようということにしました.
その意気込みに$M$人が感銘を受け,記事を書いてくれる事になりました.
$i$番目の人は$a_i〜 b_i日目$なら何日分でも書いていいと言ってくれています.
果たして誰も記事を書いてくれない日を何日まで減らすことができるでしょうか.
実行時間制限 5sec メモリ制限 256MB
####制約
$ 1\leq N,K,M \leq 2000000$
$ 1\leq p_i \leq N $ $(1\leq i \leq K)$
$p_i \neq p_j $ $(i\neq j)$
$ 1\leq a_i < b_i \leq N $ ($1\leq i \leq M$)
####入力
以下の形式で標準入力で与えられます.
$N$ $K$ $M$
$p_1 p_2 ... p_K $
$a_1 a_2 ... a_M $
$b_1 b_2 ... b_M $ `
####出力
誰も記事を書けない日の日数を出力してください.
####入力例1
25 3 3
5 10 15
3 9 15
6 11 25
####出力例1
0
無事全部の日程を埋めることが出来ました.
####入力例2
1000 6 5
1 23 52 100 245 356
1 1 1 1 1
2 2 2 2 2
####出力例2
5
1日目の分しか新たに人を見つけられませんでした.
####入力例3
1000 6 1
1 23 52 100 245 356
1
1000
####出力例3
0
一人が残りの日程を全部埋めてくれました.
##終わりに
今回の記事では, 競プロがどういう感じのものなのかを伝えようという気持ちで書きました. ジャッジやテストケース等は用意していません.
実際の問題を見たほうがより良いと思うので, ぜひ実際に過去に出題された問題を解いてみたり, コンテストに参加してみたりして面白さを感じていただければ幸いです.
なにかおかしな表現等ありましたらtwitter等で連絡ください.
解説（というかヒント）
問題A stringなどを使って判定しましょう.
問題B min((1000a)/b,(1000000c)/d)です.
問題C ソートして（1番レートが高い人,1番レートが低い人), (2番目に高い人,2番目に低い人), ... でチームを作って各チームのレートの和を計算して最大最小を求めましょう.(このようなチーム分けが最適であることは証明できますが割愛)
問題D imos法というアルゴリズムを使うことで前処理をO(N), $p_i$日目に書いてくれる人がいるかの判定をO(1)でできます(時間が足りなかったのでここではこれ以上書けません．是非調べてみてください).