yukicoder contest 225

すごくいい問題っていうのとは違うけど、実装が適度に難しくて気持ちいい。本当に久しぶりの20位以内。

No.892 タピオカ

ΣAの偶奇。簡単な問題で使わない情報があるの好き。

No.893 お客様を誘導せよ

問題文を読むのに時間がかかって後回しにしたが、順番に取っていくだけ。vectorを使いreverseするとpop_back()で対応できる。計算量はO(N*max(P))。解いてるときは深く考えなかったが、Nもmax(P)も10^5(合計人数は10^5以下のまま)だったらどうするんだろ。空でないvectorのインデックスたちをループ毎に作り直せばいいか(遅いようでオーダーは変わらないやつ)。

No.894 二種類のバス

切り上げを足して引くだけだが、AとBの最小公倍数が64bit整数に収まらない場合があるのでその判定が必要。できれば整数でやりたかったが、色々考えてdoubleで計算して2*T以上かで判断した。雑に判定できればいいので浮動小数点数が楽。

(writer解を見て)なるほどなあ、片方のバスのうち何回同時だったかを数えればいいのか。

No.895 MESE

難しそうに見えて、考えていくとけっこうスルスルと解ける。ビットの被りがないのでわりと単純な状況。大小関係の条件は要するに最上位ビットの位置。xの最上位ビットはbit0と決まっているし、そこからyの最上位ビットまではxが占める。yの位置を全探索できそうだ。あとは残りのビットだがこれはどう配置しても条件を満たすのでコンビネーションを2回やるだけ(整数の組が何個あるかわかる)。zは残りのビットに均等にばらけるので、例えば5個中3個をzが占めるなら 整数の組の個数*11111b*(3/5) となる。

No.896 友達以上恋人未満

問題文読むのに10分以上かかった。3.5秒で2^24は微妙なところで、定数倍が軽ければlogが付いても大丈夫かも。長さMODの配列を持てば各レーティングのうなぎが何匹いるかわかる。問題は倍数であることだが、logが付いていいなら1の倍数から順に愚直で間に合う(結果をその場に上書きすることでMLE回避できる)。レーティング0に注意。あとはA,Bを生成しながら答えを出力してxorとっていくだけ。計算量はO(N+MOD*log(MOD))。解説見るとloglogにまで落とせるらしい。さすがに、俺がC++で定数倍にかなり気を使って2122msなので、自分の解法が想定解ならずいぶんギリギリだと思ってた。