ABC281に参加した。

A: やるだけ

B: がんばる

C: TをAの総和で剰余をとった上で順に見ていく

D: dp[i][j][k]:=i番目まで見てj個採用してmod Dがkであるような和の最大値

E: mapに値と個数を記録して(K個採用したときの境界値, 境界値の中の採用済みの個数)を記録して順次更新していく感じでやった。セオリー的にはL,Rといった集合を用意するらしい。頭いい。よくこんな力業の方針でペナ出さなかったな？？

F: まずAの値集合を0or1で分岐していく二分木で表す。トライ木と言うらしい。これの一番右の葉ノードの横軸上の位置が最大値になる。

XORを適用するとある段の左右をひっくり返すことが出来る。これをもとにdfsして一番右の葉ノードの横軸位置を出来るだけ左にする。同じ段では一番右のノードしか問題にならないので、左右ひっくり返すかどうかを各ノードで独立に考えて問題ない。

コンテスト中は解けなかった。くやしい。なぜか完全二分木しか想像できない頭になっており、トライ木の記事に載っている普通の二分木を見たら一瞬で認識ロックが解除された。

---

散歩した。レポートも筋トレも何もはかどらないから歩いたりしてみるが何も手に付かない。