【初心者向け】競技プログラミングざっくり入門【競プロ】

この記事の目的

競技プログラミング/プログラミングコンテストに参加し始めたばかりの自分が、コンテストや過去問を解く上で参考にしたサイト、困ったことなどをメモするほか、これから競技プログラミングに挑戦していこうという人たちの参考になれば。自分のレベル感としては最初の村を出たばかりで、ひのきのぼうと皮の盾装備。PHPerなので参考URLはPHP関連のものが多いです。競技プログラミングにおいてPHPerは少数派なので情報が少なく、それが動機ともなってこのような記事を書こうと思い至りましたが、実行速度や人気度などからC++, Pythonなどでもいずれやりたいなぁと思っています。

競技プログラミングとは

競技プログラミング（以下、競プロ）とは、プログラミング技術を競うコンテストのこと。いろいろな企業や団体が主催をしていて、世界中で毎日のように競技が開催されています。様々な言語の取り扱いがあり、自分の得意な言語でチャレンジ可能。オフラインのものは参加したことはありませんが、オンラインのコンテンスト問題は、与えられたお題に対して、正しい出力が期待されるコードを送信するだけで、機械的にジャッジされて得点や順位、レーティングが分かったりするので気軽に挑戦できるのが魅力かと思います。ここでは主にオンラインの競技プログラミングに関して取り上げています。

競プロいろいろ

国内サイト・大会

AtCoder
日本最大級の競プロサイト。

yukicoder
中規模なプログラミングコンテストサイト。

日本情報オリンピック(Japanese Olympiad in Infomatics(JOI))
高校生向けプログラミングコンテストの国際情報オリンピック(IOI)の代表選考のためのコンテスト。

paiza プログラミングスキルチェック
エンジニア向けラーニング＆転職サービスですが、スキルチェックとして競プロに近いテストをオンラインでたくさん受けられます。

CODE VS
リクルートが主催するプログラミングコンテスト。

海外サイト

LeetCode
アメリカ・カリフォルニア発の競プロサイト。英語と中国語に対応。

HackerRank
アメリカにあるプログラミングコンテストサイト。

Topcoder
アメリカのAppirio社が提供するプログラミングコンテストサイト。

Codeforces
ロシアの大学 (Saratov State University) に所属するMike Mirzayanovらが実施するプログラミングコンテストサイト。

CodeChef
Directi社が運営・提供するプログラミング学習サイト。

Project Euler
数学の問題が出題されるようです。

国際大会

Google Code Jam (GCJ)
Googleが実施するプログラミングコンテスト。

Facebook Hacker Cup (FHC)
Facebookが実施するプログラミングコンテスト。

ACM-ICPC 国際大学対抗プログラミングコンテスト
大学対抗のプログラミングコンテスト。1970年から始まり今に続く歴史あるコンテスト。

2019 TopCoder Open
TopCoderが実施する祭典コンテスト。毎年開催され、年度によってURLも新設されるので注意が必要です。

ICFP Programming Contest (ICFPC)
関数型プログラミング言語のカンファレンスが実施するコンテスト。

Microsoft Imagine Cup
マイクロソフトが実施する学生向けのプログラミングコンテスト。

国際情報オリンピック(International Olympiad in Informatics) (IOI)
高校生向けのプログラミングコンテスト。参加するには日本情報オリンピックで代表に選ばれる必要があります。

AtCoderでのレーティングについて

AtCoderではレーティングのシステムが採用されていて、400ポイントごとにレベルが色分けされています。
高いものから、赤・橙・黄・青・水・緑・茶・灰・黒、という順番になっており、レベル感について詳しくは下記の記事でまとめていただいています。AtCoder主催の高橋直大さんのブログです。

AtCoder（競技プログラミング）の色・ランクと実力評価、問題例

競プロでたまに見る「標準入力」とは

その言語で想定される一般的な入力方法。入出力といえばキーボード入力・モニタ出力なども一般的ですが、競プロにおいてはテキストファイルまたは特定の値を保持したと仮定する変数、が入力の対象となることが多い印象です。
PHPの場合、変数からの入力であればそのまま使用できますが、テキストファイルからの入力が想定されるのであればfscanf()やfgets()関数で取り回しできるようになることがまず必要です。

PHP マニュアル - fscanf
PHP マニュアル - fgets

ローカル環境でプログラムを実行して出力を確認する際は、ローカルにあるテキストファイルをfopen()関数で読み取って、fgets()関数で1行ずつ変数や配列に格納したり、echoやreturnで返してあげたりすることから始めると良さそうです。
「標準入力から与えられた数値の合計を計算する」という問題が与えられたとして、仮に、入力用のテキストファイルをtest.txt、実行用のプログラムファイルをindex.phpとします。

test.txt

3
4
3

テキストファイルの取り出したい行に改行や空白が含まれて意図しない結果が出力される場合は、trim()関数で空白を削除することが可能です。

PHP マニュアル - trim

上記を踏まえ、ローカルでの実行内容としては以下のようなものが想定されます。（実行結果をブラウザで確認する場合。ターミナルで実行する場合は他の方法もあります。）

index.php

<?php
    // test.txt を r(読み取り専用)モードで開く
    $file = fopen("test.txt", "r");

    // fgets で1行ずつテキストファイルの中身を取り出して $line に代入
    // while でテキストファイルの最後の行まで繰り返すことができる
    while ($line = fgets($file)) {
        // trim で文字列 $line の先頭および末尾にあるホワイトスペースを取り除く
        // テキストファイルの全内容は1行ずつ配列として $temp[] に格納される
        $temp[] = trim($line);
    };

    echo $temp[0] + $temp[1] + $temp[2]; // 実行結果：10 (正解)

これをAtCoderなどのサイトで送信する場合は、ローカルでの入力=読み取りモードで開くなどの必要はないので、fopen()は削除してfgets($file)の代わりにfgets(STDIN)などとすれば問題なさそうです。STDINはスタンダート・インプットの略で、ソースは更に短く、下記のようになります。

index.php(提出用)

<?php
    while ($line = fgets(STDIN)) {
        $temp[] = trim($line);
    };
    echo $temp[0] + $temp[1] + $temp[2];

条件によってはechoではなくreturnで返す場合もあるかと思います。
また、プログラムの書き方は1通りではないので、もっと短く効率的に書けるようであればそちらを優先してください。（例えば、配列の数値の合計を出す関数を使うともっとスマートに書けるかも、とか。）

今日はいったんここまでにしておきます。

標準入力や使い勝手の良い組み込み関数など、PHPer用にチートシートをまとめたりしているので、興味のある方はこちらのリンクもどうぞ。

【PHP】競技プログラミング用の関数チートシート【プロコン】

参考URL

標準入力、標準出力とは何か?
http://www.creatology.jp/unix/outin.html#err
競技プログラミングとは？メリットや初心者にもおすすめな理由も解説
https://tech-camp.in/note/technology/43369/
【PHP】複数文字列の置換(str_replace)
https://qiita.com/kazu56/items/35c10fdd79393686b26d
Paizaで使える標準入力の取得
https://qiita.com/one-kelvin/items/09068b8971c4da509cd3
PHPで標準入力から値を取得して表示する方法を解説
https://qiita.com/yuhei_umeda/items/552c3f2f19e55f80fdfb
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
https://qiita.com/drken/items/fd4e5e3630d0f5859067#3-hello-world-----practice-contest-a-問題のみ
AtCoder用語集
https://atcoder.jp/contests/abc074/glossary?lang=ja
PHPの出力で文字を改行（\n）させるには’’（シングルコーテーション）じゃなくて""（ダブルコーテーション）で記述する
https://qiita.com/sola-msr/items/0814c4470dcbbd1f5ec3
asort(PHP 4, PHP 5, PHP 7) — 連想キーと要素との関係を維持しつつ配列をソートする
https://www.php.net/manual/ja/function.asort.php
配列のソート
https://www.php.net/manual/ja/array.sorting.php
PHPで割り算の余り､切り上げ､切り捨て､四捨五入する方法
https://www.flatflag.nir87.com/division-414
代数演算子
https://www.php.net/manual/ja/language.operators.arithmetic.php