NSTomoS’s blog

NSTomoSの情報系の記録用ブログです.

c++で競プロ入門(1)

最近ラボの先輩やら情報の後輩氏がgitとかpythonの入門エントリーを書いてて,自分も何か書いてみようと思い,「c++で競プロ入門」と題してc++競技プログラミングの入門講座を書こうと思います.
試しにツイッターでアンケートをしたところ,以下のような結果になりました.

ということで,院試勉強の合間の息抜き程度にc++入門レベルで書きたいと思います. (院試勉強めんどい…)

基本的にc言語(ないし他の言語)が分かっている前提で解説します.

競技プログラミングとは

競技プログラミングとは,プログラミングを武器にアルゴリズム力や実装力を競う競技です.
競技ルールはコンテストやマラソン,AI等の様々なものがありますが,このエントリーでは一般的なコンテストを対象にします.
基本的なルールはこんな感じです.

  • 制限時間が短い(数時間)
  • 厳密解の求まる数個~十数個の問題が与えられる
  • 入力に対して正しい答えを出力するプログラムを作成し,提出
  • テストケースを全て正解できればその問題を解いたことになる
  • 解いた問題の数が多いほど順位が高い
  • 解いた数が同じなら最後に正解した問題の提出時刻が早い方が順位が高い
  • コンテストによっては誤答に時間ペナルティがある

AtCoder

僕が主に参加してるのはAtCoderのコンテストです.
ほぼ毎週土曜日に定例コンテスト(初心者向けのABCか上級者向けのARCのどちらか)が開催されます.
その他にも不定期のイベントがあります.

AtCoder (アットコーダー)

今回はこの中からABC(AtCoder Beginner Contest)040を解いていきたいと思います.

AtCoder Beginner Contest 040 - AtCoder Beginner Contest 040 | AtCoder

まず,最初に右上の新規登録からアカウント作成を行ってください.

アカウントを作成したら「問題」のタブから問題を見ましょう.
定例コンテストでは毎度4問出題されます.
では,各問題を解説していきます.

A問題 赤赤赤赤青

A: 赤赤赤赤青 - AtCoder Beginner Contest 040 | AtCoder

この問題ではc++の基本的な構文や入出力,AtCoderの使い方の話をします.

ライブラリ

まず,ライブラリのインクルードです.

#include <iostream>

今回の問題で必要なのは入出力だけです.

名前空間

ここで魔法の呪文が出てきます.

using namespace std;

c++には名前空間という概念があります.
異なるライブラリの同じ識別名を区別するためにあり,各識別名を利用する際は,hoge::piyo(名前空間hogeの識別名piyoを指す)のようにどの名前空間の識別名かを明示しなければなりません.
しかしながら,基本的にc++標準ライブラリしか用いない競技プログラミングにおいてはただただ面倒なだけです.
そこでこの魔法の呪文を書いておくことで,識別名単体の記述を可能にします.
(なお,一般には名前空間の汚染等の問題からあまり良いコードではないとされる場合が多いので気をつけて下さい.)

メイン関数

int main(void) {
    
    return 0;
}

メイン関数はc言語の場合と同じです.
コマンドライン引数は必要ないので引数はvoid返り値は正常終了の0です.

入出力

c++では入出力に入力演算子>>,出力演算子<<を用います.
変数と標準入力ストリームcin,標準出力ストリームcoutをこれらの演算子で繋げることで入出力ができます.
スペース区切りで次の変数へ格納されます.

今回のA問題では2整数が入力され,1整数を出力するので以下のようにします.

int n,x;
cin >> n >> x;

int ans;
cout << ans << endl;

endlを出力すると改行出力されます. 最後に改行がないと正しい答えだと判定されない場合が多いので気を付けて下さい.

解法

本題の問題の解き方です.
端は1番目の位置かn番目の位置の2通りなので,簡単な条件分岐で解けそうです.

1番目に来る場合はx-1回の交換が必要で,
n番目に来る場合はn-x回の交換が必要です.
このどちらか小さい方を出力すればいいことが分かります.

以下の簡単な条件分岐で実装できます.

if (x-1 < n-x){
    ans = x-1;
}else{
    ans = n-x;
}

提出&ジャッジ

これらをまとめると以下のようなコードになります.

gist7f95b3db41d292e17427d39d6dfa5643

まず,問題文の入出力例(サンプルケース)で,方針が合ってるかを確認します.

次に提出です.(この提出してソースコードが全てのテストケースで正解するか確認することをジャッジと言います)
問題文の最後の「提出する」ボタンか,上部の「提出」タブからソースコードの提出画面に行きます.
ここで,問題,言語を確認し,ソースコードをコピペし,「ソースコードを提出」ボタンを押します.
言語はデフォルトで「C++14(GCC)」なので弄らなくていいでしょう.
(余談ですが,ちょっと前まではデフォルトがbashで面倒でした.)

ソースコードを提出すると自分の結果画面に遷移します.
この画面では自分の提出したソースコードの一覧が見れます.
一番上にさっき提出したはずの投稿があるはずなので,「詳細を確認」のリンクを押します.

提出した各ソースコードのジャッジ結果がわかります.
「状態」がその問題に対するソースコードの結果です.
問題の「状態」が「AC」だったら正解です.

また,下には各テストケースに対する結果があります.
この「状態」には主に以下のようなものがあります.

  • AC (Accepted) 正解
  • WA (Wrong Answer) 誤答
  • CE (Compilation Error) コンパイルエラー
  • TLE (Time Limit Exceeded) 制限時間内にプログラムが終了しなかった
  • RE (Runtime Error) 実行時エラー

他にもMLE,OLE,IEなどがありますが,ほとんど出てこないです.

その他コンテスト,ジャッジシステムについて疑問があれば下のチュートリアル,ルール,用語集,よくある質問のページを読んでください.

このサイクルで問題をドンドン解いていきます.

最小

この問題,二つの数のどちらか小さい方なので「2値の最小値を取る関数とかないの?」と思った人がいるでしょう.
ちゃんとあります.
min(x,y)xyどちらか小さい方を返します.
(cの三項演算子(x<y?x:y)と同値です)
逆はmaxで大きい方を返します.

cout << min(x-1,n-x) << endl;

このmin,maxはとても良く使うので覚えておきましょう.

[2016年7月4日追記1] 厳密にはmin,maxalgorithmのインクルードが必要です.
僕の環境やAtCoderのジャッジではなくてもコンパイルが通ったのでリファレンスを見るまで気付きませんでした.
(後述のabscstdlibのインクルードなしでコンパイルが通ります.)
この現象,前はclangだけだったのですが,どこかのバージョン以降のgccでも出るようになりました.
忘れてても勝手にコンパイルが通るだけなので特に困る事はないはずです…
ただ,気持ちが悪いので調べているのですが,答えが出ません…

[2016年7月4日追記2] 知り合いの方からのご指摘で原因が分かりました.
「明示的にインクルードしたヘッダファイルが、内部でそれらをインクルードしてるから」のようです.
例えばclangの場合iostreamをインクルードすると,ios,__locale,string,algorithm再帰的にインクルードされます.

B問題 □□□□□

B: □□□□□ - AtCoder Beginner Contest 040 | AtCoder

この問題は全数探索の問題です.

絶対値

abs(x)xの絶対値を返します.
扱う値が整数の場合はcstdlibのインクルードを,
扱う値が実数の場合はcmathのインクルードをします.
(c++C言語の標準ライブラリを扱う場合は.hを除いて,冒頭にcを付加します.)

解法

x,横yの長方形を考えた時,「長方形の縦と横の長さの差の絶対値と、余ったタイルの枚数の和」はabs(x-y)+n-x*yで表せます.

これを縦横の長さの組み全てを試します.
つまり,x1からnまで動かし,y1からn/xまで動かした時のabs(x-y)+n-x*yの最小値を求めれば良いことになります.
一見すると {O(n^2)} に見えますが実は {O(n\ {\rm ln}\ n)} なので実行時間は問題ありません.
(僕は別解法で問題を通して(ACして),コンテスト後の解説で想定解法の正しい実行時間を知りました…)

gist0d0b7da4ad970bde18a4503117950f80

次回予告(C,D問題)

C,D問題はA,Bに比べると難しく,解法が長くなるため,B問題までで第一回とします.
アルゴリズム的な話よりもc++AtCoderの話が中心になってしまいました.