AtCoder Beginner Contest 140
jsc2019で久しぶりにキョウプロしました
ABを早く解くことができて割と順位はよかったです。
でもC~は手も足も出ず精進不足を感じました。気が向いたときにやっていこうと思います。
今回はサボってた時期のコンテストを解きました。
A - Password
やるだけ。ひっかけかと思ったけど大丈夫でした
B - Buffet
各料理を1回ずつ食べることに気づけばやるだけです。これもひっかけじゃなくてよかったです
C - Maximal Value
逆に求めます。Ai=min(Bi-1,Bi)をやるだけです。端に気を付ければよいです
D - Face Produces Unhappiness
問題:N人が東西どちらかを向いて並んでいる。以下の操作をk回行い「前の人が自分と同じ方向を向いている」人を最大化せよ
操作:区間[l,r]の人の順番を入れ替え、向いている方向を逆転する。
考察:
LRLRLRと同じ方向を向いている人々をグループ化します
そうしたとき、複数グループを反転させる意味がないことがわかります。
したがって、どこかのグループを反転させることになります。
各グループ幸せでない人は1人です。またどのグループを反転させても幸せな人は2人増えます。
したがってn-(グループの数)+2*kが答えとなります
最大でもn-1人までなことに注意しましょう
E - Second Sum
問題:順列Pを考える。すべての長さ2以上の連続する部分列について、2番目に大きい数の和を取れ。
考察:
典型です。ある数字iについて、これが2番目に大きくなるような区間を考えます。
i<jなるjが下のように位置し、indexをa,b,x,c,dとします
j j i j j
a b x c d
こうすればO(1)でiによる寄与がわかります
multisetで上からindexを追加していけばO(NlogN)で解くことができます
F - Many Slimes
問題:スライムを集合Sに一致させよ
考察:上から貪欲でよいです。multisetでO(MlogM)で解けます(M=2^N)
E - Ball Coloring
700点問題解説AC
典型っぽさはあったんですが、うまく考察を詰め切れませんでした。
問題:n個のpairがそれぞれどちらかを青、他方を赤に塗る。青の範囲と赤の範囲の長さの積を最小化せよ
解説:
まず、小さいほうを片方に寄せることを考える。
そうでないとき、片方が大きく、もう片方が小さいという形になる。
もし中途半端なときどちらかを維持しつつもう片方を短くできる。
片方を大きくしたとき、もう片方を全部小さいほうにする。
この範囲をどう小さくするかを考える。
範囲の端点をpairの相手に変えるとき、特にこの場合は小さい側を大きいものに置き借る。そうすると、範囲が右側にずれて小さくなるか大きくなる。
これを繰り返して、範囲が最小の長さになるところが最適値である。
上のものと比べて小さいほうを出力する
感想:
範囲の最小化で、端点だけうまくいじるのは典型っぽく思えました。
どちらかに寄せておくのは自分でも考えつけたので良かったです。
だいたいの方針は当たったんですけど、最後の詰めが難しかったです。これは思いつきたかった感。
Codeforces Round #553 (Div. 2)
バチャ
A. Maxim and Biology
読解しづらくて9分でした。渋み
連続する4つなので全探索すればよいです
B. Dima and a Bad XOR
問題:行列の各行から1つ整数を選ぶ。XORを取って0にならないような選び方があるか調べよ
考察:
2種類の整数が含まれる行があるとき、必ず構築可能です。
なぜならその行以外から適当に選んだ時、どちらかは0より大きくなります
また、すべてで1種類しかないときは、適当に選んで0かどうか見ればよいです。
C. Problem for Nazar
問題:偶数と奇数がいい感じに並んでいる。l番目からr番目の和を求めよ
考察:
まず1からr番目の和から、1からl-1番目の和を引くことを考えます
1からx番目の和がうまく求まれば解くことができます。
まえから2^(k-1)個ずつ並んでいて、kが奇数のときは奇数の列、偶数のときは偶数の列で構成されています。
完全に含まれる群数列がどこまでか、偶数奇数どちらかがO(logx)でわかります。
以上からO(logN)で解くことができました。
D. Stas and the Queue at the Buffet
問題:n個のpairがある。これを適当な順で並べたとき、ai*(i-1)+bi*(n-i)のコストがかかる。コストの和を最小化せよ
考察:
b-aの小さい順に並べればよいです。
b=aのとき、n*aのコストがかかります。
差があるとき、aが小さいときは右側に、bが小さいときは左側にあるとうれしいのでこのようにすれば最適です。
もし上のように並べた後、どこを変えてもコストは増えます。
ai,bi,aj,bj(bi-ai<bj-aj , i<j)とします。
はじめのコストは
ai*(i-1)+bi*(n-i) + aj*(j-1)+bj*(n-j)
swapしたときのコストは
aj*(i-1)+bj*(n-i) + ai*(j-1)+bi*(n-j)
辺々引くと
(ai-aj)*(i-1) + (ai-aj)*(1-j) + (bi-bj)*(n-i) + (bi-bj)*(j-n)
= (aj-ai)*(j-i) + (bi-bj)*(j-i)
= *1*(j-i) <0
以上からコストが増えることがわかりました。
O(NlogN)で解くことができました。
E. Number of Components
問題:整数列Aから[l,r]の頂点だけ残す。連続する部分列いくつになるかをf(l,r)としたとき、l=1~n,r=l~nで和を取れ。
解説:
まず、連続する部分列の個数とは何かを考えます。
1つ前が選ばれていなくて、今見ているところが選ばれていると、求めるべき値が+1されます。
したがってすべての隣接要素で、+1になる場合の数を見ればよいです。
感想:
Eは典型っぽかったのですが、l、rから考えて詰まったしまいました。
Removing Blocksみたいに、どこをどうすると全体の値に影響するかに分割して考えるのは典型でした。
ある1つの要素をみたとき、その要素が連続部分列の先頭や最終になるときでした。
これは解けるようになりたいです。
*1:bi-ai) - (bj-aj
Codeforces Round #556 (Div. 2)
バチャした。紫なんですけど、Div2でしました。
A. Stock Arbitraging
問題:株を買ってから売って現金を最大化せよ
考察:
もっとも安いときに買って、高いときに売ればよいです。
なぜか最適かわからんくなって5分
B. Tiling Challenge
問題:十字のブロックを使って敷き詰めろ
考察:
上のブロックを基準に貪欲する。
結構実装が典型っぽくて5分でかけた、自己評価〇
C. Prefix Sum Primes
問題:1と2が与えられる。好きなように並べて、接頭辞の合計を並べる。素数の数を最大化せよ
考察:
素数は2以外奇数である。
なので、2を出した後3にして、そこから2ずつ増やすようにすればよい。
2の数と1の数が0のときは別で考えると、2,1,2222,1111とすればよい
D. Three Religions
問題:文字列sが与えられる。文字列1~3をクエリで更新する。この1~3がそれぞれ重複しないように文字列sの部分文字列にすることができるか判定せよ
考察:
DPをする。
dp[i][j][k]:1のi文字目、2のj文字目、3のk文字目が出るような、sの最前index
もし1にi文字目を追加するときは、i-1=>iの更新と、j、kについてすべて探索する。
したがってO(QM^2)である。
ここであるindex以降の最前のアルファベットが知りたい。
二分探索でもよいが、26*nの配列すべてで前計算したほうがはやい。
二分探索は意外と効く
AtCoder Beginner Contest 139
予定あって出れなかったやつやりました。
結果は70分5完で500位くらいでした。嘘解法だったのもあってちょっとつらみ
A - Tenki
やるだけ。初心者的に文字列操作結構しんどいイメージあります。
B - Power Socket
問題文がわけわからんやつでした。
サンプルエスパーすると(b-1+a-1-1)/(a-1)で解けます
C - Lower
問題:高さが以下だったら右に移動できる。好きなマスからはじめて最長の移動回数を求めよ
考察:
右側から見ます。単調非減少な部分列を求めればよいです。
D - ModSum
問題:ある順列について、順列のindex%整数の合計を最大化せよ
考察:
1つずらすことが最適です。
なぜかというと、整数iに対して%=i-1になるとうれしいです。
もともとの和が一定から動かないことから、商が増える分目的関数値が減るため、ギリギリが良いです。
したがって2 3 4…n 1という順列が最適です。
ここでー2n+1より負の効用を減らすことはできません。
なぜならn番目をなににしてもx-1より大きくならず、xがあった箇所ではx-1以下になるためです。
E - League
問題:n人の選手に対戦相手の順序が決まっている。1人の選手は1日に1試合しかできない場合、最短で全ての試合を完了する日数を求めよ
考察:
前から貪欲にやって、ケースが大きいときは最大の値を出したら通りました。ガバガバ。
トポロジカルソートをすればよさそうです。
ただし、1日にどこまでの試合がこなせるかを探しながら順序付けするのは難しそうです。
したがってボトムアップに決めていけばよいです。
dfsなどで実現可能です。
F - Engines
問題:ベクトルがn個ある。好きなものを選んだとき大きさを最大化せよ
考察:
最適に選んだ時、なす角はpai以下になるらしいです。
内積を考えるとわかりやすいです。
したがってあるベクトルから+paiまでを足すことをすべてでやればよいです。
角度でソートすればO(N^2)で解くことができます。
Codeforces Round #554 (Div. 2)
bqaya
A. Neko Finds Grapes
問題:n個の整数列Aとm個の整数列Bを1:1マッチングして、足して奇数になる組を最大化せよ
考察:
それぞれで奇数偶数の数を数えます。
奇数と偶数のマッチングしかないので、それぞれの小さいほうを足せばよいです。
B. Neko Performs Cat Furrier Transform
問題:ある整数xが与えられる。これを以下の操作をして2^m-1にせよ
操作:k>=0で2^k-1をXORする。+1する。
考察:
まずXORで下位bitがすべて変わることから、上から決めるほうがよさそうです。
既に1のbitは変える必要がないので、一番上にある0から下を変えましょう
下k桁がすべて0か、1が混じるかで場合分けします。
前者の場合は一番上の0の1つ下をkにして、後者の場合は一番上の0をkとすればよいです
C. Neko does Maths
問題:整数a,bが与えられる。a+k,b+kのLCMを最小化するkを求めよ。
考察:
a<bとします。a+kとb+kのgcdはb-aの約数にしかならないので、そのような最小のkを全探索し、各回でLCMを愚直に求めました。
WA on test 8
D. Neko and Aki's Prank
問題:長さ2nの()の対応が取れた文字列を作りたい。これを木の遷移で表すとする。色のついた辺同士が頂点を共通に持たないように、辺に色を塗る。色のついた辺を最大化せよ。
考察:
valueを(で+1、)で-1するものとします。対応が取れた文字列とは、すべての地点でvalueが0以上で、最後に0になるものです。
残りの試行で全てマイナスしなければ実現不可能
いまのvalueが0のとき
上では、マイナスするしかないです。下ではプラスするしかないです。それ以外ではどちらも可能です。
これをDPします。
このとき、1つ前の辺は1つしかないです。これが塗られているか塗られていないかで場合分けでき、状況は無差別です。
したがってDP配列を2つ持てば解くことができます。
遷移先が2つ
前が色あり:両方塗らない
前が色なし:片方だけ塗る
遷移先が2つ
前が色あり:塗らない
前が色なし:塗る
この貪欲で最適解が求まります。
なぜなら、もし2連続でわざと塗らない箇所を作ると、1つ減るかそのままです。
端点までの長さの偶奇で変わりますが、増えることはないです。
以上でO(N^2)で解くことができました。
Codeforces Round #558 (Div. 2)
ばたや
A. Eating Soup
問題:n人が円状にならんでいるとき、m人を退席させる。非連続にわかれる最大の個数を求めよ
考察:
n/2までは増えてそれからは減りそうです。
奇数のときでn/2付近が怪しいので実験して丁寧に解きましょう
B1. Cat Party (Easy Edition)
B2. Cat Party (Hard Edition)
問題:n個の整数列がある。k個目までで、1要素削除したとき、出現する数字のそれぞれの出現回数が等しくなるようにしたい。最大のkを求めよ
考察:
1要素削除して回数が一致する場合を考えます。
まず出現回数の種類は2種類以下の必要があります。
はじめに2種類のときです。多いほうの出現回数の出現回数が1回で、差が1のときOKです。また、1回の出現回数が1回のときもOKです。
わけわからないので具体例を出します。以下はそれぞれの整数の出現回数を列挙したものです
1-1:3,3,3,4
1-2:1.3,3,3
こんな感じです。
次に1種類のときです。
出現回数の出現回数が1回か、出現回数が1のときOKです
具体例です
2-1:4
2-2:1,1,1,1,1,1
出現回数のmapと、出現回数の出現回数のmapを持てばO(NlogN)で実行可能です。
実装にすごい苦労して1時間くらいかかっちゃいました。
下手すぎる
こういう愚直に場合分けするのはIQが試されてる感じがして苦手です。なぜならIQ低いので。
C1. Power Transmission (Easy Edition)
C2. Power Transmission (Hard Edition)
問題:n個の点がある。任意の頂点対を取り、2つを通る直線を引く。直線の交差する数を求めよ
考察:
直線の傾きと切片をすべて出します。
どちらも一致するものを削除します。
もし傾きが同じなら交わらないです。
傾きが違うもの*傾きが同じもの
これをすべての傾きで行えばよいです。
O(N^2logN)程度で実行可能です。
実装:
long doubleでやると破滅します。しました。
直線を表すとき、xの増加量:yの増加量で判別すればよいです。
それぞれをa,bとかおきます。式をガチャガチャすると切片cで表せます。
比を取る際にgcdで割ったり-1をかけたりします。
gcdの関数に0であるときの注意をしておきましょう。すべての点はdistinctなのですべて0になることはないです。
2点を通る直線を表す
ax-by=c
a=y1-y2
b=x1-x2
c=x2y1-x1y2
これを毎日3回、ロシアの方角に向かって唱えることにしました。
D. Mysterious Code
問題:文字列cの*を好きな文字に置き換えたとき、連続する部分列が、文字列sに一致する数-文字列tに一致する数の最大値を求めよ
解説:
KMP法を使うらしいです。
KMP法:
KMP配列を前計算し、文字列の中に出現するパターン文字列を求めるアルゴリズムです。
KMP配列とは、パタンのk文字目がパタンの接頭辞と一致するかの判別を示します。
あるk文字目が一致しないとき、また1文字目から確かめるとO(NM)になってしまいます。したがってどこまで戻ればいいかを記録します。
一致するなら1つ進み、一致しないなら一致するまで戻って1つ進みます。
もしk文字目がcのとき、どのような遷移をするかをすべて求めます。
与えられた文字列を見ながらその遷移を行ったとき、パタンの最後まで見れれば一致しているといえます。
これを*がどの文字になるかで遷移を計算します。
パタンsとtそれぞれの何文字目を見ているか、与えられた文字列分があり、遷移は前計算をすることでO(1)です
したがってO(|c||s||t|)で解くことができます。
なんとなーくKMP法についてわかったようなわかってないような。
コードを空で書いたり応用することは不可能な段階なので、しっかり復習したいと思います。