読者です 読者をやめる 読者になる 読者になる

RUPC2017参加記

すっかり遅くなってしまった

1日目

okaduki さんとhaji149 さんとでチーム名oohajiで参加した.色々あって自称div2 onlyチームだった

A問題

haji149さんが通した

B問題

二つの周期が重なるところはgcd取れば計算できるので愚直に計算するだけ
紙コーディングしておいたおかげかOnsiteのFAを取れた

C問題

okaduki さんが通した

D問題

okaduki さんが4連続ぐらいしかしないよねって言って通した

E問題

最初,魔法の効果が適用されるのはi番目の文字だけだと誤読していて,XとY独立に貪欲にやるだけだと勘違いしていた
haji149 さんの助言で,普通の最大化DPとRとL,UとDを反転させた最大化DPを解けばいいことになる
実装も手伝ってもらった

F問題

okadukiさんが色々考察して辺を逆に張って10回Dijkstraすればいいことに気付いてAC.つよい

K問題

haji149 さんがフローやん!!って言って通してた.つよい

懇親会

お腹ペコペコだったのでずっと食べ続けていた.他の参加者とお喋りするのも楽しかった

感想

3時間コンテストだとちょっと実装バグらせて時間を溶かすと一瞬で終わるので,4時間コンテストは嬉しかった.チームの他の人達が強くて本当にdiv2か??って思った.

2日目

TTJR さんとyurahuna さんとでチーム名toy18で参加した.18はチーム全員が18卒なことから

A問題

問題に図が書かれていて苦手な算数要素が含まれていそうな問題でつらくなる
適当な式変形をしていたら,yurahunaさんが読んでいたC問題が構文解析らしくswapする
yurahunaさんがかなりつらそうだった

B問題

TTJR さんが通した

C問題

「NLPerは構文解析が好き」,「odan氏はNLPのプロ」という仮定のもとC問題を任された(後者は明らかに嘘)
BNFが書かれているけど+か-でsplitするだけなので,構文解析パートはそこまで難しくなかった

D問題

TTJR さんが取り組んでいて,相談に乗りながらデバッグしていたけどサンプルしか一致しないくて困っていた
yurahuna さんが違うDPの更新式を考え出してそれでACした

E問題

yurahunaさん がFA取っていてプロ

F問題

制約が小さいならフローだけど,大きいので解けるのか??という気持ちになる
yurahuna さんに相談すると答えの値は高々2なことを教えてもらう(プロ)
Kについてのアルゴリズムを考えると,元々ある障害物をDFSで探索すれば良さそうなことになる
助言を貰いながら 置く障害物の個数 dfs(現在位置, 障害物を置いた回数) のmin を取る再帰を書いた
提出するがTLEを貰い,mapunordered_map に書き換えるが,読めないコンパイルエラーを吐かれて時間切れ
コンパイルエラーの原因は hash関数を unordered_map 型の変数を宣言するより後に書いていたのが原因だった

懇親会

ウコンを受け取ってしまい,大変申し訳有りませんでした….
お刺身が美味しかった

感想

5時間コンテストは最後の方お腹が空いてしまうので,つらい
F問題はコンテスト中に通しておきたかったなあ

3日目

omurice__ さんとthreepipes_sさんとでチーム名mod_3 で参加した

A問題

問題文の並び替えて回文にできるようなセットにしたい という部分を見逃していて時間を溶かした

B問題

omurice__ さんが通した

C問題

threepipes_s さんが通した

D問題

omurice__ さんから,問題概要と速度の取りうる範囲が小さいので拡張Dijkstraで解けるとの方針を教えてもらって,そのまま実装した
辺を舐めるfor文内でif文+continueを書いていなくて遅いDijkstraを実装していたせいで,WAをもらってしまった

感想

Dijkstraは,辺を舐めるfor文内のif文+continueはあってもなくても,実行時間はさほど変わらないだろうと思い込んでいたけど,そうではなかったので次からは気をつけたい

感想

今年もRUPCも楽しかったです.来年も開催されるなら参加したい
普段学内でチーム練習する時はわりと殺伐としているんですが,RUPCみたいにワイワイチーム戦をするのもいいのかなあと思いました
運営陣+作問陣の方々,懇親会スポンサーのRCOさん,ありがとうございました