naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 029

12/15(土) 21:00-23:20

20:50まで某会場にいて(帰宅TLE確定)

今日は参加断念かな…と思いながらもiPhoneAtCoderにログインして問題を読みながら帰る
(提出しない限りレートに反映されないAtCoderルールはこういう時に助かる)
でもせっかくA,B,Cまで解法思いついたし実装しとくか

いまから投げてもレート下げるだけだからなあ…と思ったものの
欲しいのは実力、ということで
開始から2時間ほど*1経ってたけど3つまとめて思い切って投げる
→AC WA WA
おうふ

Bは実装ミスを1か所見つけたのを直して
→AC

CはTLE…
幅(オーバーフローの影響を考えて多めに見て64とか取ったけど)2進法のときでも最大18桁でn\le 2なn進数ではもっと狭くていいわけで、動的に幅を決めてもよさそう
最後までWAケースが1つ消えないまま終了

オーバーフローの影響というか、狭めた幅で計算したのを右シフトしなくちゃと思ってしていなかったのが原因だった(よくこんなテストケース準備してるなあさすが)
直して
→AC

2完パフォ1613でレーティング微減(1754→1740)

A - irreversible operation (300)

BW→WBと変わると、それが右端ならもう手を付けられないBが生まれる
てことは
右から貪欲にやっていけばいい?
最終的に全てのBが右端に来る?
ってことはだ
B=1 W=0とすると
BWBWBW=101010 で
これが 000111 になるまで操作する
バブルソート
転倒数を答えればいいだけでは
ライブラリ作っておいたよな確か
→AC
https://beta.atcoder.jp/contests/agc029/submissions/3801652

解説読む

はい

B - Powers of two (600)

最大マッチング問題?
グラフが複雑に絡んでたりとか、同じ数が沢山入ってたりとかすると厄介だし
そもそも最悪エッジの数が10^{10}本とかになりうるのでは
合計が2,4,8,16,...になるのを順に調べていく?
例えば1は1+1=2にも1+3=4にも1+7=8にも使えるし…絞れないな
逆はどうだ
2^{31},2^{30},...と順に見ていくとする
和が2^{31}になるペアは…少なくとも片方は(時には両方が)2^{30}以上なはずだ
2^{30}を超える数はこの機を逃すとペアが組めないので、

  • [2^{30}, 2^{31}) の範囲の数に対して合計が 2^{31} になる相手を探す

何がいくつずつあるか調べておけばこれは一瞬。(std::mapでもO(\log N)
2^{30}の時は特殊で、2^{30}同士でのペアリングなので\lfloor \frac{個数}{2}\rfloor組出来て、奇数個なら1つ残る。(残ってももう使えないのだが)
これを上から順に合計2=2^1まで見ていく
→WA
https://beta.atcoder.jp/contests/agc029/submissions/3801663
実装にミスがあった(調べている区間より小さい最初の数が飛ばされていた)ので直して
→AC
https://beta.atcoder.jp/contests/agc029/submissions/3802320

解説読む

はい(大きい順)

C Lexicographic constraints (700)

サンプルケースにはないけれど、同じ数が複数連続するケースを考えてみる
例えば

8
2 2 2 2 1 1 1 1

のようなケースをどう解く?

aa
ab
ba
bb
c
d
e
f

だと6種類だが

aa
ab
ac
ad
b
c
d
e

なら5種類で行ける。
下1桁をどこまで使っていいか決め打ちすれば良さそう。
これってn進法で数えてるのと同じだよね(a=0,b=1,...)
とするとn進法のnを探索して、それで表現しきれるかを調べればいいか
二分探索で行ける?
N=2\cdot 10^5とかだと、200000\lt 262144=2^{18}なので高々18桁にしかならない。a_i\gt 18の部分は無視できるかも?(繰り上がりでオーバーフローする可能性に注意)
通算で数えるとa_iが大きくなった時に死亡確定だよね…
個別に数えて、上を揃えて足し算するだけか
前よりa_iが大きいときは0から数えればいいけど
前よりa_iが小さいときは…1から数えないといけない
注意点はそのくらいかな
オーバーフローを防ぐには幅が2倍以上あればいいかな?
とりあえず64桁で
→TLE
https://beta.atcoder.jp/contests/agc029/submissions/3801705

桁数を減らして何度か試してみるけどWAが2つ残り、1つ消せて残りWA1つ、って辺りで時間切れ

繰り上がりオーバーフローを防ぐために右シフトすれば良いよね、と思ってたやつがちゃんと書けてなくて
直して
→AC
https://beta.atcoder.jp/contests/agc029/submissions/3805429

解説読む

固定桁数に寄せなくても出来そう(「ほとんどの文字が0であることを考えると、mapや配列を適切に用いることで比較的容易に管理することができます。」)
O(N\log N\log\max A)

D (800)

読んでない
700を飛ばしてこっちを通してる人も割といたし、こっちを見ても良かったかも?(帰宅ACしてたらそういう選択肢を取っていたかも)

*1:116:29