UTPC2010

2010年度東京大学プログラミングコンテストに参加。UTPCは初参加だったりする。
コンテスト後の懇親会が楽しかったお。色々なぱない方々に会えた。

Result

26位
00:03 (0) / 00:08 (0) / 00:40 (3)/ 04:20 (8) / 04:31 (1) / 03:05 (0) / - / - / - / - / - / -
12WA 6AC penalty 1007

びみょー。。。
実装問すら解けない辺りコンテストのスタートラインに立ってない気がする。

簡単な流れ

C,D辺りから解いたら最速ACに名前載るんじゃね、とか密かに思ってたんだけど某ターゲットさんが開始前に全く同じこと言ってて、これは無理だと思い普通にAから挑戦。


実地参加だと問題文のプリントが貰えた。ノートで参加なのでこれはうれしい。

A

5教科合計の最高点と最低点を求める問題。


書いて送信したがジャッジのQueueが混んでいた。

B

当選番号の一覧が下のような形式で与えられたとき、手元のくじの当選金額の合計を調べよという問題。

*******1 100
******22 1000

↑******の部分はワイルドカード
なおかつ一つの手元のくじが同時に二つ以上の当選番号に該当することはない。


これも実装問。書く。Queueこんでる。

C

ぷよぷよの盤面が与えられた時、連鎖数を求めよという問題。


書いた。サンプル通らない。ぷよの落下を1段しかさせてなかった。
修正。送信。WA.


おじゃまぷよの場合わけ書こうと思って忘れてた!
PKUみたくサンプルがひとまとまりではなくて、Codeforcesみたいにサンプルが分割されてるからデバッグがしにくい。
来年は要工夫だなあ。
んで訂正してサブミット。WA.なんぞ。適当に直す。WA.


あー隣接するぷよの数数えるときにおじゃまぷよも一緒に数えてるじゃんこれじゃ。
訂正。AC.


これで30分ハマるとか。。。うーんやっぱり実装力弱いなあ。

D

単位の接頭辞(キロとかメガとか)の、それぞれの関係が与えられたとき、
(メガはキロの1000倍、などなど)それらが無矛盾であるかを判定せよ。


去年とかD辺りから少し面倒になってたような。去年出てないけど。
一瞬では方針が立たない。図を描いてちょっと考える。


んーよくわからんが有向グラフ作ってワーシャルフロイドで二点間の最短距離を求めて、それが最初の距離と変わってたら矛盾じゃねーの?
書いた。送信。WA.あらら。


えーと、これだと元にエッジがない場合合わないじゃん。適当に修正。WA.


ていうかサンプル通ってないし。
あーもーこれサンプル確かめにくいよ。テキストファイル3つも4つも作っていちいち実行するの面倒すぎる。


あ、k-最短路が使えるんじゃない?2番目に最短な経路と1番目に最短な経路が同一でなければそれは矛盾。いける!


うおーグラフ全部辺表現に直さないといけない。めんどい!


書いた。サンプルも正しい!
WA.訂正。


WA.
もういいやこれ。萎えてきた。

E

ピクロス(お絵かきロジック)みたいな問題?
NxNの正方形の形にランプが並んでいて、それぞれの行とそれぞれの列ごとに点灯しているランプの状態が与えられるとき、点灯しているランプの状態を一意に決定できるかどうかを判定する。


……うーん?N≦10000??探索とか盤面保持する時点で無理だなぁ。通してる人多いぞ???
よくわからん。


これもしかして「ある一列または一行の全てが埋まったらその行or列を取り除いていく〜」みたいな操作を繰り返すだけで判定できるんじゃ。
O(nlog n)で書いてみる。ソートして後ろから取っていく。
サンプルあわねー。バグとれない。


Aizuのコンテストに続きまたバグゲーかー。才能ねーなー。とばそー。

F

問題の要約がめんどい。ワイルドカードの入ったビット列が与えられたときそれがUTF-8の文字列として正しいものは何通りあるかをmod1000000で求めよ?
↑要約になってない


DPの典型問ぽい。書いてみよう。
1バイトのUTF-8のコードと2バイトのコードと3バイトのコードと4バイトのコードがある。んで形が全部違う。うおー。
まあ別に場合分けすればいいか。substrいっぱい書く。


書けた。
サンプル一個目いきなり合わない。ん???
ワイルドカードに0,1を入れる入れ方は何通りあるかという問題じゃんこれ!!
じゃあDPを変更。全面的に書き直さないと……


お、実装が超楽になった。
サンプルも合った。

送る前に……一応longlong使っておくか。送信。AC.
ふー。

E(再)

サンプルのつじつまを合わせた。送信。WA.くそが!!!

F(再)

方針変更してみよう。
k-最短路で解けそうな気がするんだが、つーか自分の中では解けるに決まってるんだけど、AC数が多いから簡単な解法があるだろう。


一つ単位の関係が決まるたびにDFSで矛盾があるかどうか調べればいいんじゃねーの。


書いてみよう。あーまた隣接リストから行列に戻すか。
書いた。サンプルあった。送信。


RE.あれ、単位の数を100で取ったのがダメだった?一応200もありうるのか?
200に変更して送信。AC.

E(再々)

方針が間違ってるのか単にバグってるのかがなぞい。
O(n^2)の解法で送ってTLEが返ってきたらおそらく方針は合っていると思われる。


vectorつかって行列をナイーブに消す解法を書く。
送信。


AC.


おい!N^2で通るなよ!wwww

I

G,Hはなんだか問題がグロい気がしたので飛ばす。
移動の禁止パターンが与えられたときに迷路を最短距離で抜ける歩数を求めよという問題。


方針を考える。
禁止文字列は10個以下で、それぞれ長さは10以下。
10歩分の移動履歴で多重化した幅優先でいけるか?4^10は100万。
マップのサイズは50*50だからこれじゃ明らかに無理だなー。


うーん、あ、有限オートマトンを作ればノードの多重化はその遷移の個数で抑えられるじゃん。


有限オートマトンどうやって作るんだ?
ぐぐっているうちにコンテスト終了。