Codeforces Round #559 (Div. 2)
バチャ
A. A pile of stones
問題：ある個数の石ｘから初めて与えられた操作をする。最小値が0以上のとき、最後に残る石の数を最小化するｘを求めよ
考察：
Aにしてはちょっと厄介でした。
全体での最小値を0とすることが最適なので、x=0とか適当にして、最後の値-最小値とすればよいです。
B. Expansion coefficient of the array
問題：k|i-j|<=min(ai,aj)を任意のi,jで満たすような最大のkを求めよ
考察：
任意のaiでk|i-j|<=aiとしてよいです。
またこの式で一番厳しいものは、j=0,n-1のどちらかなのでどちらも試します。
これをすべてのaiで求めて最小のkを出せばよいです。
minを外していい理由ですが、もしai>ajならajを調べるときに抑えられています。
C. The Party and Sweets
問題：ｎ人の男子とｍ人の女子がいて、男子が女子全員にお菓子を送る。
ｉ番目の男があげた菓子の数の最小値がai
ｊ番目の女が受け取った菓子の数の最大値がbjになった。
送られた菓子の和の最小値を求めよ
考察：
まずa,bをソートします。
そのとき、a[n-1]>b[0]のとき、実現不可能です。
a<=bのとき、ある女子に余分に菓子を送る男子がいることがわかります。
これはaiが大きい男子が余分に送ることが最適なので、a[n-1]から余分に見ます。
a[n-1]<b[0]のとき、m人に余分に上げると最小値a[n-1]が実現できません
なので、m-1人に余分に送り、もう1人にはa[n-2]さんが余分に送ります。
受け取りてのbさんはだれでも変わらないことは、式を書けば簡単にわかります。
以上のことを愚直に実装しますが、n=1やm=1のときに気を付けましょう
D. The minimal unique substring
問題：長さｎの01の文字列を構築せよ。ある文字列tを部分文字列として登場する回数が1になる。を満たすｔの最小の長さがkになるようにせよ。ただしn%2==k%2
考察：
ｎが奇数のときは01010をk+2個分繰り返した後0をつければよいです。
n=kのときはすべて0にすればよいです
ｎが偶数のときが構築できませんでした。
E. Permutation recovery
問題：ある順列ｐを復元せよ。ai：i番目より右側にあって、piより小さい値が出現する最小のindex。が与えられる。
考察：
iより大きくai未満のindexはpiより小さいです。またpaiはpiより大きいです。
この区間がズレて重なる場合実現不可能です。
そうでない場合は適切に辺を張ることでトポロジカルソートで求めることができます。
バグりました。
※通したので追記
後ろから決めないとバグります。setなどを使いましょう
辺を張るときにすべてに張るとN^2本の辺になり間に合わないので、隣接するものに張りました。このとき、少し離れている頂点対に張られておらず、前からでも後ろからでも同じ優先度になります。
しかし、繰り返すようですが後ろから前に辺があるので、後ろから決めなければいけませんでした。
Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2)
A XORinaccistandard
a,b,a^bの順になります
やるだけ
B Uniqueness
問題：整数列Aから連続する部分列を削除して、残ったものがdistinctになるようにせよ
削除する部分列の長さを最小にせよ
考察：
左からと右からを考えます。
左からL個残したとき、右側をどこまで残せるかはO(N)でわかります。
したがってO(N^2)で解けます
完全な典型なので、素早く解きたいところでした。12分なのでちょっと遅め
C Magic Grid
問題：0~n*n-1をn*nのグリッドに置く。各行各列のXORが等しくなるようにせよ。ただしnは4の倍数である
考察：
4の倍数なので4*4ずつ配置するとよさそうです。
順番においてうまくいきます。
全てに16足したとき16以上のｂｉｔは等しく、4個並ぶと0になるので必ずＸＯＲが等しくなります。
2*2セットでできるらしいです。
苦手なタイプの問題ですが、14分で解けたのは割とよかったと思います。
D Restore Permutation
問題：ｎ個の順列がある。左側にあって、aiより小さい値の和siが与えられる。復元せよ。
考察：
まず一番後ろが簡単に求まります
x(x-1)/2=s[n-1]を解けばよいです。
次にa[n-2]をｍと仮定したとき、整合性があるかはO(1)で求まります。
mより小さい値を足したとき、m(m-1)/2になればよいです。
もしmに関する項をまとめるとm(m-1)/2+xi+xi+1...となります。
これはmを大きくすると単調に非減少です。
したがって二分探索によってmが定まります。mより小さく既に出た値の和はSegmentTreeで求まります。
以上でO(Nlog^2N)で解くことができました。
E Let Them Slide
問題：ｗ列あり、各列ｎ行の和を取る。ある行は長さｌのベクトルでできており、端がはみ出さなければずらしてよい。値がない部分は0とする。各列で、和の最大値を求めよ
考察：
ｗ＝ｌならそのまま足す。
もしｌが十分小さければ、真ん中には行の最大値を足せばよいので、簡単に求まりそうです。
そうでないときは、尺取りや、SegmentTreeを使いO(WlogL)でそれぞれの列の最大値が求まります。
2番目の真ん中の部分を考えましょう。これはimos法で解くことができます。
[l,w-l)に最大値を足すので、1次元上をimos法で進めればO(W)で求まります。
以上からO(LlogL)で解くことができました。
反省：
基本的な考え方は80分くらいにはできていました。ちょっと遅いけど、Dで詰まった分を考えれば許容範囲かなと思います。
ただ1次元上のimos法が定着しておらず、イベント処理みたいな形式にしてバグっていました。
イベント処理形式って使うんですかね。座圧＋imosで十分そうに見えました。次からは抜けないように通したいです。
700点3問
C - Sequence Growing Easy
問題：すべて0の数列XのX(i+1)=Xi+1にする操作を好きなだけできる。数列Aiを実現する最小操作回数を求めよ
考察：
逆順に見ます。
操作：Ai+1==A(i+1)のとき、A(i+1)を好きな要素に変える。
全て0にしたい。
もしA(i+1)>=Ai+2のとき実現不可能です。
順にAi以前の要素を多くしたとしても、最後は0,2などとなり、0を増やすことはできないので不可能です。
よって増加する場合は+1の必要があります。
また、A0==0の必要があります。
Ai>=A(i+1)であるときを考えます。
このときAiをA(i+1)-1に置き換える必要があります。これが1以上のときは操作を2回必要とすることがわかります。なぜならA(i+1)-1にしたあと0にする操作が必要だからです。
このことを踏まえると、A(i+1)回操作が加わることになります。
以上を実装すればよいです。
E - Connected?
問題：x方向[0,r]、y方向[0,c]の範囲の長方形の周上含む内部に２ｎ個の点がある。2*iと2*i+1個目の点を曲線で結ぶ。長方形の外に曲線がでないように、またｎ本の曲線が交わらないように結ぶことはできるか。
考察：
まず、両方が周上にある場合だけを考えればよいです。
周上と隙間がある場合そこを通って結ぶことが可能です。
1周して順に何番目の頂点かを並べます。このときｘｙｘｙの並びになっていたら不可能です。
同じ組が隣接していれば必ず結ぶことができます。その後その頂点対は考えなくてよいです。
前から要素を追加していき、1つ前の要素と一致すればpopします。
最後に残った要素が2より大きい場合NOです。
vectorで簡単に実装可能です。
E - guruguru
問題：明るさは１，２、…m、１と循環で1ずつ変えられる。またお気に入りの値xに1回で変えられる。a1からanまで順に明るさを変えたいとき、操作回数を最小化するxを決め、操作回数を求めよ
考察：
まず後者の操作を無視して考えます。
この時各操作で
a[i] => a[i+1]
a[i] => a[i+1] + m
の2通りが考えられます。
x=a[i] + 2のとき2回かかる操作が1回になるので1回得します。
この要領で考えるとあるxベクトルを考え、a[i] => a[i+1]について
区間[a[i]+2,a[i+1]] に 1，2、…を足すというクエリを処理します。
このxの最大値分、操作を削減することができます。
このクエリ処理問題に帰着できました。
これはイベント処理のように解くことができます。
はじめにクエリを始点の昇順に並べておきます。
そして1~2mまで見ていくとき、いま所持するクエリの数と、いまある効用の大きさを持ちます。また、各クエリの(終点、長さ)を終点の昇順で持ちます。
以下のアルゴリズムを実行します。
1：始点と一致するようなクエリ分、所持数を増やす。
2：所持してるクエリの数、効用を増やす。
3：終点に達しているなら、効用から長さを引く
各ステップでx[i%m]に効用を足せばよいです。
以上でO*1で解くことができました。
実装かなりキツめでしたが、通せてうれしかったです。
*1:M+N)log(N
第一回日本最強プログラマー学生選手権-予選-
参加しました～
A - Takahashi Calendar
全探索で十分間に合うのでそうします。
B - Kleene Inversion
問題：N個の整数列ＡをK個並べた整数列の転倒数を求めよ
転倒数：あるaiより左側にあり、aiよりstrictに小さい。これを満たす整数組の数
考察：
ｉ番目の整数列Ａのｊ番目の要素をaijとします
このaijより左側にある要素は、Aがi-1個分と、Aの中で0~i-1番目までです。
両者のaiより大きい要素数は愚直にO(N)で求まります。
各iについて求めると、等差数列になるので和がO(1)で求まります。
全体でO(N^2)で解くことができました。
C - Cell Inversion
問題：黒白に塗られた２ｎ個のマスがある。ある２マスを選んでその区間（両端を含む）を黒白入れ替える。ｎ回の操作後にすべて白にする方法は何通りあるか
考察：
あるマスｉを考えます。
このマスの左側にはi-1マス、右側には2n-iマスあります。
左側で2つマスを選んだり、右側だけで2つマスを選んでもマスｉの色は変わりません。
また各サイドで偶奇も変化しません。ここに着目します。
片側が奇数、もう片方が偶数なことは、全体が２ｎ個なことから明らかです。
もしマスｉと奇数のほうをマッチさせると、両側が偶数になり、偶数回マスｉを含む操作がなされます。
したがって奇数のほうとマッチすると1回の反転、偶数のほうなら0回の反転と、同じ結果になることがわかりました。
初期値と、左右のマスの数の偶奇から、どちら側にマッチさせるかが求まります。
左側から順に決めていけば、簡単に総数が求まります。
右側と左側の数が不一致だったり、途中でマッチさせる相手がない場合は0通りです。
Submission #7113722 - Japanese Student Championship 2019 Qualification
D - Classified
問題：ｎ個の頂点にnC2本の辺を追加し、各辺にレベルを設定する。このレベルごとに、ある頂点からその頂点に戻るようなパスは必ず偶数長になるように、レベルを設定する。レベルの最大値を最小化せよ
考察：
木構造ならn-1レベルまでなりそうです。
これより小さい場合を考えます。
1-2-3-4…という直線状の構造なら木と同じです。
この場合さらに辺を増やすことができます。
1-4など2個飛ばしなら追加しても問題ありません。
全てで2個飛ばしに追加したとき、追加できる辺はありません。
次に辺が張られていない頂点集合が背反になります。
mod2の0,1なので当然です
1,3,5...
2,4,6...にわかれます。
帰納的に同じことができます。
各ステップで最適に辺を張っているので、nC2本になるまで繰り返せば最適です。
1ステップ目で2個ずつ、2ステップ目では2個ずつの2個ずつ＝4個ずつなので、2^kになります。うまいこと調整して求めればO(N^2)で解くことができました。
感想
156位で本戦出場権を得ることができました！たぶん！
Dがエスパーっぽかったんですけど、結果は結果なので喜んでおこうと思います。
Cは結構苦手な流れの考察でしたが、試行錯誤してどうにか通すことができてよかったです。ただケアレスで2ペナだったのは痛かったですが。
知り合いもおらずかなり不安なオンサイトなんですけど、せっかくのチャンスなので出ようと思います。たのしみ～
Codeforces Round #561 (Div. 2)
bあｙた
A. Silent Classroom
問題：n個の文字列が与えられ、2つのグループにわける。下で定義される値を最小化せよ。
うるささ：同じグループ内で同じ頭文字を持つペアの順序なしの数
考察：
まず全部を頭文字でわけます。
ある文字で始まる文字列がｋ個のとき、k/2ずつにわけることが最適なのでそうします。
算数得意じゃないと厳しそうですね。
k/2^2+k/2^2が最も小さくなるのって、算数の典型っぽいけどどこで身に着けたかあんまり覚えてないです。
B. All the Vowels Please
問題：整数ｋが与えられる。k=n*mを満たす任意の整数の組n,mで、n*mグリッドを作る。どの行、またはどの列にもすべての母音が現れるようにしたい。そのような長さkの文字列を構成せよ。
考察：
まず言いたいことがあります。問題文がわかりづらすぎる。マジで読解に時間かかりました。n,mも含めての構築ならかなり簡単です。この任意の整数組n,mというのが書いてなくて想像でやるしかなかったです。ほんとにひどい。
はい愚痴でした。
では考察していきます。
まずn,mが5以上になる整数組がない場合は構築不可能です。
例えば5と6で割り切れるとしましょう。
このとき文字列をaiueoの繰り返しにすると、n=5ではじかれます
1行ごとに1文字ずらしても、6のときはじかれます。
ではmod5で、存在しない数でずらすとしましょう（５，６なら2~4のどれかです）
次にmod5がすべて存在する例を考えます。
このとき構築不可能でしょうか？
結論から言うと適当にやっても構築できます。
最小でも2520くらいになります。
n<mとすると、ｎでは1周、mでは2周以上することが保証されます。
したがって雑な構築でも通ります。
実装結構重いですが、頑張ると通ります。
読解パートで２ペナでしたが、19分なのでよかったと思います。
C. A Tale of Two Lands
問題：ｎ個の整数が与えられる。この中の2つを選ぶ方法はnC2通りある。その各場合について下の条件が成り立つ個数を求めよ
条件：[|x|,|y|]を、[|x-y|,|x+y|]が完全に含む
考察：
ｘ、ｙが順不同！って書いてあるんですけど、これは算数しないと順不同でよいかわかりません。問題が悪すぎる。
はい愚痴でした。
順不同でも結果が変わらないことが暗に保証されています。
ではどのようなときに条件を満たすでしょうか。
ｘ、ｙが正、負、片方だけ正で片方が負、の3通りにわけたりいろいろします。
そうするとすべて絶対値を取ってよいことがわかります。
ここでx<yとして、2*x<=y のとき条件を満たします。
はじめにソートしておき、すべてのxの候補に対して二分探索でyの個数を求めていけばO(nlogn）で解くことができます
読解で苦労した割に17分だったので結構よかったと思います。
unorderedに惑わされなければ十分な速度だったと思います。
D. Cute Sequences
問題：n個の整数列を考えます。xi=x1+x2+...+xi-1+ri、1<=ri<=mです。あるクエリa,b,mについて、a=x1,b=xkかつk50以下の整数列を構築せよ
考察：
丁寧に整数列を計算してみます。そうすると以下のようになります
a
a+r1
2a+r1+r2
4a+2r1+r2+r3
これを一般化すると、だいたい
xk=2*xk-1+rk
のようになります。
kの個数で全探索をします。
2^k*aは固定なのでbから引きます。
またriは1以上なので、最低でも2^kは使います。最大で2^k*mです。
この範囲にb-2^k*aが収まるとき構築可能なので、riをiが大きいほうから貪欲に求めていきます（ｍ以下の最大の整数にしていく）
このとき、最後のほうでriを1にするとｂを超える場合があります。
これを防ぐためにあらかじめ2^k引いておいて、rのベクトルを1で初期化します。
各ステップでm-1以下になるように構築し、rベクトルに足せばよいです。
2^14*2^14でオーバーフローしてた；；；；
実質ACｗ
泣
E. The LCMs Must be Large
問題：n個の整数がある。この整数からsi個の整数を選ぶ操作をｍ回行う。各操作で、選んだ整数のlcm＞選ばなかった整数のlcmが成り立つことはできるか？
考察：
選んだ集合から、背反な2つの集合があるとき必ず不可能です。
このことからすべての集合から、整数のindexを経由して他の操作に行くパスを見つけるグラフ問題を考えます。
全ての操作において、他の操作が距離2以下ならOKです。
操作回数は高々50回らしいのでO(M*(N+M))くらいでも十分間に合います
考察重めで、実装もそこまで軽くないんですけど25分程度で通せました。
これが通せてなんとかって感じですね。通らなかったら3完だったので冷えてました。
Codeforces Round #562 (Div. 2)
バチャ
ボロボロすぎた
A. Circle Metro
やるだけ。
特別気を付けることもないかなって印象です。
サンプルみて問題もよくわかりました
B. Pairs
問題：pairがm個ある。ある整数2つを選び、すべてのpairのどちらかにどちらかが含まれるx、yはあるか。
考察：
かなり苦戦しました。
ひらめきがないと厳しいんですかね。あんまり理論的に詰めることができませんでした。
着目する点としては、x、yの片方がカバーするpairの数は、どちらかがm/2個以上になります。
なので、m/2回以上出現する整数をxとします。これは最大でも4種類しかないです。
xを含まないpairのすべてに含まれる整数を求めればO(m)で解が求まります。
2つ要素があったら片方固定は典型でしたが、試すまでに時間がかかったりとよくなかったです。このくらいの問題は長くとも15分程度で通せたらうれしいなー。精進します。
C. Increasing by Modulo
問題：ｎ個の整数列がある。任意の個数選んで( ai+1)%mする操作が行える。最小回数で非減少にせよ
解説：
これわからなかったです。解説で通しました
ある操作回数に対して、非減少列になるかがO(n)でわかります。
また操作回数は最大でm回なので二分探索で解くことができます。
二分探索の各ステップの説明です。
操作回数分足したとき、1周するかしないかで、以前の最大値と一致するならそうします。
しないとき、もし以前の最大値より小さければダメです。
大きければ以前の最大値を更新してそのあとを見ます。
操作回数に対して一意に決まることに気づけなかったところが敗因ですね。
要素を1つずつ見てもわからなそうだったら、最大でどのくらいかとか、また別の視点で見るべきですね
感想
Div1同時開催なので本番なら0完でした…
怖すぎます。というか実力なさすぎる。
DEも練習して通せるようにします。ただ解説読んだ感じかなり厳しそうでした。うーんつらいですね。
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が昇順
