【ABC361】 ABC361にやられました…
どうも競プロerの緑抄と申します。今週のABCは寝不足と実装をバグらせてパニックになって普通に4完しかできませんでした…。ただ時間内にE、Fを考えた方針は合ってて時間が足りてればかなり勝てたセットだったので悔しいところではあります。ということでFまでの問題に対して復習をしておきたいと思います。
A - Insert
いつものやるだけ枠です。いや本当にinsert使うだけ…
実装例
B-Intersection of Cuboids
いや急に殺意高くないですか？！要するに全部の座標系で二つの区間が交わっていることを書き起こせばいいのですが直接書くのが面倒すぎてかなり狼狽しました…。ただ交わらない条件の方が書きやすいことだけ気をつけて気合いで書きました。
区間が区間で交わらない条件は区間を[a, b], [c, d]としたときb<=c || d<=aなので覚えておいていいかもです。
実装例
C - Make Them Narrow
順当な枠きました。とりあえずsortした方が扱いやすそうなので一旦sortします。するとできる限り最大と最小を小さくしたいということは要素間の幅を一番小さくした、連続したn-k個の要素だけ残す場合だけ考えればよく、その最初と最後の差の最小値だけ計算していけばいいです。
(私はsortしたことを忘れてBTreeMapで管理してしまっていました！そのため一応載せはしますがこの提出コードは参考にしないでください！)
実装例
D - Go Stone Puzzle
この問題を見て少し考えた末、思ったことは「うわぁ…めんどい…」でした…。やり方自体はシンプルで空白を含まない連続する2個を選んで空白に嵌めるという遷移を繰り返すだけのBFSです。では何が面倒か？それは黒、白、空白の3状態を長さn+2分だけ持ちつつ逆戻りを防ぐ→hash化して遷移しなきゃ…と。配列やタプル直接でもいけなくはないとは思います。これで計算量を見積もれば$${3^{16}\leq5.0×10^{7}}$$なので十分間に合うのですがちょっと面倒くさかったです。あと後ろに空白を含む場合を弾き忘れたのに気づくまで10分、実装に合計50分もかかってしまいこれで事実上敗北しました…。どこに空白があるかを別の添え字に分離してもいいと思います。
とにかく高速にDFS、BFSはかけないとダメですね…。
実装例
E - Tree and Hamilton Path 2
これ以降は時間切れで時間内では解けてないですが解説もTLも見ずにその後解けたのでそのままやっていきます。
まず条件設定から木構造になっているので全てを巡って戻ってくるならば全部の道路を2回ずつ通ることに気づきます。ならば同じところに戻ってこないという条件緩和を行うとどうなるのでしょうか？
これは閉路の最初と最後の町の間の距離だけ削ることができるということです。よって求める長さが最小になるのは最初の街と最後の町の距離が最大になるものを選んだ場合なのでこの距離の最大値を高速に求められればいいです。
ではどの様にして町同士の距離の最大値を計算していくのでしょうか。これは実際に木を描いてもらうとイメージしてもらいやすいですがまず根を一つ定め、そこからDFSで情報を統合していくことを考えます。各頂点に対してその頂点以降での距離の最大値と葉からその頂点まで向かう場合の距離の最大値を計算します。この情報からその頂点を通る場合の距離の最大値と今まででの距離の最大値を統合してまた同様に計算すると繰り返していくことで$${O(N)}$$で距離の最大値を計算することができました！
実装例
追記:
この木での距離の最大値は木の直径と呼ばれある任意の点から最も離れた頂点を求めさらにそこから最も離れた点を求めることで計算できるようなので慣れたらこっちの方が簡単だと思います。
F - x = a^b
ぱっと見「え、それだけ？」と思いましたが制約が$${N\leq10^{18}}$$とかなり大きいです。基本的な方針としては小さい方から全列挙していくということになりますが工夫が必要そうです。
この制約の場合3乗以上で表されるものに関しては$${10^{6}}$$以下しかなく、1以外の各数字に対しては$${O(logN)}$$で、累乗で計算できるため十分高速に列挙できます。そのためあと数えるべきは上の列挙を行う際に一度も出てこなかった$${\sqrt{N}}$$以下の数の個数です。あとは平方根の値だけ計算して実装すれば終わりです。正直Dよりずっと簡単です。
実装例
最後に
今回のセットはおそらくDが後ろに置かれてれば普通に5完できたと思われるのでかなり悔しいです…。でも重実装を高速に実装できないと多分上がれないのでこれも経験として演習に励んでいきます…。ここまで読んでいただいてありがとうございます！精進頑張ってください！
この記事が気に入ったらサポートをしてみませんか？