PCK Post Contest 2009

Contest

パソコン甲子園の問題セットを使った部内コンテスト。
実はパソコン甲子園の翌日には後輩たちとがっつり問題のレビューをしてたので、自分のは参考記録みたいなものです。
なんとなく今日は後ろから解いてみました。

Problem K: Pachimon Creature

  • 5回DP回すだけ。さっくり実装してみた。
  • 合わない。問題を読み間違えてることに気づいた。
    • 最初の1匹はもらえるのであって、主人公がぶん殴って捕獲するのではないのですね。修正。
  • まだREとWAだ。よく見たら配列の添字間違いがそこかしこに。修正。でもまだ通らない。
  • あ!解無しの判定が間違ってる!
    • さっきの読み間違いのせいで「モンスターが1匹もいない属性が1つでもあったら不可」としてたけど、モンスターが1匹もいない属性が1つまであっても大丈夫だ。
  • 直した。ようやく通った。

Problem J: Autumnal Illumination

  • 多角形の交差判定書くだけ。ライブラリをコピペった。
  • intersectGGはまだライブラリになってなかったので打ち込んだ。DisjointSetもライブラリにないので打ち込み。
    • 丸暗記してるからなくてもいいやと思ってたけど、コピペありのコンテストのためにはやっぱりあった方が便利ですね。
  • 入力の形式が冗長で戸惑ったりしたけど難なくAccepted.

Problem I: Subdivide The Land

  • めんどい。飛ばそう。

Problem H: Highway Express Bus

  • おなじみ拡張Dijkstraだけど、面倒臭いので最近お気に入りの収束するまで回すメソッドに逃げた。
    • Bellman-Fordっぽいけどちょっと違う気もする。
  • とりあえずAccepted.

Problem G: Jogging

  • 周期を求めてLCM。はいはい雑魚雑魚。
    • と思ってたら周期が整数にならないことに気づいた。どうしよう。
  • ...
  • とりあえずおにぎり食べよう。
  • ...
  • 全員の距離に適当に全員の速度のLCMでも掛けてやったりすればよいのでは。
  • 答え出た。Submit. WA...
  • オーバーフローしてそうな感じだ。...後回しにしようか。

Problem F: The Squares

  • 書くだけ。でも面倒くさいのでパス。

Problem E: Scene in a Picture

  • ひたすらループ回すだけ。これぐらいは素直に書こう。
  • -1はワイルドカードだけどマッチした位置として出力してはいけないことと、座標値を (横方向, 縦方向) の順で出力しないといけないところに引っ掛かった。
    • 何なのこの無駄に面倒臭い仕様・・・。
  • とにかくAccepted.

Problem D: Room Numbers of a Hospital

  • 8進数に変換するだけ。
  • さっきの問題が面倒臭かっただけに、実装の簡単さが嬉しい。10行で書けた。Accepted.

Problem C: Block

  • 塗り潰すだけ。DFSした。
  • wとかhとかいらないよね、と思いながらAccepted.

Problem B: Next Trip

  • Accepted.

Problem A: Rock, Paper, Scissors

  • 適当に書き殴った。Accepted.
  • えーと、次何やろう。
  • とりあえずおやつタイム。LOOKをつまみつつあったかい缶コーヒーでまったり。
  • 面倒臭いの書きたくないし、Gやろうか。

Problem G: Jogging (retry)

  • オーバーフローしないような計算に持ち込まねばならぬ。
  • ...どうやればいいんだろ。全然分からん。
  • ...
  • あ!sampleのケースだと時速300km超でジョギングしてる!
    • 赤ベコ小学校は鬼パないですね!!
  • ...
  • 別の方法考えてみたけど答えが合わないままタイムアップ。8問でした。

反省

  • 問題文をがっつり読んでたというのに3問残るとは。残念すぎる。
  • 自分の数学(というか算数)の素養のなさに絶望です。
  • 初春さん強いー。どこのどちら様なのでしょうか。