HUPC2020 3日目
1日目はこちら、2日目はこちら
3日目は、とまとさんるぎうさんとのチームです。
例によって問題は解いた順です。
内容
A
ここはサクッと。全体3番目だったので良かったかと思います。
C
るぎうさんがサクッと考察していたのですが、少しバグって僕がコードを見たりしました。
遅すぎはしなかったのでまぁこれから、という感覚でした。
I
るぎうさんに通ってる(けどパッとはわからない)から見てみてと言われたので僕が見たところ、2,3分で最小全域木→倍数→調和級数、という考察フローを辿れたので即座に実装、ACしました。この問題を軽く通せたのは良かった気がします。
M
僕が考えたりるぎうさんが考えたりしましたが、るぎうさんが最終的に考察を出し、僕が実装するという流れに。
3進数を描きたくなくてmap + stringでごまかす→TLE
基本strnigでmapの部分だけ3進変換→TLE
stringを一切使わず全て3進数で実装→2.82sでAC(TLは3s)
という流れでした。結構オーダーギリギリだから気を付けてとるぎうさんに言われたのにいう事を聞かなかった僕が完全に戦犯でした。
ところで、よくよくこの問題を見直すと、同じ頂点からの辺は高々1度しかみないという、WUPCのJ問題そっくりの問題だったので最初に見た時点で気づけず反省…
B
最初、とまとさんと僕で解法をくみ上げ、たかだかマンハッタン + 2で抑えられますね、という解法(縦横どっちかを先に終わらせた後、残りを計算)を連打してペナを蓄積しました。
結局、るぎうさん一人で考察しなおしてAC…
E
僕とるぎうさんで考察を行い、考察はいいが自分が実装があんまり思いつかないからどうしよう、と話していたところでとまとさんが参戦。とまとさんとるぎうさんの話を聞いていたところで僕が実装イメージをくみ上げ実装していましたが、まず偏角ソートが幾何ライブラリに入っていませんでした。
yosupo judgeで適当にコードを漁り(かつっぱさんのものを参考にしました、ありがとうございます)、それを自分のライブラリに組み込むことで実装を行いました。
が、なぜか偏角ソートの確認でバグって動かず、よくよく見たらお手製サンプルの方が間違っていて時間を溶かしました(つд⊂)ｴｰﾝ
その後実装を終えますが、なぜかサンプルの答えがグラフ全体の面積に。
手元で確認したところ、辺の向きが逆になっていたので書き直すとサンプルが通り、無事AC。
この時点ではまだあまり通っていなかったので、ここをさっさと処理できたのはよかったです。
この時点で、あと通せそうな問題がG(るぎうさん)、F(とまとさん)に加えて +1問(J,Kのいずれか)になり、これが全部通れば結構いいのではないか、と思っていました。
G
カツサンドの問題ということ以外何も知りません。気づいたら通っていましたシリーズです。ありがとうございます。
F
問題を見終えて割とはやい段階で、swapが定義できること、 GYYというものがあったときに GRR もしくは GBB に変換できること、がわかり、後は細かい部分を詰めればいけそう、という話をとまとさんと二人でしていました。
が、そこから嘘解法にひたすら走ってしまうことになり、結局最後まで通せず…
最後にるぎうさんが駆けつけてくださりましたが、間に合いませんでした。
結果
もう一声欲しいですね(2回目)
反省
BやFで、とまとさんと僕が2人で嘘解法を投げまくっていました。
とまとさんの実装スピードがせっかくはやいのに、僕が嘘に気づけず修正ができないのが弱点な気がします…
今後は、るぎうさんが考察のかなめになり、嘘っぽい解法で炎上しかけた際はかならずるぎうさんに見てもらおう、という話になりました。
そのためにも、るぎうさんの考察は僕ととまとさんが実装(実際、僕は変な実装でなければ基本的にスピードがそこそこで、とまとさんはスピード + 安定感があります)することになるので、練習しておこうと思います。
おしまい
3日間はやっぱり多少疲れました…
楽しかったです、運営してくださった皆様ありがとうございました！
弊学チームはACPCでまたボコボコにしたいと思います。
