Meta Hacker Cup 2022予選参加記

初めてMeta(Facebook) Hacker Cupに参加したので、参加記を書きます。
AtCoder水（アルゴリズム）、Codeforces青ぐらいのレベルです。（参加を考えている方の参考に） 毎年開催されているようで、Round2の上位2000位に入るとTシャツがもらえます。

結果はRound2まで進出し、2100位台というTシャツをもらえない悔しい結果となってしまいました。来年もし参加するならば、Tシャツを絶対に手に入れたいです。。。

Qualification Round

雑解法

A. 各種パーツをカウントして、被らないように分けるだけ。
B1. 細長いフィールドの時は、条件を満たせなくなる。あとは空きマスを木で埋めてしまえばよし。コーナーケースはそもそも木がない時は必ず条件を満たす。
B2. DFSで周囲を見て条件が達成できるかを確認していく。DFSは再帰だとオーバーフローしたのでスタックで書いた。
C1. 与えられる符号の最初の1文字と異なる文字からスタートしてハフマン符号の要領で構築。
C2. 期間中はわからず
D. 期間中に問題をみなかった

コンテスト中の日記

B2の感想 フィールドがMAX(3000*3000)なので、意外と時間がキツそうと思った。実装が終わって確かめるが、validケースが弱い。MAXケースを自作して実行したら、スタックオーバーフローした。DFSを再帰で書いていたが、どうやら再帰だとオーバーフローしやすいらしい。はじめての経験だった。なんとか打開法を調べているとスタックに積む形にDFSを書き換えるといけるかも？はじめて書くので帰りがけの処理とバグに苦労した。再度、自作のMAXケースを実行。エラーもなく出力できた。提出前にMAXケース作ったのが偉すぎる。順位表を見るとB2で6分の制限を切らしている人がちらほら。自分と同じことをしたのだろう。

この段階で19時。夜にABCとえでゅふぉがあるので、今日はここまでMHCはまた明日。C1,C2,Dが残っているが、点数を見る感じDはきつそう。

C1.モールス信号をモチーフにした符号化の問題。一種類の符号が与えられるので一意に復元可能な符号パターンを残りN-1個作る。200文字まで使えるので適当にハフマン符号化するといける。 C2.C1と異なるのは符号化するときに10文字までしか使えないところ。瞬時符号について調べていた。bit全探索の要領でやると容易にN-1パターン生成できることは分かったが、それが一意に復号出来るのか悩んでしまい提出できなかった。解説を読むとできるらしい。瞬時符号とごちゃ混ぜに考察していたのがよくなかったようだ。少し実験して納得した。学びを得られたのでよしとする。

Dは期間中は全くみていなかった。配点的に解けるものだと思っていなかったが、コンテスト終了後に見るとすぐに方針は立った。だが、計算量が怪しい。連想配列をふんだんに使っているのと、深さ2のBFSを対称の頂点に対して全て行なっているので、ブレがあるものの手元の実行時間で2分半ぐらいかかった。本番中のことを考えると6分制限なのでスムーズにいけば通せそうだが、実際にできるかと言われるとかなり怪しい。解説を読むと、辺が多く出ている頂点（BigNode）を別処理して、2stepでやると計算量が改善するらしい。知らない高速化手法が無限にあるんだなあとしみじみ。またどこかで復習しておこう。一応自分の解法も方針としてはいいらしい。Twitter見た感じだと自分と同じ方針でももう少し高速化できるらしい。

Round1

雑解法

A1. コーナーケースに注意して順列をrotateするだけ（コーナーケースがつらい）
A2. B+A+AでZアルゴリズムをする（これもコーナーケースがつらい）
B1. 座標通りに管理して前計算することで計算量を落とす
B2. 求める式を式変形すると座標の和と二乗和を計算すると、O(1)でクエリを処理できる

コンテスト中日記

A1.順列をrotateして正解の並びにできるかを判定する問題。操作回数が0,1,2の時にコーナーケースが散りばめられている。一番配点が低い割に注意が必要でいやらしい（後にやらかしていることに気づく）。最初にk=0,1,2の時を別処理してから、始点を見つけてから愚直に並びが合うかを確かめる。自分がミスったのは、k=1の時にa!=bならYESとしてしまった。初歩的すぎるミス。なんでvalidが通るのか、一問目なのだから弾いてほしい。
A2.この時点の順位表では、A2を飛ばしている人が多かった。おそらくCを除く4問では一番難しいのだろう。自分もかなり時間がかかった。A2はA1の順列制約が無くなったバージョン。方針としては、A1と似た感じで最初にコーナーケースを別処理して、その他を判定する。コーナーケースは、k=0とk=2かつn=2の二つだと思っている。k=1のパターンは、その他の判定のところで分岐を作ってうまく取り込んだ（正直コーナーケースが網羅できているのか相当怪しい）。その他の判定がメインの問題だが、ここはZアルゴリズムをうまく使って線形計算量で判定した。B + -1 + A + Aの配列でZ配列を作る。Z配列の値がNを超えていれば。rotateで並び替えることが可能。k=1の時だけZ配列を見る範囲を絞らなければいけない。

方針は合っていると思うが、コーナーケース…。A2のチェックをしている時に、A1の本番用の入力を使っていたときに、A1が間違えていることに気づいた。かなり萎えた…。前から順に解いていたので、A1,A2が怪しいとなると、配点的にB2が解けないとRound1の突破が怪しくなってくる。Tシャツがなんとしてでも欲しいので、それだけは避けなければ。

B1.二次元平面上にN点が与えられて、さらにQ個の点が与えられる。各Qに対してユークリッド距離の二乗和を計算する問題。B1は点の座標が3000以内なのでヒストグラムを作って前処理してあげると線形時間（modint使ってるので嘘だけど）で解ける。
B2.自分がおバカすぎて2時間も無駄にした。シグマの式を展開して式変形するとX座標Y座標それぞれの和と二乗和が前計算できていれば簡単に処理できる。これもさっきと同じ嘘線形時間。流石にこれは通ったと思うので無事Round1突破（懇願）。

Cは問題をみたが問題文がむずい。制約が以前と変わったと書いてあったが、いつから変わったのか（コンテスト中？）、以前出題された問題なのか、よくわからなかった。 （後で追記する）

Round2

雑解法

A1 文字種が26種類しかないので、各文字が何文字登場したかを累積和の形で保持できる。判定は要らない文字が前後にあるパターンで場合分けすれば良い。

感想

Round2は3時間で日記をつける余裕もないので、感想を書く。A1は簡単だったが、A2が何もわからなかった。ちらっとハッシュは頭によぎったが、経験値不足で解法につなげられなかった。文字列アルゴリズムや動的wavelet matrixでできないか調べていたが、どれもよくわからず。

結果としては2100位台でTシャツにも届かなかった。A1をもうちょっと早く通せていれば、全然可能性があったので余計に悔しい。

以下は、終了後に解いたものについて書く。 A2 どうやらzobrist hashで解けるらしい。通常はXorで持つところを和で計算すると良い。 セグ木などに乗せると配列の更新と区間和を計算量を落として求めることができる。 条件を満たすかの判定は、A1とさほど変わらずに不要文字が前半にあるパターンと後半にあるパターンで場合分けしてあげると良い。

（その他の問題もupsolveしたら追記する）