わふぅ。

わふです。

ICPC2014国内予選

競技プログラミング 参加記

結論

落ちました。来年は全完できるようにがんばります。

解いた問題

B問題

シミュレーションするだけ。

行ごとに消去されるブロックをチェックして消したあと、列ごとに下からブロックを積みなおす、という作業を繰り返すだけ。

E問題

木DPっぽさがあるが、すこし考えると直径を求めておしまい。

元のグラフGからリーフを切り取ったグラフG'を考えれば、答えは「Gの全長 + G'の全長 × 2 - G'の直径」で、あとは O(n) なコードを書くだけ。 ちなみにこれは、グラフG'上での直径を実現する端点S,Tを考えれば、Sから作業を始めてTで作業を終えるときの最小コストに等しくなる。

JOI2013本選のおはなし

参加記 競技プログラミング

概要とか本選全体の適当な感想とか

JOI2013の本選。最後の本選。金メダルをとるつもりで行ってきた。結果はお察しください。

1日目

今年は1日目がセキュキャンフォーラムとかぶったので、プラクティス/講演会には出ずに、懇親会だけ出た。 大人数でワイワイガヤガヤするのはやはり楽しい。1日目は唐揚げとかソーセージとかケーキとか食べて、いろいろな人と名刺交換したりハラスメント合戦したりして楽しんでいた。OBもたくさんきていて楽しかった。いもすばーがー。

懇親会のあとは、kagamiz氏と一緒にお風呂へ入りに行ったり、談話室であり本を読んだりして過ごして、早めに寝た。 談話室と近い部屋だとDEGwer氏などを始めとする余裕勢がまだ談話室で遊んでいたりするので、気になる人は耳栓を持って くるか殴りこみにいくのがおすすめ。

2日目

2日目は7時くらいに起きてTwitterでkagamiz氏と連絡をとり一緒に朝ごはんを食べに行った。適当にコンディションを整えつつ競技を迎える。

競技を終えたあとはお通夜フェーズのまま昼ごはん。コーラをたくさん飲む。食べ終わったらすぐにセンター棟へ本選問題の解説を聞きに行く。

解説を聞いたあとは解散。暇だったのでhogloid氏/tozangezan氏/Hziwara氏とともに新宿へ行った。ゲーセンに寄って音ゲーを適当に遊んだあと、サイゼリヤでぐだぐだと話をしていた。受験生は心を失っているので時々ひどいハラスメントが飛んでくることもあったが、いろいろな話ができて楽しかった。またこういう機会が欲しい。

持っていったもの

毎年なにを持っていけばいいのか迷うので、(春/夏)合宿のときもきっと同じように迷うはずだと考えて、書き残しておく。あくまで最低限ですけど。

  • 着替え
  • 歯ブラシ
  • タオル・バスタオル
  • ハンカチ・ティッシュ
  • スモールマスコット
  • 名刺
  • 財布
  • 携帯電話
  • ノートPC
  • 筆記用具

インターネットを発する機械を持っていったほうがいい気がしたが、1日だけだしAndroid機もあるので今年は持って行かなかった。さすがに(春/夏)合宿だと持っていくほうがいいと思う。

本選競技とか時系列順に

問1を解く

去年の問1はやるだけだったので今年もそのぐらいかなーと思いつつ読解。 簡単なDPかなーと思いつつ適当にコードを書くもWA。うむ。難しい。範囲をうまく扱えない。 けっきょく泥沼にはまってしまい、WAがとれないまま50分ぐらいが経過。解法を思いつかない。本選0点の可能性が頭をよぎる。焦りとつらぽよがたまる。精神的にはかなりキていた。 その後10分くらいで [a,b)をひっくり返す→[1,b)をひっくり返して[1,a)をひっくり返す というふうに変換してうまくDPに直せた。 2WAののちAC。すでに競技開始から1時間が経過していて、このペースだとメダルどころかAランクすらあやうい。わりとパニックになっていた。

問2をとりあえず解く

問1から激しく難化していてパニック状態のまま読解。どうやらこちらもDP。 しかし頭がおかしかったので意味不明なDPを書きつつたくさんのWAを出す。ふぇぇ。 なんとか動くものを仕上げてメモ化再帰になおして提出するもTLEで50点しかもらえない。 O(ST)のはずなのにTLEなのはさすがに頭が真っ白になった。高速化を試みるもTLEがとれない。とれない。とれない。 競技開始から2時間ほどが経過していた。もう無理だと思い問3に移動。

問3をとりあえず解く

典型的なグラフの問題。5分くらいで解法がわかる程度には簡単だった。ここにきてなんとか点数を確保できそうだと思い実装。 30分ぐらいで書き上げて提出。しかしWAで80点しか得られない。なぜだろう。デバッグ。わからない。とりあえず80点とれたしあとに回す。 バグりつつもこの時点で230点を獲得できていたので精神的にはなんとか持ち直してきていた気がする。

問4をチラッと見る

自明な10点解法しかわからない。時間が少なくなってきたら部分点狙いで愚直解書くことにしてパス。

問5をチラッと見る

あり本があたまをよぎる。しかし部分点をとるより問2-3のデバッグのほうが点数を期待できそうだと思いパス。

問2に戻る

すでに競技開始から2.5時間ほどが経過。いちばん点数が期待できそうなので高速化を試みる。ifを除去したりいろいろとせこいテクニックを使うもとれない。あせる。 「O(ST)だから通るはず」という思いが焦りを増大させていく。vectorから生配列にしたりしてみるがTLEがとれない。とれない。ふぇぇぇぇ。問3と問2を行き来してデバッグする地獄が始まる。

問3に戻る

よくよく問題文を読みなおしてみるとオーバーフローするケースがあることに気が付きコストの処理を64bitに変更。しかしWAがとれない。ソースコードを何度も読みなおす。 けっきょくはコストではなく頂点番号を64bitにしていた箇所を発見して修正。WAがとれてACになる。自分の実装力の無さに絶望しながら問2に戻る。

問2に戻る

いろいろと高速化をためす。どうやらメモ化部分が遅いらしい。高速化を試す。メモの配置を変えたりする。 けっきょくはメモ配列をshortにすることでキャッシュ効率が上がりなんとかTLEがとれてAC。うむ。なかなかクソい。この時点でほとんど時間が残されていない。

問4 (2回目)

戻ってきて部分点解法を書いて終わり。30点解法を考える余裕もなかった。

問5 (2回目)

SegTreeを書きながら残り時間がほとんど残されていないことを知り諦める。コンテスト終了。

競技の感想とか反省とか

  • 精神力 is たいせつ
  • 実装力の低さに絶望していた。
  • DPは十分に探索関数に落としこむ前に実装しようとして死ぬパターンが多かった。
  • オーバーフローミスとかさすがに死ぬべきだった。
  • 難易度的には 問3 <<<(越えられない壁)<<< 問2 < 問1 <<<(解けなかった壁)<<< 問4 < 問5 だと感じている。
  • グラフ楽勝というかDP苦手というか。
  • 本選課題が入った封筒がなぜか丁寧に糊付けされていてうまくはがせなかった。適当に破いた。
  • 競技開始後1分くらいは開場に「バリバリバリ」という音が響きわたっていて面白かった。

JOI2013予選のおはなし

競技プログラミング 参加記

概要

JOI2013の予選。

たぶん4完だと思われるので人権喪失確定。提出ミスをしていたら予選敗退もメニーチャンシズなので震えてる。 昨年度より成績悪いとさすがに落ち込むぽよ。

とりあえず思ったこととか適当に書いておく。

問1

やるだけ。問1にしてはひねってある問題だと思った。

問2

数え上げやるだけ。意外とめんどくさいコードを書いてしまい実力不足。

問3

文字列処理。つらぽよ。配列のサイズを間違えたのでたぶん0点。

問4

典型DP。問3よりやさしめ。

dp[day][c] := day日目にc番目の服を着た時の最大の累積派手さ としておくと各要素についてO(N)で計算できる。 着られない服に関しては -inf とか置いてやると場合分けせずに楽にかけるはず。

問5

座標圧縮するだけ。前日に座標圧縮の問題をすこし解いていたので余裕だった。 N=50と小さいのでいもす法を用いずナイーブに数え上げをしていってもO(N**4)で間にあう。 どうでもいいけど半開区間は楽ですね。

問6

問1-5までわりと簡単だったので問6もすぐ終わるだろ、と思い2時間を費やすも解けず。実力不足。 周囲10マスぐらいの状態を覚えておけばいいのかなーとか思ったけど激遅だしバグるし死。 すぬけ氏のぶろぐを見ると綺麗な解法載ってるし参考になるんじゃないでしょーか。