n-knuu's logs

憧れ駆動。だいたい競プロ

KUPC2015

KUPC2015(京都大学プログラミングコンテスト2015)に参加しました
京都オンサイトで参加していました(初オンサイトコンテストだった)
結果は5問解いて、700点(64位)でした。

-1:20ごろ

  • クスノキ前に集合して、会場に移動する

-0:40ごろ

  • 東京会場のトラブルで20分の遅延

0:00 開始

  • Aを読む。最初から面倒そう。
  • 貪欲でいけそう。文字列処理が面倒なのでpythonで書く→提出

0:05 A(100) AC

  • はい
  • Bを読む。わからない
  • サンプルでも点数もらえるじゃん→提出

0:10 B(9) AC

  • 順位表見たら3位だった(スクショ取っておけばよかった)
  • これもう少し減らせそう→提出

0:15 B(40) AC

  • とりあえずC読むか
  • 具体的にグラフ構成したくないなあ
  • ワーシャルフロイドの更新が発生しなければいけそう→提出

0:23 C(100) AC

  • Dを読む
  • 何か貪欲解法がある気がする
  • とりあえずDP解で部分点とってみるか
  • サンプルが合わない...
  • 順位表見たらBを満点で通している人が結構いるのでBを考えなおす
  • 適当に並べて通らないかなあ
  • ジグザグに行くのができたっぽいぞ→提出

1:00, 1:02 B 2WA

  • 全然ダメ
  • 適当にいじっていたら出来た→提出

1:31 B(100) AC

  • Eを読む
  • 何か見たことある気がするなあ*1、確か二等辺三角形になるはず
  • 1点を左下に固定して、もう一点を右の辺で2分探索(垂直二等分線を引いたときの距離で動かす)して、求めればいける気がする→提出

2:00 E(200) AC

  • Fを読む。勘違いしていて絶望的に分からない
  • Dを考えなおす
  • わからない。とりあえず全探索して提出しよw→提出

2:25 D(0) TLE

  • 知ってた
  • これ例の移動とタスク(滞在)を分けて考える貪欲では?→提出

2:47, 2:49, 2:51 D(0) 3WA

  • intのオーバーフローとか、最後に移動するパターンとか、移動の方法とかを修正した→提出

2:54 D(200) AC

  • デバッグ楽しい(白目)
  • Gを読む。これとかこれとかに似てるけど、実装が辛そう
  • G以外も読んだけれど、G以外は方針が全く思いつかないし、Gをやろう
  • 高橋君チームの小さい方から考えて、位置をFenwick木で計算して、ワザマエがダメな場合は移動するところをlower_boundで探せば良さそう→提出

4:12 G WA

  • 半分以上がテストケース通ってない(絶望)
  • 青木君のチームに同じワザマエがある場合がダメそう→提出

4:23 G 2WA

  • さっきと同じ数しかテストケース通ってない。ダメみたいですね...
  • 残り30分でFでも考えるか
  • 分からない。気がついたら終了5分前→シャッフルして計算させよw→提出

5:00 F TLE、コンテスト終了

  • 64位。点数は去年の2倍以上だった。
  • これがオンサイト効果か

反省

  • 全体的に証明を考えずにやってしまった
  • 最後の30分でFに行くのではなく、Gを頑張った方が良かった
  • Gの勘違いが酷かったけど、スタックとキューだし、構文木の探索順序の話を考えれば良いのを思いつかなかったのが厳しい
  • Bみたいな思いつきがいる問題が非常に弱い、典型力〜〜〜

*1:競プロの問題じゃなくて大学受験の問題集だったっぽい