ICPCアジア地区予選2020 参加記
はじめに
競プロの大学生で最も大きな大会，ICPCのアジア横浜地区予選に参加してきました．
予選の話は↓です
時系列順に参加の様子をお話しします．
本番の様子
予定通り，僕(xryuseix)，cre_chanはA問題へ，jubileusssはB問題に行きました．
開始直後，A問題はめっちゃ難しく感じた．内容はこんな感じの
NNNの立体空間の中に111のキューブが設置されています 3方向から見えるキューブの配置(二次元平面*3)が与えられるので，その全てを満たす図形が存在するか答えて(N<=100)
僕は復元までが問題だと誤読しててむずいいいいって思ってたけど違ったぜ． ある場所にキューブがある場合，三方面から必ず写っているはずなので，解法としては
x,y,zを全探索してその座標の二次元平面に映るキューブの個数を数えて，それが3の場合は(コピーしておいた別の)二次元平面からキューブを削除，最終的に(コピーしておいた別の)二次元平面にキューブが映ってなかったらOK
ってなった．この問題は割とすぐ思いついて考察も実装もほぼ僕がやったのですが，座標軸バグらせてcre_chanと修正してました．(0:37でAC)
とかデバッグやってる間に気づいたらjubileusssがB解いててはええええええええ天才だってなった(例年だとBかなり難しくないですか？問題は見てませんがむずそう)(0:25AC)
この時点で順位表を確認
11位じゃんいけるぞxjubi_chanx！！！(※調子に乗りました)ってなってました．
一般的に難易度シャッフルのコンテストではみんなが解いている問題は簡単そうなので，それから解きます．実際に簡単であることが多いです．
しかし初体験なのですが，この時点C以降の問題は他のチームがほとんど解いておらず，どの問題に行くべきか迷いました．
とりあえずcre_chanはCへ(順に問題を読む予定だった)，僕はJへ(なんか二人解いてるので)，jubileusssはGかHあたりを読んで無理とか言ってました．
でなんだかんだグダってJが数人解かれたあたりでJを通すムーブになってました． Jはこんな感じの問題
木があって，その中にナッツが置かれています．今いるますの隣にナッツがある場合，ナッツを押し出すことができます．行ける頂点集合の個数を答えてください．(<=1e5)
これのアルゴリズムは言われた通り動かせばいいだけなんですが，場合分けがしんどかったです．Aと同じく，考察実装をメインで僕がやって，デバッグ補佐でcre_chanに手伝ってもらってました．
解法としては
とりあえずdfsで進む．今の位置にナッツがなければdfsを続ける．ナッツがあるとき，ナッツを転がす先が1箇所の時はナッツを転がして，dfsをしたのちに元に戻す．2箇所以上の時はナッツがなかったことにする．0箇所の時はその頂点にこなかったことにする．
って感じでした．これ考察は30分くらいで終わったのに実装で1時間以上バグらせてごめんなさい...って無限になってました．(1:51AC, 3WA)
次にみんなが解いてたGへ
問題はこんな感じ
頂点に重みつきのグラフが与えられる．ある閾値Xとした時，X以下の頂点とXより大きい値の頂点を結ぶ辺を削除し，その後全ての頂点が次数2以下，かつ追加できる辺は頂点の重みがX以下とXより大きいもののみであるような辺を好きなだけ追加する．このときに全ての頂点が連結となるような最小のXを求めなさい
僕らの解法としてはこんな感じ
とりあえず座圧してXを固定する．辺を重み順にソートして，Xを増やしながらUFをした結果を保存しておいて，その後再度連結が可能かどうかを判定する
最後の部分がうまくいかず，グダグダして5WAして終わってしまいました......
最後に
みんな強すぎて日本は安泰だなって気持ちと，彼ら彼女らは多分宇宙からきたんだろうなって気持ちと，自分は人類最強かなって気持ちが湧いてきました． 来年も出るので頑張ります．
