読者です 読者をやめる 読者になる 読者になる

パソコン甲子園2007(予選)を攻略してみよう (前編)

高校生たちのアルゴリズムの祭典・パソコン甲子園2007の予選が終了しました。
先日予選の結果が発表されましたが、私の母校もなかなか良い順位についており、11月に行われる決勝戦が楽しみです。

さて、予選の問題は パソコン甲子園公式Webページ で公開されています。
問題はすべて、「標準入力から入力を受け取り、問題文に書かれている処理を行い、標準出力に出力せよ」という形をとっています。
良い問題が揃っていますので、プログラミングが大好きな人も、プログラミング嫌いを克服したい人も、いざ挑戦してみましょう。

【以下のヒントはすべて私個人の見解であり、その正しさについて保障されているものではないことをご了承ください。】

問1のヒント

キャンディーの配布をそのままシミュレートしてみるのもひとつの手ですが、ここはやはり剰余算を使うのがセオリーでしょう。 ただ、単に%39としても上手くいきません。工夫が必要です。
出力する数字が一桁のとき、頭に0を補わなければいけません。
面倒だなと思った人は、(CかC++を使っていれば) printfの使い方をよく調べると幸せになれるでしょう。

問2のヒント

if文を使って地道に数えていきましょう。

問3のヒント

素数の判定には、エラトステネスのふるいを使うのがいいでしょう。
単純かつ高速な、ぜひ知っておきたい良いアルゴリズムです。

問4のヒント

while ループを使って、右・下・右下・左下に調べていきます。
何でもかんでも main 関数の中に書こうとせずに、関数に小分けしていくとミスをしにくいです。

問5のヒント

入力処理が厄介で、何も考えずに scanf を使っていては、次の行のデータまで読み込んでしまいます。 fgets で1行読み取り、sscanf または strtokatoi を使えば大丈夫です。
また、一つ一つ入力を取っては10かどうか見る (10ならばストライク = 1投少なくなる) というのも手です。
C++ であれば StringStream も効果的です。

さて、これでちょうど半分です。調子はいかがでしょうか?
難しい?それともまだまだ余裕ですか?
後半にはもっと難しく面白い問題が控えています。気を引き締めていきましょう。

担当 : 田山