naoya_t@hatenablog

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

LoC June 2017

Lord of the Code (LoC) June 2017

CodeChefでやってた3日間のコンテスト。
ABCみたいな感じのやつなのかな。

やってると気づいたのが2日目の半ばで
問題ひと通り見たらさほど難しい問題でもないし、
standingsを見たら5問全完が30人ちょいいて
これ今から出して全完しても33位とかそのくらいだし、レート落ちるだけな気がして
解くだけ解いて提出しなくてもいいかなと思ったけど
なんかレートにこだわるのもつまらないかなと思って(というか、楽しさと経験値獲得を優先したいし)
解くだけ解いたコードを提出してしまえと思い提出。
(貼付コードのURLの通り提出順は難しい順だけど、解いたのは易しい順)

The Riddler (RIDDLE99; 1290, 24.57%)

b/m - ((a-1)/m) だよね
あれ?WA
b/m + ((a-1)/m) って書いてたorz
→直してAC
https://www.codechef.com/viewsolution/14392134

Harry and magical number (HHMGN; 978, 25.59%)

ソートしたAのどことどこの間にKが来るかは二分探索で
あとは割り切れるか
→AC
https://www.codechef.com/viewsolution/14392102

Kth Character (KCHAR; 487, 27.02%)

2進数で、ひっくり返しながら(補数を取りながらというか)折りたたんで行くだけ、みたいな。
10番目→8番目を中心に鏡像→6番目(反転1回目)
6番目→4番目を中心に鏡像→2番目(反転2回目)
2番目=立ってるビットが1つだけなので a
反転が2回なのでa→c→a、で答えはa。
10^{2017}桁全てを生成する必要はない。
→AC
https://www.codechef.com/viewsolution/14392096

Little Chef and Cake (PCAKE; 180, 11.76%)

素因数分解して、結果を累積して、
あとは、ある点からどこまで同じ素因数を2度使わずに伸ばせるか。
尺取り?いや尺取りで出来なくもないんだけど、
制約そこまで厳しくないから
始点全探索 x 終点2分探索でO(N\log N)
→AC
https://www.codechef.com/viewsolution/14392087

Roommate Trouble (PRATABHI; 37, 8.75%)

配列(クエリのたびに変わっていく)の bitwise OR、って
各ビットが初めて使われる位置だけ分かれば、Aに出現する数は全て分かる
kのビットをA
における出現順に見ていく
0→0 ないし 1→1 のときは(そのビットさえA[]のどこかで使われているなら)何もしなくていいんだけど、
0→1, 1→0 の場合、そのビットを
あるビットが立っていて、その次に出現するビットが立つまでにいくつ間があるか、によって

あ、同じ添字に値を再代入したときの処理を忘れてた
どのビットが過去にどこで出現したか分かれば、要らないやつだけ消せるし、次の場所もlog Nで分かるから更新が楽

→WA出した
https://www.codechef.com/viewsolution/14392078

実装ミス1点。
smallはnext_permutation(という名のbrute force)で通るはずだから取りあえず通るやつを書いて通して(自分の理解が間違っていないかの確認のため!)
テストケースを沢山作って、とりあえず通る版と同じ答えになるようにする過程で実装ミス箇所を発見&修正
→部分点20点(2箇所TLE);
https://www.codechef.com/viewsolution/14392286

「どのビットが過去にどこで出現したか分かれば、要らないやつだけ消せるし、次の場所もlog Nで分かるから更新が楽」の所をvector<int>じゃなくてset<int>に変更。その方が消す処理が早い。あと、更新時にかぶってるビットについては何もしない(1001→1010だったら一番左の1は放置できる)
→AC
https://www.codechef.com/viewsolution/14392910

5完(500点)で34位。