パソコン甲子園2014本選 参加記

プログラミング班の松崎です。

2014年11月8日(土)から二日間、パソコン甲子園のプログラミング部門にプログラミング班の割地君とチーム「!thinkable」として参加し、6位に入賞しました。

問題数は10問でした。僕たちのチームは1~6,8の7問通しました。

自明ではないような問題(今回は4番以降と予想)と簡単な問題(1番以降)を並行して解いていきました。 ちなみに5番はFirstAcceptでした。

各問題ごとの解法を簡単に書いていきます。

  1. 書いておいて
  2. デッドロックの問題で、閉路検出をやればおわり
  3. 組み合わせの総数を求める問題、treeとしてみて葉から解いていき、ノードごとに場合分けすればよい
  4. 累積和を使ったO(n^4)解法は間に合わないので、枠の左右を固定し、尺取法を行うO(n^3)
  5. 解けず
  6. まず、各本棚についてn冊目から始めたとき何冊目まで入るかを調べ、その後bitDPを行う

6位と自分の目標の順位より下でしたが、実力を出しきった結果だと思います。僕が問6で3回間違えてしまい、順位を落としたのは少し残念でした。来年はWAを減らし、より多くの問題を解くことでベスト3への入賞を狙いたいと思います。

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です