2015-06-26

ICPC2015 国内予選参加記

ICPC

チームnegainoidoで昨年と同じメンバーのflowlightさん, Tailedさんと参加。
8問中7問解いて、全体1位をとれました。

解いた順番とだいたいの時間は

A 7分
B 13分
C 20分
D 61分
F 96分
E 123分
G 162分

でした。

始まる前のチームの戦略としては、

自分が全ての問題を実装する
自分がA,Bを解いている間に、TailedさんはC,DをflowlightさんはE以降を開始直後から考えてもらう

というものを考えていました。

A

一昨年のA問題に雰囲気が似てると思いながら、書きました。
http://pastebin.com/bVRXh8Gd

B

A問題より問題文が理解しやすいと思いました。
http://pastebin.com/SFBjS17A

C

Tailedさんに概要を伝えてもらい、実装しました。
足し算と掛け算を逆に書いてサンプル合わなかったりしました。
http://pastebin.com/LYZWZDub

D

このへんから難易度が急上昇してましたが、flowlightさんがDPを考えてくれたので、実装しました。
何個目の商品、500円玉の枚数、500円以外のお釣りの合計という状態で最小コストを持つDPでした。
お釣りの計算や、使う千円札の枚数などで結構バグりました。
このへんでプリンタがなぜか印刷できなくなってしまい、紙デバッグが不可能になりました。
E問題を書こうとした時に間違ってソースコード消しました。

F

Dまで終わった時点でEの方針が立っていなかったのと、Eが自分には無理そうだったのでFをflowlightさんと考えました。
その間、Gが出来そうと言っていたTailedさんにライブラリを写経してもらってました。
自信は無かったのですが、全域木を片方の会社の辺だけでつくり、最も得する辺を交換していくという貪欲を二人とも思いついたので、
Tailedさんからバトンタッチして実装しました。
解法があっているか分からなかったので、flowlightさんには若干渋い反応をされましたがACできました。
http://pastebin.com/VnSYj8mM

E

自分がFを書いている間に、flowlightさんがEを解いてくれていたので、解法を聞こうとしたのですが、
flowlightさんに書いてもらったほうが早そうだったので、書いてもらいました。
77uのサンプルだけ通らないと言っていたのですが、自分自身でロックしたものをロックしようとすることがあると言ったら、すぐ修正して通してくれました。
http://pastebin.com/QQbLDSit

G

Eを解いた後は、TailedさんにGをずっと書いてもらいながら、自分とflowlightさんでHを考えていました。
すごく長いライブラリの写経でコンパイルエラーを沢山出していたので、キーボードを自分と変わってもらって3人でペアプロしました。
サンプルが丁寧だったので、バグを少しずつつぶしながらACできました。
http://pastebin.com/yaBJNzSi

残り

flowlightさんが最後にロボが集まる場所の候補を絞ってくれたので、最後20分弱でHを実装していたのですが、間に合わず終わりました。
縦棒のチームとは結構激しいデッドヒートを繰り広げていたので抜かされないか冷や冷やしてました。

その他

ひどい詰まり方をする問題がなく、多くの問題が解け、いい順位が取れたのでとても嬉しいです。
チームメイトが自分が解けない問題を解いてくれたので、感謝の気持ちでいっぱいです。

当日は去年の成績が良くなかったのと今年で最後というプレッシャーで胃がキリキリしてましたが、ありがたいことに研究室の先輩に胃薬をもらえたので何とか凌げました。
終わった後、もとチームメイトのpepsin_amylaseさんとy3eadgbeさん(コーチ)に台湾料理ごちそうになりました。

2015-02-25

Codeforces Round #293 (Div. 2)

Codeforces

http://codeforces.com/contest/518/room/1008

C. Anya and Smartphone

アプリ使ったら一番目までくると誤読してタイムロス
サンプルをシミュレートすべきだった

D. Ilya and Escalator

表示桁数調整せずにcout使って1WA
メモ化再帰がバグっていると勘違いしてループのDPに書きなおしていた

E. Arthur and Questions

前から埋める場合を書いて、コピペしたあと後ろから埋める場合のコードを書き換えるのがおかしくて2WA
0 <= i < nの半開区間を意識すべき

F. Pasha and Pipe

いくつまで空白が続いているかの実装をメモ化再帰でサボろうとしたらTLEになった
pretestが弱くて、結局システムテストで落ちた
他の人のコードみて、今まで見てきたやつを捨てる場合を考慮し忘れていることが分かった

その他

A,Bはこれ以上のパフォーマンスは難しいと思った
D,Eはミスらないようになりたかった
Fはプリテストもう少し強くしてほしいと思った
注意力の欠如
全部のプリテスト通った段階で部屋と順位表見たらハック無双している人たちがいて、順位の期待値を上げるには順位表のこまめな確認も大切と思った

2014-07-14

ICPC2014 国内予選参加記

雑記

いろんなチームの人たちが書いてみるのをみて、自分も書いてみようと思いました。

チーム構成

自分(atetubou), flowlightさん、Tailedさん
担当としては、実装、実装&難しめの問題、幾何という感じの予定だったと思います。

結果

http://icpc.iisf.or.jp/2014-waseda/domestic/results/
5完ペナルティ 20135 18位

流れ

A

自分が読む。
去年A読んで頭が真っ白になったのとがトラウマだったが、なんとか書けそうだったので書く。
6分くらいでAC

B

Tailedさんが読んでいたので、内容を聞く。
かけそうだったので、実装に移る。

落ちる処理がバグっていて、なかなかサンプルが通らず焦る。
18分くらいにACだったと思います。

たぶんこのあたりから泥沼だったと思います。

C

Tailedさんとflowlightさんが二分探索すればよいと言っていたので、Tailedさんに書いてもらう。
サンプルがなかなか合わないといって、自分以外の二人でデバッグしたりしていた。
Dを書いているあいだにデバッグが終わらないような感じだったので、印刷されたのを見る。
入力がちゃんと取れてない。

直すとサンプルがあったので出す。
１回目はあったのに、2回目でWA。

何が間違っているかわからずに、ひたすらコードを見る。
誤差とか、提出するファイルみすったかとかいろいろ考えたが、Tailedさんが調べるべき座標として円の両端を入れてなかったので、入れたらAC
3回くらいWAだったと思います。