解いた人数が少ないEをゴリ押せたので9位！この順位は嬉しー。
No.668 6.0*10^23
前問（やるだけなので略）に続いてprintfが便利。仮数が1.0になる範囲は95から104で自然だが、95が100になる様はちょっと奇妙だ。それは「小数第2位以下を四捨五入した値」と言えるのかという哲学的な何かをちょっと感じさせてくれる問題。生放送見てたら、先頭3文字に5を足すことで場合分けが要らなくなるらしい。995のときは50を足したい気がするけど、現実にはうまくいくのか、たまたまなのか、わからない。
No.669 対決!!! 飲み比べ
ニムじゃん。全く理解してないけどxorで行けるんだよね。と思ったらサンプルが通らない。Kが上限なのか。
Grundy数の計算方法と使い方 - pekempeyのブログ
Grundy数を（覚えたこともないけど）思い出すためこのページを開く。いや、まんまじゃん。すみません理解してないのにACだけ取りました。
No.670 log は定数
問題名を見て、O(QlogN)だけど定数が軽いものを選べという問題だと思った。しばらく考えると、何にlogがかかるのか色々ありそうだと思えてきた。まず、安直にstd::lower_boundを試すと22秒とかだった。定数倍高速化でどうとでもなりそうだ。yukicoderのジャッジは手元のPCよりちょっとだけ速い感じで、手元で4秒台のコードをもう少し高速化するゲームとなった。
他の人の実行時間を覗いてみたら1秒切ってるのがあって、xを読み込むだけのコードを動かしても1.8秒とかだったんで、何があるんだと思った。今にして思えば、そこでO(Q)のメモリを使わないという発想を出したかった。最初から解説を楽しみにしていて、「なんかすごい方法があるんだろうな〜」みたいな。コンテスト中から解説に頼ってる感じだった。ただ、それはそれとして「愚直+高速化」で現実のACを目指す。
まあlower_boundは速いので、それ以上となると基数ソートだよなあと。ただし、メモリ使用量を計算すると、xをインデックス付きで持つ時点で512MBギリギリになってしまう。基数ソートはその倍のメモリを使うのでアウト。ただ、時間的にはギリギリ間に合いそうな雰囲気もあり、なんとか基数ソートを使おうとした。2つに分ければオーダー変わらずメモリ使用量を半分にできる。
ここから自分で書いたradix_sortを取ってきたが、使い方がわからない（おい）。これは実用的な決め打ちで書き直すべきだ。書き直したコードよりも、書き直したという経験に価値がある。ソート対象でないインデックスが付いているので使い方を間違えた。2回目の提出はノックアウトされないギリギリのTLE。ループは2回なので展開してACを得た。
想定解はO(Q)だった模様。ワロス。
