WUPC 2012 参加記
コンテストリンク AtCoder WUPC WUPC2012
早稲田大学の有志の方々によるプログラミングコンテストに参加しました。
制限時間2時間、6問、部分点が存在する構成でした。
以下、結果です
| 順位 | ペナルティ | ||||
|---|---|---|---|---|---|
| 18th | 129:18 | ||||
| A | B | C | D | E | F |
| 02:17 | 58:01 1WA | 13:56 | 19:42 | 54:14 1WA | 99:18 1WA |
全完！
開始前
出先から超特急で帰る
途中お昼ごはんに松屋の「豚しゃぶ丼」を買う
13:50に帰宅する
弁当をかっこむ。これウマイ！！
でも半分残す
開始
難易度順に並んでいるとのことなので順当にA問題から読んでいこう
A読む
日数の差か、カレンダークラスに差を取るやつあったっけなー
え？日付は2012年のしかありえない？
じゃあ楽だわ、1日ずつ動かそう
はい提出ー
Waiting JudgeなのでとっととB読む
ふむふむ、ソートして順にくっつけるだけじゃね？
最後のサンプルが合わない
あー選ぶのは「2個以上」なのか
辞書順で最小なら2個だけでいいよね
s[0]+s[1]が答えだわ
提出ー
勢いでCを読む
うむ、BFS2回やるだけだな
周囲は必ず壁だから範囲チェックもいらないな、素晴らしい
始点と終点決めて最小コスト求めるbfs(始点、終点)を作って2回呼ぶだけだわ
ほい提出ー
どんどん進もう、さぁDだ
三角形、数字、最大値
ほほぅ、DPの典型問題ですな
サイズも100までで大したことない
端の処理に気を付けてガリガリ
ほいっと提出ー
次はEだ
ふむふむ、mod 4とmod 7の情報を持たせた拡張ダイクストラで行けるな。
似た問題をCodeChefのMay Long Contestで見た気がする
えーと、会場についたら引き返せないっと
お、道は引き返してはならない！？
これはめんどくさいぞ、以前にどこにいたかの情報も必要じゃないか
するとノードはN*N*28でちょっとやばい感じ
でも2.8 * 10^7で行けなくもない感じ
んー、まぁ書くか
ガリガリ
書けた
最後のサンプルが合わない
およよ？最後のマップは街が一直線に並んでるから往復なんてできんのでは？
問題読み直す
あー！道を「途中で」引き返してはいけないのか
だから直前にどこにいたかなんて気にしなくていいんじゃん
削除削除
サンプル合う
行ってこーい！
提出
一気に5問提出したった
結果を見るかな
A Accepted
B Wrong Answer
C Accepted
D Accepted
E Wrong Answer
ほげぇ！？
BでWAか、んーちょっとおいとこう
Eのバグを取るか
どこで間違ってるんだろう
・・・おい！
会場についてるときに移動してるじゃないか！ドジ！
修正
提出
E Accepted
Bのバグとり
んー反例反例・・・
あれ？
文字列2個繋げるだけよね？
文字列50個しかないよね？
余裕で全部試せるよね？
修正
提出
B Accepted
BとEのペナルティがアホすぎる...
競技時間は半分丸々残ってる
Fに挑むぞー
開く
図形が見える
ちょっと気圧される
えーと、座標の範囲は1000*1000か
num[x][y]: [0, x]*[0, y]の範囲にある点の個数
という累積和のテーブルを用意すれば、ある長方形の内部に点があるかのチェックがO(1)で出来るな。
[0, x]だとちょっと扱いずらいから、全ての座標を(+1, +1)しよう
問題は、長方形の頂点の選び方だな
左上と右上の頂点を選ぶとうまくいくかな？
各y座標について、点を一列に順序付けて持たせておこう
すると、左上の1点を選ぶと、そのy座標の列で右側にある点だけが、右上の頂点の候補になる
長方形の上側2点が決まったら、1 <= z < yの高さを逐一見ていって、左下の頂点を見つけよう
あとは、右下の点が存在するかをチェックすればいい
これらの内部に点があるかどうかはnumを使う
この処理の途中で、内部に点がある長方形が作れてしまったら処理を中断しよう
それ以上やっても無駄だから
気を付けてカリカリ書く
これ、点の並び方でオーダーが変わる感じだなぁ
まぁ何とかなるだろう
いってこーい
提出
F Time Limit Exceeded (部分点30)
あちゃーダメかー
TLEになってるのは1ケースだけかー
んー、上側2点を決めた後、愚直に1 <= z < yの範囲を見てるのがやばそうだな
実際にこの範囲に存在する頂点の数は少なさそうだ
x座標についても点を順序付けしよう
提出ー
F Accepted
通った！全完だー！
