HTTF2020本選参加記
この記事は、NITKC Prolab Advent Calendar 2019 の17日目の記事として書かれています。
前日は宮野さんの記事です。
まえがき
とばりといいます。
最近は友人が思いついた問題(有名な未解決問題だった)に軽い気持ちで挑んでいます。解けるかなんて知りません。
それはそれとして今年は8月からほぼ一か月に一回のペースでオンサイトコンテストに出向いているんですよね、焦点の定まらない生活を送っています。
今回は、その中でも、12月7日 に行われたHack To The Future 2020 本選 についてお話します。
HTTF
予選と本選があるマラソン形式の8時間コンテスト
予選問題 : HACK TO THE FUTURE 2020予選 - AtCoder
本選問題1 : HACK TO THE FUTURE 2020 本選 - AtCoder
本選問題2 : HACK TO THE FUTURE 2020 本選 2 - AtCoder
日記
本選は12/7(土)に東京で行われたのですが、僕は福岡県にいつもいるので
12/6(金)旅立ち
12/7(土)本選
12/8(日)帰宅
みたいなスケジュールにしました。
これはあたりまえなのですがあたりまえのような金曜日の授業は欠席されました。
1日目
旅立ちの日
— とばり (@toritobaritori) 2019年12月6日飛んだ
これは前日の脳内
明日東京、どこ行こうか
— とばり (@toritobaritori) 2019年12月5日
秋葉原に行ってください、次にヨドバシカメラによってください、そのあと東京タワーに行ってください。
こんな声が未来から聞こえてきました。
秋葉原に行きました。
ここで！ラジオ会館を登っていると、†ドルフィードリーム†というどこかで見た文字が！！！ 偶然です。運命でしょうか。
ドール界隈についてはぜんぜん知らないのですが、実は少し前からドールに何かを感じて一から紙粘土で作ろうとしていた友人がいて、ドールの文化に初めて触れたのはその辺です。
ドールって、フィギュアとは違って関節が動いたり、目は眼球を模していて、人形に生命が宿っているように感じるところがとても魅力的なんですよね。思わず写真を撮りたくなる。。。
ドール、、、いつの日か、、お迎えしたい。。
次ですが僕は今回デジタル一眼レフを持ってきていまして、NikonのD3400なのですが、、このレンズをいろいろ見たいとのことでヨドバシカメラによりました。
やすくて5万、ぼくは何をしに来たのだろう...
このあと東京タワーによったのですが、外観はとても美しい、しかし、入ってみると低い、東京タワーは外から見るものなのでしょう。
2日目
本選当日です。
朝は早く起きてお食事券を使用して朝食を食べて元気を出します。本選を頑張る決意をしました。
雨の中、傘もなく、道に迷った末、無事集合場所にたどり着きました。
上と下は趣味に書くべき内容なんですがここでプロの内容を書きます。
(これは技術要素ですか？いいえ)
本選
今回の本選では、作問ミスがあり、8時間マラソンが4時間、4時間のダブルマラソンとなりました。 それぞれのコンテストで僕がどんなことをしたのかを書きます。
問題の概要
xy平面上のN個のノードの集合Vと、S個の木Tiが与えられる。
Vにおいて与えられたノード間にはノード間の距離がある値以下であれば辺を張ることが可能。
与えられたS個の木のそれぞれのノードとVのノードを対応づける。
このときできるだけグラフと木がマッチする(Gの無駄な辺が少ない)ような辺の貼り方とノードの対応づけを行ってください。
コンテスト(問題1)
最初に実装したのは以下のようなものです。
まず、Vで張れる辺はすべて張っておきます。ここでできたグラフをGとします。
Gから平面の真ん中近くにあるノードを選択します。
次に、Sから入力順に木Tを一つ選択します。
Gから選んだノードを木Tの根に対応付けて、Tに従ってGをDFSして、TとGのノードの対応付けを行っていきます。
ここで、各Tに対して同じGの頂点からDFSを行っていきました。ノードの被りや辺の被りも全く気にしないコードをまず書いて、TがGにそもそも埋まらない場合はエラーとしてお祈りのコードを書きます。
最後に使わなかった不要な辺をGから削除します。
ここで初の提出を行いました！！
迫真の！ 0点！！！
だいたい予想どおりの結果でWAが出なかったことに安心します。
(なんかこの時点で2時間たっていてなんと満点が数人。実装力ダメです。頑張ってください。)
この辺でchokudaiさんがやってきまして、コンテストが二分割されることが決まりました。
ここから満点を目指して実装を頑張ります。
次は、それぞれのTの根に対応付けるGを乱択しながら頑張ります。
適当に出してみると、95万点が取れました。うれしい。
しかし、これ以降点数は上がりませんでした。
バグなどと戦った末、やり残したことがたくさんでした。
コンテスト(問題2)
問題2は問題1の制約拡張版でした。
木のサイズが大きくなって可変となり、辺の制約が少し厳しくなりました。
本番はここからだ！と気合を入れて実装をしました。
といっても問題1のコードにやりたいことを追加していくだけです。
実装したのは以下のようなアルゴリズムです。
Gのサイズに対して木のサイズが大きくなったため選んだ根によってはGとTの対応付けができない場合があるー＞あるノード(子)から先が対応付けできないならば、DFSバックトラック時に対応付けをもとの状態に戻して、次の子で試す。
木単位で根を選びなおして対応付けを変更し、スコアの上昇があったときにそれを採用する山登り。＜－あまりぎりぎりの制約でなさそうだったので貪欲で十分強そう。
Tの各ノードにおける子の順番の変更(山を登りきってそうなときに)。
これらを実装しました。しました。したはずでした、、、、、
点数が、、、27万点、、、、、
結局これ以上伸びませんでした。
対戦ありがとうございました。
点数が伸びなかった原因(バグ)
僕がバグ埋め小宮になっていたことが後日になって分かりました。
どんなバグ？
一度バックトラックが起こるとTがGに埋まらないという判定になって根の変更まで戻ってしまうというバグです。
バックトラック時の判定が親を通り越して伝わっていたんですね。
まぁ時間もなくて焦っていたのもあるんですがDFSのバックトラックにおける勘違いはここだけの話ではなく無限回起こしたことがあるのでいつも気を付けています(気を付けています(素振りしています(素振り！)))
本番では素振りしましたが(ア！)
これ、JOI本選でも同じようなことをして春を逃しています。お疲れさまでした。 (WAの光景が目に焼き付いて離れませんたすけて)
懇親会
懇親会ではとてもおいしい料理が無限にわいてくるテーブルが用意されていて、たらふく食べさせていただきました。ごちそうさまでした。
主にユースの人々と競プロのことについてや本選問題についてなどの会話をしました。
楽しかったです。
三日目
朝食、TLEしまして、秋葉原にもう一度ドールと音楽機器を見に行きました。
技術書同人誌など売ってるところにも行ってみて回りました。
ここでたべたのは朝食兼昼食
おいしかった。ただ朝食兼昼食にはちょっときつかった。
その後、小説読みながらフライトをしました。
博多に戻っての夕食
博多駅周辺を歩いていたら神のような店を見つけ、即決で食べました。
👼おいしい.......
しろごはんのやさしい甘さがわかる人はみなさんここに行ったほうがいいと思います。
こうしてHTTFの旅が終了しました。
あとがき
遅刻しました。ごめんなさい。
睡眠の誘惑にはどうやっても勝てなさそう。
これでとばりのAtCoder初オンサイト参加記を締めさせていただきます。
次の日の担当はhunachiさんです。
