ei1333の日記

ぺこい

ACM-ICPC 2017 Asia Tsukuba Regional 参加記

たぷぷー

たぷで書いてみます（？）

0 日目

たぷ！！

ei1333.hateblo.jp

前日はパーカーほしさにこれしてた。前日中にパーカー安全圏まで解けてよかったたぷ！(あとは放置

1 日目

天界からつくばまで

予定より {n} 分遅れて出発したけど, 東京駅についた時間は予定通りですごいっておもってた。

おめでと！！

すやすやしてたらあたまがいたくなった。前日あまり寝付けなかったので(魔界からの妨害？。

ねむい。ねね。つくばにつく。

暇だったため, codesprint で大変そうなbeetさんを煽りに行く。

Tシャツを逆にきていたらしい。去年のわたしのまねなのかな？

Practice がある。Practiceをする。2 完でした。

懇親会に行く。えー木のなりきりアカウントやひふみなりきりアカウントなど見つけたりする。

ARC前にホテルについたので、ARCにでたたぷ。D でたぷをしてしまったため 2WA したけど E が解ける問題だったため結構いい順位。

レートがたぷたぷですごい下がっててねねだったけど、やっと橙に戻った。橙タプリス5回ぶり。(あとこだは事故に優しいとはいえ大事故をすると厳しいため)

ねむいため 12 時ごろねね。ねつけず。

2 日目

7 時半頃起きる。さむさむでふるえてる。サンドイッチ食べて 10 分くらい歩いて会場に。ねむねむ。あとさむい。

開始前トイレがすごいこんでた。ICPCの人気コンテンツのひとつ。すわってるとコンテストがはじまる。

ABCまでは難易度順なので、チームの 2 人にぜんぶまかせてたぷはD問題から読む。英語が読めないため問題を読めない。えーん。

D問題は 2 点消したときの凸包の面積。 {O(N^3 \log N)} ならわかった！！えー変化したところだけみればよさそうというアが浮かぶんですが、コーナケースを考えると眠たくなっちゃった。捨てる。

E問題は塗りつぶす最小回数を求める問題。制約が大きいため貪欲か状態数が線形で済むようなDPをしそう。まず貪欲を考えるたけどわかんなかったたぷ.... ちょっとチームメートと相談してわからないためとりあえずとばす。

F問題は有向グラフ上の頂点1から2への最短距離が, それぞれの辺を反転させたときにどうなるか求める問題。すき。

G問題は幾何っぽいためあとまわし。

ここらへんの段階でABをチームメートが解いててたぷーーー。えーなにもわからないため今年の問題難しくない？難しいたぷって言ってる。

F問題が好きなのでFを相談しながら考える。詰めると、最短路DAGに使われた辺だけ考えれば良くて、その辺のうち必ず最短路に使われる辺はどれか問題に帰着したけど、解き方がわからないのでこまるたぷ。たぷぷ

もうちょっと考えるとこれは無向グラフでみたときの橋なので、もってきたうしさんのライブラリを写すだけで解けそう。ライブラリを印刷してきてよかったって思った。写す。キーボードがUSキーボードなので打ちにくい。時間がかかる。つらくなる。キーボードを打つ力がどんどん強くことに気づいたので、途中まで書いて写すのをなげる。

Eを考える。各要素について操作するのは高々2回で、区間と区間が微妙に被るみたいなことはなさそう。これを考えるとスタックを使う謎貪欲が生まれる。反例ありそうでウクニキア。

F問題のやりのこしたmain関数の部分をちょちょいと書くとせぐふぉする。3分前のことを忘れるため {n} と {m} の役割を途中で忘れて 1 個逆になってた。直すと一発でサンプルが通ってえぇ...ってなる。たぷたぷ喜ぶ。提出するとデバッグ出力をそのままにしていたためWA。たぷたぷ落ち込む。えーん。消すとAC。

C問題が解かれる。すごい。題意が読み取りづらいという話。

Eの反例が見つかる。だみだこり。えーもうちょっと考えると、なんか塗りつぶす異なる区間を何個か選ぶ問題になりました。塗りつぶす区間のコストが求まれば解けそう。（いやここまで考察していて何で解けないたぷね（えぇ....

I問題をみる。ある区間と重複する区間の個数が求める問題に帰着する。3 人で考えるんですが、これは平面走査を適当にすれば解けることがわかり、ちょっと実装すると解ける。

G問題がすごいとかれているのでまず問題文を読もうというという話になる。なんか展開図を考えると実装する問題になるという話になる。実装しているのを応援する係をしています。終了-3秒前くらいにサンプルが通ったらしい(すごい)ので提出する。できないね（終わり（えーところで途中でたぷを忘れてました

13 位だったたぷ。去年の 27 位の半分なので当然来年はその半分をとりたいたぷ。

反省としては解いている人数をもうちょっと見たほうが良さそう（結果論なんですがね....うしさんもうちょっと考察して

終わるとおひるごはん。大悪魔胡桃沢=ウクニキア=マクドウェルさんがメロンパンをちょっとくれる(食事のインターバルが短く食べきれなかったみたいです)。やさしいたぷ（？

あとは解説を聞いて、企業ブース回って、たぷたぷね。おっらてじゃーんをして、滝本ひふみさんと謎コミュニケーションをした。

翌日の1限に間に合わなくなるため途中で切り上げて🐸。ICPCの配信をちょっと見る。ねながらレポートをやる。

3 日目

レポートなんですが、寝落ちしたため大学でやる（ずるい

4 日目

参加記を書く