ARC146

2完。ARC前にプロセカのイベスト読もうと思ってたらギリギリ間に合わなかった(8話途中で中断してARCへ)。そういえば先週のAGCで意気消沈してから競プロなんもやってなかった。

A - Three Cards

こういうのしんどいよー。0が含まれる可能性はあるが、最上位桁は0でない。まず、桁数は可能な最大にする必要がある。並べ替えをどうするか。色々(532, 537, 53とか)考えられるので難しい。同じ桁数で考える場合、単に大きいものから使うのがいい。ということは、単に降順ソートして最初の3個を使うので確定だな?桁数が大きいのが優先されるし、選ばれた中で桁数が一番小さいものはその桁数の中で大きいものだ。あとはnext_permutationで全探索するだけ。to_stringで結合してstollで戻す(この辺の関数名未だにパッと出てこない)。

B - Plus and AND

すぐに二分探索を思いつくが、単調性はなさそう。上から決めていけばいい。logが2つ付きそうだと思って実行時間制限を見ると5秒なのでよさそう(?)。上から順にそのビットを立たせることができるかチェックする。やってることは二分探索。M回で実現可能ならそのビットを加えるというか今調べた数に更新する。調べ方は、それぞれ何回の操作が必要か計算してソートして小さい順にK個の和をとりMと比較する(ここなんかありそうだとは思ってたけど、nth_elementの使いどころだったか)。何回の操作でA_iをTにできるかは、上から調べてTで立っててA_iで立ってないビットがあればそこ以下のビット列を取り出して引き算(そのビットを立たせる必要があるので10000みたいのを必ず経由する)。そういうビットがなければ(当たり前だけど)0。提出してWAで、「なんでMが小さいんだろう」「あ、それに助けられてたのか」「いや助かってないじゃん」で30ビットではなく31ビット見るようにしてAC。一応、intで2^31-1までは扱えるので大丈夫そう(今見たら2^31を経由してたけどまあ正しく動作はしそう)。

C - Even XOR

難しいね。要素数が偶数かつxorが0の集合を数えるとしばらく勘違いしていた。まあ考えたことはそんな無駄にならない。数が大きすぎてきつい。一応条件なしに集合が何個あるか計算するコードは(思考が詰まったタイミングで)書いておく。奇数個選んで全体のxorをとる、その数があれば消すなければ加える、というのを思いついたが特に使えなかった。 偶数個でxorが0なのがダメで、部分集合にそういうのが1個でもあったらダメ。しかし空集合は含まないので対称性的にどうなのか(ほんとに計算できるの?)。