2021-03-17

AtCoder Heuristic Contest 001

AHC001に参加し、

pretest 48,180,294,618 点で 227位/1370

system test 961,756,505,063 点で226位/1407

でした。

何かの役に立つかもしれないので、マラソン中に行ったことなどを記録しておきます。

初日

テスト駆動開発に憧れがあったので、長期間のマラソンはRustを使い、単体テストを書きながら実装を進めることに決めていました。

問題を確認し、拡張・移動などができる矩形クラスがあると便利そうだなぁと思ったのでまずはそこから実装をはじめました。

その後、それぞれの広告を面積1の正方形からはじめて、+x/+y/-x/-yの4方向に他の広告とぶつかるまで拡張するような実装を行い、正の点数 45,272,241,873 点を得ました。

f:id:coco18000:20210317221140p:plain

初日(seed : 1)

2日目

初日の方法だと4方向を他の広告に囲まれているような広告の面積が伸び悩みます。

そこで初回の拡張後、各広告に対して

・可能であれば面積を保ったまま、いずれかの方向に平行移動

・目標面積に到達していない&更なる拡張が可能な広告の面積拡張

を繰り返し行い、46,716,891,361点を得ました。

f:id:coco18000:20210317222549p:plain

2日目(seed : 1)

ちなみに2日目以降、テストコードは全く書きませんでした

３日目

2日目までの実装だと、面積が目標値に達した広告の形状はそれ以降変わりません。

そこで、面積をある程度保ったままx軸方向やy軸方向に引き伸ばすような処理を入れ、47,356,764,995点を得ました。

f:id:coco18000:20210317223830p:plain

3日目(seed : 1)

4日目

3日目までの実装は実行時間に余裕があったので、ヒューリスティック的な探索を導入してみようと思い、平行移動時の移動方向を全通り試し、上位数個を採用するビームサーチを実装しました。

思いのほか効果が現れ、48,090,523,361点を得て、目標の480億を超えることができました。

f:id:coco18000:20210317224909p:plain

５日目以降

その後はランダムに選んだ広告を破壊したり、広告の拡張処理を高速化してループ数を増やしたりなどしていましたが、思ったような結果は得られず、最終得点の48,180,294,618 点に落ち着きました。

感想

存在は知っていながらも、真面目にマラソンに取り組んだのは初めてでしたがかなり楽しむことができました。

長期間のコンテストも初めてでしたが、マイペースに取り組むことができ、自分の性分にあっているような気もしました。

今後もAtCoderではマラソンコンテストが定期的に開催されるそうなので、より精進して行きたいと思います。

2020-08-24

Rustにおけるパターンマッチメモ書き

タプルなどの一部にのみマッチ

matchの中でif文を用いる

タプルとrangeの併用

2020-03-08

Present (Codeforces #626)

codeforces.com

Xor Sum 5 !

問題概要

長さNの数列 $a_1, a_2, ... , a_N$ が与えられる。

$\begin{aligned} \left( a _ {1}+a _ {2}\right) \otimes \left( a _ {1}+a _ {3}\right) \otimes \ldots \otimes \left( a _ {1}+a _ {N}\right) \\ \otimes \left( a _ {2}+a _ {3}\right) \otimes \ldots \otimes \left( a _ {2}+a _ {N}\right) \\ \ldots \\ \otimes \left( a _ {N-1}+a _ {N}\right) \end{aligned}$

を求めよ。
ただし、 $x \otimes y$ は xとyのbitwise XOR を表す。

$2\leqq N\leqq 4\times 10^{5}$
$1 \leqq a_i \leqq 10^{7}$

考察

xor操作の基本に習って、「あるビットに注目した時、そのビットが1となる物がいくつあるか？」を調べたい。
$a_i + a_j ,(1 \leqq i \lt j \leqq N)$ の各ビットが1となる物がいくつ存在するかを調べてみよう。

$a_i + a_j$ のbビット目の値は $a_i$ のbビット目以下の値と $a_j$ のbビット目以下の値にのみ依存する。
具体的には $(a_jのbビット目以下) + (a_iのbビット目以下)$ のbビット目が1であれば $a_i + a_j$ のbビット目は1であり、0であれば $a_i + a_j$ のbビット目も0となる。

ここで、 $Xのbビット目が1 \Leftrightarrow 2 ^ {b} \leqq X \lt 2 \times 2 ^ {b} or 3 \times 2 ^ {b} \leqq X \lt 4 \times 2 ^ {b}$ であるから、 $a_i$ を固定して考えると、 $a_i + a_j$ のbビット目の1の個数は $2 ^ {b} - (a_iのbビット目以下) \leqq (a_jのbビット目以下) \lt 2 \times 2^{b} - (a_iのbビット目以下)$
、または
$3 \times 2 ^ {b} - (a_iのbビット目以下) \leqq (a_jのbビット目以下) \lt 4 \times 2^{b} - (a_iのbビット目以下)$
となるような $a_j$ の個数に等しい。