Educational Codeforces Round 71 (Rated for Div. 2)
参加しました～
A. There Are Two Types Of Burgers
やるだけです。
h,cの大小で場合分けしてもよいですし、全探索でも間に合います
B. Square Filling
問題：n*mの０１行列がある。任意の2*2の範囲をすべて1にする操作を好きなだけして、与えられた行列が実現できるか。
考察：
いろいろな解き方があると思います。
n*m回くらいは操作していいらしいので、左上のマスを全探索します。
このときn+1行目とm+1列目に余分に0をいれておくと実装が楽になったりします
4つとも1だったらそのマスに操作をして、すでに塗ったことにします。
最後にすべてのマスをもう一度みて塗ってないマスがあればー1、なければ操作手順を出力します
C. Gas Pipeline
問題：読解がかなり大変。図とサンプルから、1のところは高さ2、0のところは高さ1、間をナニカで繋ぎ、高くするやつがb円、つなぐやつがa円だとわかる。コスト最小化。最初と最後は高さ1にせよMUST。
考察：
全ての高さを2で初期化します。初期値はa*n+2*b*(n+1)です。
そこから低くして得するところのコストを引いていきます。
最初と最後だけ別で処理しておきます。このときすべて０ならここで終わります。
0が続くだけ、高さを1にすることが最適です。
次に間にある0ですが、0がk個続く箇所を高さ１にするとします。
そのとき削減するコストはb*(k-1)-2*aです。これが正のときのみ減らします。
以上を愚直にすればよいです。
D. Number Of Permutations
問題：pairがn個与えられる。(firstが昇順でない)かつ(secondが昇順でない)とき、その並びを良いとする。良い並びの総数を求めよ
考察：
NOTなので外してみます。
そうすると!*1となります。
昇順な並びは簡単に求まるので、ﾎｳｼﾞｮをうまく使って求まります
n! - (firstが昇順) - (secondが昇順) + (どちらも昇順)
これが答えです。
E. XOR Guessing
問題：インタラクティブである。ある整数が答えである。100個の整数を聞くと、その中のどれかとのXORを返す。クエリ2回することで、整数を当てろ。
ただし、200個の整数はdistinctな必要がある。
考察：
XORなので、あるbitを固定して100個の整数を渡せばそのbitがわかります。
2^14未満より、1回のクエリで7桁わからないとだめそうです。
残りの7桁で128通り表せるので、7桁固定できてこの問題が解けます。
F. Remainder Problem
問題：5*10^5の整数列があり初期値はすべて0である。Q個のクエリを処理せよ
クエリ１：ax+=y
クエリ２：i%x=yなるすべてのｉについてaiの合計値を出力せよ
考察：
まずクエリ2のみで考えます
xが小さいとき、結構大変そうです。
xが大きいときは、5*10^5/x回の操作で求まるので愚直にできそうです。
xが小さいときのみクエリ1をそれぞれのxで計算しておきます。
こうすることで計算量はO(Qsqrt(5*10^5))になり、ギリギリ間に合います。
ほんとにギリギリで3990/4000msでした。なんで遅いのかわからないんですが、入出力あたりかなと思いました。
結構ひらめきに頼ったところがあったので典型として覚えたいです。
sqrtに落とすのは典型っぽいので。
感想
Cにかなり時間かけちゃったなって印象でした。
DEもちょい遅いくらいなんですけど、これ以上早くするのは運が絡む気もします。
Fを通したかったです。考察が終わったというか、ひらめいたのが15分前だったので時間は厳しかったんですけど、+=yと=yを誤読して（実装段階で勘違いした)通せませんでした。
E通した後50分のうち35分考察にかけたのはよくなかったです。
典型として身につけていれば通せる問題でした。
レートは結構伸びるみたいで、感触がよくなかったにしてはラッキーって感じです。
紫になったらまたDiv1で0完すると思うと鬱ですけど。まあ頑張ります。
ｲﾝｼﾑﾘ
*1:firstが昇順)または(secondが昇順
