AOJのITP1問題集の傾向と解法のヒント

おそらく競技プログラミング入門として取り組まれるようなITP1の問題集ですが、見てみると成功率があまり高くない問題がちらほらあるので、解答とまではいきませんが初心者向けに簡単な補足をしてみたいと思います。

本投稿はAOJの問題のヒントを取り扱うため、若干のネタバレが含まれます！

AOJのITP1とは

ITP1は、"Introduction of Programming 1"という事で、実践的な問題というよりかは、競技プログラミング全般(あるいは単純にプログラミング)における入門のための問題集という感じがします。
AOJを含め、競技プログラミングを始めようか悩んでいる方や、あるいは始めたばかりという方は、まずこの問題集にある問題を解いてみる事をおすすめします。

問題数は2018年7月13日時点で44問で、以下の11ジャンルから4問ずつ(A, B, C, D)出題されています。(AよりもDのほうがより難しい傾向にあるようです。)

1. Getting Started【入門】

• C/C++では1つのprintfやstd::coutで済む(Dはやや難しいか？)程度の計算問題。

1. Branch on Condition【条件付き分岐】
2. Repetiting Processing【繰り返し処理】
3. Conputation【計算】

• "Getting Started"よりもややクセのある問題があります。計算の有効数字も気にするような問題。

1. Structured Programming I【構造化プログラミング I 】

• "構造化プログラミング"とありますが、実際はコンソール(あるいは端末)上で入力に応じた何かしらの図または表形式で出力するような問題がほとんどです。
  ただし、D問はプログラミングの組み立てに関する問題として出題されています。
• 構造化プログラミングについてはこちら(Wikipedia:構造化プログラミング)

1. Array【配列】
2. Structured Programming II【構造化プログラミング II 】

• "Structured Programming I"に同じ。

1. Character【字】
2. String【文字列】
3. Math Function【数学的な関数】
4. Structure and Class【構造体とクラス】

• さいころを例とした問題です。C言語では面倒臭いと感じるはず…？

(競プロ初心者向け)AOJ全般でACを取るまでのヒント

詳しい事はAOJの公式サイトにあるので、ここではPEとWA抜粋して解説します。
→AOJ-ジャッジ結果の詳細

まず、回答を提出したときにPE(Presentation Error : 出力形式によるエラー)をもらったときは、ここであきらめずに以下の点を確認してみてください。

• **半角スペースが1つ余計についていませんか？**または、半角スペースを付け忘れていませんか？
  • PEをもらった時のたいていの原因は、この場合がほとんどです。数字や文字などを空白区切りで１行に出力するとき、例えば3_4_5_6_(ここでは半角スペースを_と表記しています)と標準出力してしまっている場合があります。
• 余計な改行が含まれていませんか？または、改行が不足していませんか？

次に、WA(Wrong Answer : 回答が違う)をもらったときは、普通に解答が間違えているか、または問題が複数ケース与えられるのに1ケースしか受け付けられない場合のどちらかだと思います。

• 前者のうち、実数や数値計算が入っている場合は、小数の有効数字内で値が間違っている場合があります。
  • 特に、円周率や自然対数の底などの無理数の数学定数が絡んできている場合、これらが定義されている桁数が足りていない場合があります。
    参考までに、$\pi$=3.14159265358979323846...、$e$=2.71828182845904523536...
  • もしくは、合計・総和を問われる問題では、オーバーフロー(またはレアケースではアンダーフロー)が発生している可能性があります。その場合、問題に与えられる値の範囲にもよりますが、long long intなどの64bit型変数で合計・総和をとるなどで解決できる可能性があります。
    大正義C/C++では、int型でとれる値は$\pm$約20億までなのに対し、long long int型では$\pm$約900京まで数え上げる事ができる。
• 後者はAOJでよくやらかしてしまう事だと思います。一応、ITP1を順当に進んでいけば、ITP1-03-B:テストケースの出力以降から要求される場合があるので、ここでこの形式に慣れておくとよいでしょう。

ITP1の問題についてのヒント集

一応、ITP1において成功率が低い問題(約30%以下、ほとんどがD問)についてヒントを示しておきます。
以下、ネタバレ注意です！問題を解いたときの達成感を損なう可能性があります
(解説を飛ばして「あとがき」まで飛びたい方は、右側の見出しもしくはこちらからどうぞ)
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓
↓

ITP1-04-B : Circle

$\pi$を自分で定義している場合は、その値の有効桁数に十分注意する必要があります。
入力ケースを見ると、最大で10000程度まで与えられます。また、小数点5桁までの精度を保証する必要があります。

ITP1-04-D : Min, Max, and Sum

入力形式を見ると、最大100万までの値が連続で1万回与えられる場合があります。この場合の合計は100億となり、int型ではオーバーフローを起こして正しい合計が得られません。(WA率が6割近くを占めているため、もしかするとこれが原因で落ちている可能性が高いです)
そのため、より大きな値を保持できる型を使う必要があります。また、合計は負の値をとる可能性も考慮しなければなりません。
(最大値、最小値を保持する変数はintで十分です。)

ITP1-05-D : Structured Programming

コードを解読するよりかは、とりあえず実際に提示されているコードをコンパイルしてみて、出力されている数字の傾向をつかんだほうが早いかと思います。
傾向のヒントは「世界のナベアツ」です。

ITP1-06-C : Official House

適当な3次元配列を使ってあげると、forで回してあげるだけになります。
各棟の各階の入居者数を出力する際、最初に半角スペース がついている事に注意。

ITP1-07-D : Matrix Multiplication

入力形式を見ると、要素の値が最大で10000なので、要素同士の積で最大1億、これが100回行われる可能性があります。Hintにある通りで、計算結果を保持する変数のオーバーフローに注意しましょう。

ITP1-11 : Dice I～IV

Cで実装するのはちょっと面倒なので、C++のクラスでさいころを転がすオブジェクトを作ってあげると楽だと思います。(Cでは解けないという訳ではありません)
ITP1-11-Cが解けたのに、ITP1-11-Dを解くとTLE(Time Limit Exceeded : 実行時間超過)となる場合は判定アルゴリズムを改良する必要があるかと思います。

そのほかのITP1の問題のヒントについて

希望があればヒントを示したいと思います。(全ての問題を解いているわけではないため、やや時間はかかるかと思います)

どうしても解けない場合は？

問題ページの虫眼鏡マーク(Solution)をクリックすると、ACされたソースの一覧が見れます。
一覧のカラムRun#のリンクからソースが見れます。(いわばカンニングする事ができます。)
形式上、これらの公開ソースをコピペして提出する事も可能ではありますが、**「なぜこのコードで通るのか？」**という事を考えたうえで、再度自力でコードを書いて提出する事を強くお勧めします。コピペして提出する事はお勧めできません。

#あとがき

やっぱり競技プログラミング勢が増えてほしいという思いをはせてこの記事を投稿してみましたが、いかがだったでしょうか？
AOJのITP1は競技プログラミングやもっと一般的なプログラミングにおける基本ともなるため、最低でも各ジャンルのC問まで解く事をお勧めします。
自分も現在進行形でアルゴリズムなどを勉強している最中なので、もしかしたら間違っている事を書いてしまっている可能性があるので、その時はこっそりと教えてください。

どうでもよい話なのですが、「フロントエンジニアやマークアップエンジニアなどを目指す人には競技プログラムは無縁だ」っていう話を同級生から聞いた事がありますが、正直なところそういうわけではないと思っています。
個人的に感じている事ですが、競技プログラミングでの成績は少なくとも問題解決能力やコーディングといったものの基礎的なものが十分にできる事、専門とはいかないものの、他の分野でも十分に適用できるという証拠になると思います。(わがままだったらごめんなさい…)
もしこの記事を読んでいる方が情報系の学生ならば、競技プログラミングは自分の実力を示すいいチャンスだと思うので、この機会にぜひ競技プログラミングの世界に足を踏み入れてみませんか？