パソコン甲子園予選に参加しました

ふぃらっはです。夏休みが残り2週間になってしまいましたが，みなさんいかがお過ごしでしょうか。

さて，9/9（土）にパソコン甲子園プログラミング部門の予選に参加したので，解けた範囲で大まかな解説と感想を書こうと思います。

問題1から問題6まで順に解説していきます。問題自体はパソコン甲子園公式サイトにそのうちアップロードされると思うので，そちらを参考にしてください。なお，提出したコードはGitHubにて公開してあります。レイアウト的な問題から記事中ではコードを画像で貼り付けているので，コードをコピーしたりしたい場合はGitHubからどうぞ。

問題1

入力を受けて，足して2で割ったものを出力するだけです。

問題2

3パターンに分岐して解きます。

所持金だけで買える場合（m≧b）：0を出力します。
所持金とA君のお金を足してもなお買えない場合（m+f<b)：NAを出力します。
それ以外の場合：b-mを出力します。

問題3

入力を7で割った余り（X%7）を求めます。余りが0なら木曜日，1なら金曜日，2なら土曜日，……となるので，switch文を使うなり，["thu", "fri", "sat", "sun", "mon", "tue", "wed"][x % 7]ってやるなりしたら解けます。

ここまでの問題は相方の投資家おじさんが解いてくれました。

問題4

この問題で詰まっている人が多かったように思います。あとでTwitterを見てみると「問4は実質国語の問題」みたいなつぶやきがありました。確かに問題文の読解が少々めんどくさかったのかもしれません。

冷静に考えて，パターン分けを行ってみます。

時刻の重複が発生するのは次の条件のどちらかに引っかかった場合です。

1:新しい予約の終了時間が，既にある予約のうちどれかの開始時間より遅く，終了時間より早い。
図にするとこんな感じです（大変拙い図ですみません）。

2:新しい予約の開始時間が，既にある予約のうちどれかの開始時間より遅く，終了時間より早い。
同じく図にするとこうなります。

既にある予約の全てについて，これらの条件が成立していないかどうか調べます。もし一回でも成立したら0を出力し，一回も成立しなかった場合のみ1を出力します。
コードは以下のようになりました。

問題5

入力をそれぞれix, iyとします。
電線は左上隅から右下隅までまっすぐ張られるので，電線はそれぞれの縦線，それぞれの横線と必ず一度交わります。つまり，交点は全部で(ix+1)+(iy+1)=ix+iy+2個あることになります。

ただし，このままだと縦線と横線と電線が交わっている部分を重複して数えてしまっているので，重複している分だけ合計から引いていきます。具体的には，以下の処理を行います。
数学の気持ちになってy=ax（a=yの変化量/xの変化量=iy/(ix*2)）という式（電線の式）を立てます。0≦i≦ix，0≦j≦iyを満たす2i, jの組で，j = a * 2iを満たすものがある場合，そこで重複が発生しているので，先ほど求めた合計を一つ減らします。

コードは以下のようになりました。

問題6

トランポリンを跳びついで一往復できるかどうか求める問題です。

まず，両端にあるトランポリンのうちどちらか片方でも最大ジャンプ距離が10未満の場合は，どう頑張ってもそこから先に進めないので”no”を出力します。

次に，両端以外のトランポリンについて考えていきます。最大ジャンプ距離が10以上のトランポリンについては何も考えなくていいですが，最大ジャンプ距離が10未満のトランポリンについては，以下のように判定する必要があります。
1つ前にあるトランポリンの最大ジャンプ距離が20以上ならOK
→もしダメでも，2つ前にあるトランポリンの最大ジャンプ距離が30以上ならOK
→それがダメでも，3つ前にあるトランポリンの最大ジャンプ距離が40以上ならOK
→……
図にするとこんな感じになります。

この判定を繰り返して，一度もOKにならなかった場合は”no”を出力します。

コードは以下のようになりました（メチャクチャなコードですがご容赦ください）。

感想

できれば問題8ぐらいまで解きたいと思っていたのですが，残念ながら途中までしか解けませんでした。問題7以降はアルゴリズムとデータ構造の知識が必要になってきて，対策無しで解くのが難しくなるので，来年はしっかり勉強して臨みたいと思います。

パソコン甲子園の問題を解くのに必要なのは，問題文をよく読んで必要な処理を考える力と，考えた処理をプログラムにうまく落とし込む力だと感じます。特に後者の能力は，競技プログラミングに限らずゲーム制作やWebサイト開発を通じても養えると思います。日頃からプログラミングに親しんでおくことが大事なのではないでしょうか。

拙い文章ですが，最後まで読んでくださりありがとうございました。