はじめに
10:50で全完、ペナなしで12位だったよ
成功したのでコンテスト中の流れや考察についておはなしするよ
コンテスト中の流れ
コンテストが始まって、最初にDをみたよ 問題文が読めるまで7秒ぐらいかかった気がする(回線さん…)
D問題
問題文が分かりやすくていいね 区間[A,B]の値を全てxorした値を求めよって問題だよ
まずは制約を読むと普通にやると通らなさそうな事がわかって、こういうのは各bit毎に決めていく(ここ典型ポイント)といいんじゃないかな？みたいに思ったよ
でも各bit毎に決める時の判定がむずかしそう＞＜(5秒ぐらい考えても分からなかったので、他の解法を考える事にしたよ)
問題文をもう一回読んで考えると、[A,B]の値は[0,A)と[0,B]の値のxorを取ればいい事がわかるよ(ABC007-D 禁止された数字 とか、桁DPでよくある考え方だと思う)
[0,B]は[0,A) xor [A,B]だから、こうすると[0,A)の部分が2回xorされて打ち消し合って、結果的に[A,B]だけ残るよ
で、ここまで考えるとf(x)=[0,x]の全てのxor を速く求められれば解ける事がわかるので、それをしたい でもわからないので実験をするよ(多分この辺で1分半ぐらい？)
愚直に600ぐらいまで全探索をして、"x: (ここに[0,x]の累積xorが入る)"みたいなのを600行出力したよ そうすると、明らかに4で余りを取った周期で何かが起きている事がわかるよ
具体的には、余りが0ならそのままxを返す、余りが1なら1を返す、余りが2ならx + 1を返す、余りが3なら0を返す をすればいい事がわかるよ なので実装をして、サンプルが会ったので投げると通った(ここまで5:41)
ちなみにこういうのは特に証明しないで投げてるよ 手元の実験で合っててサンプルが合ってれば通るみたいな気分だよ
提出した直後に順位表をチラ見すると400がまだ(ジャッジ待ちの僕を除いて)2人にしか解かれていない事が分かって、とても気分がよかった
C問題
問題文を読んで、適当に入力受け取り部分を書いたよ
値段が少ない順に買っていけばよいのはわかるんだけど、個数に制限がある → 値段と個数でpairを作ってそれを配列に入れて、それをソートして前から持っていけばよい みたいになったよ
Aiの制約がキツいので64bit整数を使う(intだとオーバーフローする)事に気をつけて実装、C++でpairの入ったvectorに要素を新しく挿入する時はemplace_backを使うとmake_pairとか書く必要がなくて便利だよ(setやqueueなど、他のデータ構造にもemplaceという関数があるよ)
これで通して終わり Dを提出してから2分20秒、考察+実装にかかったのがちょうど2分ぐらいだよ
B問題
問題文を読んで入力読み込みを書くことにするんだけど、すごい面倒な感じになってるよ
問題文はサラーっと読み流しつつ入力を読む、こういうのは最悪問題文を全部ちゃんと読まなくてもなんとなく書けばいいと思う…
「N個のソースコードのうち…個数を求めてください。」ってあるからN回ループを回して全探索をすればいい事がわかるよ(どうせABCのB問題なので、制約を読まなくても全探索でよさそうな事がわかる…)
あとはそのすぐ上の行にある式をそのまま実装、サンプルを合わせると通った Cを提出してから1:51秒 B問題にしては相当たいへんだと思う
A問題
とりあえず読むとよくあるやつな事がわかって、こういうのは答えもよくあるやつなので総和から引いて引いて重なった部分を足し直す(包除げんりみたいなかんじ？)といいと思うのでサンプルをを投げると合って、通ったよ これ普通に(H-h)*(W-w)で解けた事にコンテスト終わってから気がついたよ
おわり
ひさしぶりに成功して楽しかった。D問題で実験に走った割には速く解けて3位だったのは良かったんだけど、速い人は本当に速いんだなぁとおもった。
Dはf(b)-f(a-1)みたいに事に気づいて、あとは累積xorさえかければ実験ができて、この実験さえできれば天才じゃなくてもわかるので、実験しような！！！！
