第2回WUPCオンサイト 参加記
早稲田大学の有志主催の第2回WUPCのオンサイトに出場してきました
13:00集合とのことでしたが、私用で遅れて13:45頃に到着。事前に遅れることを伝えていたが申し訳ない...
お昼がまだだったので、ツナマヨおにぎりを放り込みながら準備。
すぐ終わり、5分ほどついったー
情報によれば、オンサイト参加者内で5番以内に入れば賞品が貰えるとか貰えないとか
結果
| 問題 | 結果 | 時間 | ソース |
|---|---|---|---|
| 団子とうさぎ | AC 50 | 01:45 | ソース |
| 雨上がり | AC(1WA) 50 | 11:12 | ソース |
| 至高のケーキ | AC 75 | 30:35 | ソース |
| 5キューブ | AC 75 | 61:01 | ソース |
| 独立記念日 | AC 100 | 132:04 | ソース |
| 僕は宇宙人 | AC 100 | 92:42 | ソース |
| だるま落とし | 部分点 20 | 157:11 | ソース |
| ダイヤグラム | 部分点 10 | 164:44 | ソース |
| その味は甘くて | 部分点 50 | 212:07 | ソース |
530点 217:07
全体 26位
オンサイト 4位
ｳﾋｮｰ！というわけでいただいたUSBハブです
以下思考の変遷です
団子とうさぎ
二乗総和の式使うだけだよな！？！？
出す
AC
雨上がり
ぱっと見て、
dp[x]: 位置xに至るために踏む水たまりの最小個数
書く
出す
WA
ほげぇ！？
バグ発見
直す
AC
至高のケーキ
階段状の探索ループ書くのがめんどくさい！
1. 何かいい手はないものか...
2. そんなの考えるより手を動かした方が速いのでは...(1へ戻る)
結局ごり押しで書くことに
出す
AC！！
よかった
5キューブ
でかい奴から順に埋めていけばよさそう。
でかい奴を埋めて、余ったところに小さいのを効率よく入れる感じ
3, 4, 5のブロックは、絶対に1個しか入らないので、大きさ2、1のブロックについて余った空白をどう埋めるか考えればいい
で、まとめると
5のブロック使う：空白なし
4のブロック使う：61個の1のブロックが入る
3のブロック使う：7個の2のブロックと、42個の1のブロックが入る
2のブロック使う：最大8個入り、125-8*(2のブロック数)の1のブロックが入る
あとはifでもぞもぞ
出す
AC
おｋおｋ
独立記念日
む、グラフ系か
閉路が1つしかないと、ふむふむ
んー
閉路が無いときは、どこ切っても必ずグループが1つ増えるから辺をソートすれば行けそう
閉路があるときは、閉路のうち1本を切ってみれば、閉路が無いときと同じ状態になるからなんとかなりそう
サンプル見る
え、グラフは連結でないときもあるのか
混乱
飛ばそう
僕は宇宙人
読む
問題のサイズ的にギリギリメモ化DPできるんじゃね？
(i, j)のマスから向きdirを考えた時、文字cにぶち当たる歩数を前計算しておくといい感じ
書く
AC
よっしゃ
ここで、残りの3問に全て目を通す（通したハズ）
独立記念日
何とかなりそうなのはこれだな
んー
あれ、閉路から1本とれば閉路が無い場合になるんだよな
閉路がある場合は、閉路を切る解の場合と、閉路を切らない解の場合がある
閉路を切らない場合、閉路の辺以外をソートすればいいんじゃ...
頭でまとめる
つまりこうなる。Kを分けたいグループ数として、
閉路なし：ソートして小さい方からK-1本切る
閉路あり：閉路の辺でないものをソートし、小さい方からK-1本切る（K個に分けられないケースに注意）。また、全ての辺をソートし、小さい方からK本切る。これらの最小値が答え
グラフのグループ数や閉路はDFSでがりがりと
書く
出す
AC!!
だるま落とし
後半3問は難しそうだから部分点狙いにシフトするか
部分点はやるだけ問題
書く
ちょっとバグったりする
提出
部分点get
ダイヤグラム
部分点2種類あるけど、一番点の低い奴しかできそうにない...
書く
部分点get
その味は甘くて
六角座標とクエリとかまじ勘弁す...
ダイヤグラムより、大きい方の部分点をとれる感じがしたので50点を狙いに行く
んー
素直にシミュレートするとTLEだなーー
とりあえず、座標を2次元上でプロットしてみるかー
ちょっぴり規則正しそうな形になることに気づく
これ、X座標毎にsegtree作って、範囲に対して+1するクエリを処理すればいけんじゃね？
segtreeとか久しく触れてないので、ここで蟻本を読む！！
持ってて良かった蟻本！
コンテスト中なのに、segtreeの練習とかしちゃう
うまく動いた、行けそう
クエリ数は10000
シミュレートに登場する座標の範囲はxもyも-1000〜1000
つまり2000*2000個しかない
dat[2048][4096-1]のsegtreeを用意
[a, b)の範囲に+1するクエリと、
点(x, y)の糖度を計算するクエリを書く（葉から根に向かう時に通るノードの総和）
座標は+1000してやれば負の値が消える
ガリガリ
提出
部分点get！！
満点ではないけど嬉しい結果に！！
ここいらで割といい順位につけていることに気づいて２８２８する（20位以内にいた）
最後にだるま落としに挑戦する
だるま落とし
んー、BITを使うっぽいんだよなぁ...
でも途中のブロックを吹っ飛ばした時どうすんだろう
あれ？
その点を0にするだけでいけるのでは
書く
サンプル合わない
ここで終了
講評・表彰式
リクルートコミュニケーションズの方々(確か)のお話とか
記念撮影とか
懇親会
早稲田学内生の方々とおしゃべり！！
感想
とても楽しいオンサイトでした。
スタッフの皆さまありがとうございました！
