ABC147

4完。楽しかったけど結果で死亡するやつ。

A - Blackjack

Yes/Noにしろってchokudaiさんに言われませんでしたか?内容自体はいい問題。

B - Palindrome-philia

全探索じゃないBもいいね(貪欲かな)。N/2(切り捨て)まで調べる。

C - HonestOrUnkind2

2^N通り調べるだけ。実装がそこそこ重いけどさすがにこのくらい慣れてますよと。が、ふと我にかえると条件がわからなくなる。不親切な人を調べなくていいのはわかる。じゃあ、正直者が「この人は不親切な人だ」と言ってる対象が嘘を言っていなかったら?矛盾はないけど正直者でない証明にはなっていない。じゃあどっちでもいいんじゃ?みたいな感じで最初正直者の不親切発言を無視していた。サンプルが合わずその条件を入れる。これで「正直者が嘘を言ってないか」はチェックされるので深く考えず提出(さすがに深く考えるのはコンテスト後でいい)。当然AC。実際は、どっちでもいいなんてことはない。最初に各人が正直か仮定してるので、それに反したらダメ。具体的には、不親切な人の発言はチェックしてないから嘘を言っていたらアウトだしそもそも正直者にカウントしてない。めちゃくちゃやんけ。全探索してるんだから、不親切として矛盾がなけりゃいいんだよ。

D - Xor Sum 4

A xor B = (A + B) - (A and B) * 2 みたいな性質があるので、まず全体の和を求める(各AがN-1回現れるっぽい)。そして各Aとのandだが、これはループを回しながらbit位置毎のそれまでの出現回数を持っといてA_iの立ってるビットと掛け算すればいい。入力を配列に保存せずできてよかった。

E - Balanced Path

AとBがあって塗り分けるというけど結局AとBの差だけが重要。各マスに1個の非負整数が書いてあって、経路上での合計が100で、いくつか選んで50にできるなら偏りは0、みたいな問題。経路がわかっていれば簡単だが、経路が多すぎるので無理。情報を保持するには値の範囲が狭くないとと思って制約に気づいた。全部80やんけ。全部80だから見えないんだよね。さて、この制約なら、そのマスに至るまでの合計としてありえるものを保持とかはできる。しかし、経路によって使える数が変わるので、合計から偏りはわからないし、現れた数を経路の数だけ保持するのは無理だし、経路関係なく現れた数だけ保持しても意味ないし。Fも少し読んでいたのだが、ここで完全に詰まって、以降ずっとFをやっていた(残り45分くらい?)。

(追記)合計じゃなくて偏りで普通にDPできたは。

F - Sum Difference

例えば数列が1,2,3,4,5なら簡単で、作れる最小値から最大値まで全部作れる(0から15まで16個)。制約から、選ぶ個数を0からNまでN+1通り試す方法を思いつき行けそうだと思う。XがDの倍数だったり全然関係ない数だったりが難しいが、これはもうGCDをとって割ってしまう。XとDが互いに素になった。-1を掛けることでXかDを非負に固定できる。どっちがいいのか最後まで揺れてた。Dが0のときは場合分けしてしまう。必要かどうかわからないけど、一応Xが0のときも場合分けしてしまう。さて、選ぶ個数を固定すれば答えは簡単。しかし、被りが生じるのでそこは引き算しないといけない。選ぶ個数をiとすると、Xの寄与はX*i。Dの寄与はDの倍数。互いに素なので、X*i%Dで分けることができる。Dで割ったあまりが異なれば被りは生じない。あまりが同じもの同士でmapを使い(使わない方法もある気がしたが短時間ではわからなかった)区間が被った分を引いていく。たぶん区間の変化は単調だろうから不連続な区間は左右の端だけ保持すればいいと思った。閉区間なことに気をつける。サンプルを試し答えが大きく出るので、区間の長さをDで割る必要があることに気づく。この時点で2分前。しかしサンプルが惜しいところで通らない。原因を考えていたら終わっていた。

(追記)ミスを直したら通った。それとは関係なく、各変数がどのくらい大きくなりうるか全然わかってなかった。