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

math314のブログ

主に競技プログラミング,CTFの結果を載せます

ICPC 国内予選 2014

チーム kyutOUki(@__math, @mitaki28, @ustimaw) で出ていました. 6完,6位 でした.

担当分け

A : __math, B : mitaki28, C : ustimaw, D以降は 二人以上でやる予定でした.

練習phase

ミーティングが入っていたので残りの二人で出てもらった,何してたんだろ.

本番

問題文印刷しつつAを読む. "商品の税抜価格として 1 円から s-1 円のすべてを考慮に入れよ." と書いてある,二重ループ回せという意味か.

A 00:05 (AC)

Aが通る.Bは読めたらしいので実装してもらう. Cは幾何らしい,少し難し目に見える. とりあえずDを読んでみることに.

8分くらい

Dわからん…,一方でCも悩んでいるらしい.Cは得意分野に見えたので交換することに.

20分くらい B 1WA

Bが出来たらしいので投げるも1WA. Cは二分探索かとおもいきや貪欲でいけそうなので,Bを印刷してCに交代.

B 00:29 (AC)

間違いを見つけたとのことなので交代したら通った,つよい.

C 00:33

Cの実装が終わったので投げたら通った. Dをmitaki28君,ustimaw君が議論して解けそうな雰囲気を醸し出しているのでEをやることに.

Eは葉を見る必要がないことだけはわかる,とりあえずsampleで遊ぶ. 根付き木について頂点(u,v)を考え,u -> lca(u,v) -> v のコストを最大にすると答えがでそう?ということでO(n3)解を書くことにした.

D 01:01 AC

通ったらしい,この辺りの記憶があまりない. 順位表見ると12位くらいだった気がする.

Eの方針が立ったので交代.

01:15 くらい

なんかバグる…,二人に手伝ってもらう.

dfsやlcaのバグを探るも,原因はinputのindexズレだった.

修正 -> バグる…, 原因はinputのindexズレだった(2回目),ひどい.

その間にF,Gを読んでもらう.

F : サイコロ,G : 幾何 らしい. どうせ最終防衛だろ~と高をくくる.

E 01:33 AC

通った. 後で分かったけど,これは木の直径と一致するのでO(n)で答えが求められる.

実はこの時点で自分だけ残り1時間だと勘違いしていた.

Gは思いつかないけどFはまだ可能性がありそう… この辺りでとても眠くなる.

01:45くらい

"サイコロの目の,どれが上を向いているか","(t1,t2,t3,t4,t5,t6)" の2つから可能かどうかをO(1)で判定出来れば,O(n)で辞書順最小が求められることはわかる. ただし定数?としてnext_permutationの6!とかサイコロの配置の24通りとか効いてくるけど,まあ通るだろ.

"可能かどうか"をどう判定する? サイコロの目の遷移グラフを書いても思いつかない… でもこういう時ってすごいきれいな判定式が出来る気がする… (1,6),(2,5),(3,4)は判定時には同一視して問題ないので,変数はこれらと"サイコロの目の,どれが上を向いているか"の4つ. 前半3つについて,変数をa,b,cとすると,

f(a) <= g(a,b,c)
f(b) <= g(a,b,c)
f(c) <= g(a,b,c)

みたいな式になるに違いない,絶対にそうだ,そうに決まってると自分に言い聞かせて必要条件の式を立てる.

(1,6)のどちらかが上になるには,一つ前の状態は(2,3,4,5)のいずれかが上であるから a <= b + c (+ 1) みたいな式は成り立つだろう. +1つくのかな?

移項すると 2a <= a+b+c(+1) になって綺麗,綺麗ならば正しいのでは?と勝手に納得して説明し始める.

平行して,input読んだりnext_permutationするとかの必要な処理をmitaki28君に頼んでいた.

02:10 くらい

残り20分しかない…(思い込みです),順位は10位前後で解けなくても国内予選は通りそう.

上の式を判定に使えるはずと踏んで,実装し始める. サイコロやべえ…でも実装しないと,ということで,ustimaw君にサイコロの実装を紙で書いてもらいつつ,自分は実装できるところを書く.

02:15 くらい

うーん,サイコロはライブラリにあるからそっちを使うべきでは…と思い始める ustimaw君にその旨を伝えつつライブラリを写し始める. ustimaw君ごめんなさい

写し間違えそうになるとmitaki28君が直してくれたので,ライブラリは間違えなかった. ところでライブラリの使い方を覚えていなかったので,適宜確かめながら書いていた,ライブラリに書いてあるサイコロ回転の方向を表す変数が直感的でないらしい,悲しくなりつつもデバッグ出力して確かめた.

02:25 くらい

もう時間がない,「もうおわりかー」と発言したところ,チーム二人にまだ30分残ってるとツッコまれる. ああ7:30までだった…

そういえば考えた条件式,上を向いている目を使ってない,どこかに入らないとおかしい. "+1つくのかな?" と疑問に思っていた所に,関わってくるのでは?と思い,合いそうな方に+1をくっつける.

02:40 くらい

実装は終わったがバグる,そりゃそうだよな~と半ばあきらめつつもデバッグを開始

02:47

サイコロの目が負の数になるを許容していることが判明する. これを修正するとsampleが合った!!!

F 02:53 AC

Fが通った!!!!!!! 6位だって!!!!! まさか通るとは思ってなくて,周りに他のチームがいることをすっかり忘れて大声で話始めてしまい怒られる,ごめんなさい. 気を落ち着けるためにGを読むけどわからん,なんだこれ.

03:00 終了

お疲れ様でした.

終わった後王将に行ってワイワイご飯食べていました.

G全くわからなかったので,自明に解法が思いつくくらいになりたい.

反省

我を忘れない.