Codeforces Round #573 (Div. 2)

ちわ。おつっす。

コドフォに出ました。前回の初参加がunratedになったので実質初参加でした。自分用メモに。

codeforces.com

A - Tokitsukaze and Enhancement

問題：4の剰余で強さが決まる。与えられた整数に0～2を足して強くする。

解答：強さの上から％4=1,3,2,0でバラバラなのわかりづらすぎる。

B - Tokitsukaze and Mahjong

問題：麻雀の説明たくさん。ドンジャラ経験者なので勝ちました。3つ牌が与えられて、追加で自由に牌を選んで役を作るみたいな感じ。

解答：

・英語が全然読めずに苦労。まずは入力が何かを先に見たほうがよさそう

・たくさん場合分けを実装する

C - Tokitsukaze and Discard Items

問題：1からnの整数列からm個の指定の整数を削除する。k個表示されるページ内の指定の整数を1回の操作で削除できる。前から順に操作を行った場合、何回かかるか。ただし削除した後、整数列を前詰めする

解答：

・整数列が最大10^18なので単純ループは無理そう

・指定の整数リストPだけ見ればm個見ればよいため10^5程度

・指定の整数を含む1番前のページを考えて操作を行っていく

・ページめくりするといい感じに状態がリセットされそうだから、ページめくりをwhileの1セットとみた

Pの一番前のページがどこから始まるか計算
+k未満のものまで捨てる
捨てた分新しく詰めた整数を見る
捨てる整数がある限り、3を繰り返す
2と3で捨てた分ページの先頭のmod kがズレているため計算

・index outにならないように気を付けて実装

D - Tokitsukaze, CSL and Stone Game

問題：n個の山にそれぞれa[i]個の石がある。交互に1個ずつ石を取る2人ゲームを考える。ただし、ある2つの山が同じ石の個数になってはいけない。互いに最適行動をした場合、どちらが勝つか求めよ

解答：

・strictに大小関係のある2山では、石の個数は入れ替わらない

・なのでソートして考えるのがよさそう

・試してみると最終的に0,1,2,…個になることがわかる

・最終形までに行える操作を2で割って勝ち負けを決める

・ここで1手目が行えないケースがある(examplesにある)

同じ数字iが2つ並ぶとき、i-1があると負けを回避できない
同じ数字が3つ並ぶとダメ
0が2つ並ぶとダメ
「同じ数字が2つ並ぶ」が2つ以上あるとダメ

これを調べて終わり

・4を忘れててsystem test落ちました…

・typoしてpretestは通ったっぽい。なにこれは

E - Tokitsukaze and Duel

問題：デュエル！おれの勝ち！exactlyなk枚のカードを、全部同じ向きにする。交互にしたらどっちが勝つか。10^9回以上決着がつかなければ引き分けとする

解答：

・非常にシンプルな形を考える

111…1100000

(1が無限個、0がi個など)を考える

・iがk以下なら当然先手勝ち

・iがkより大きいとき、1手で終わらないようにできる

・例えば1の部分を1にすればよい

・結構引き分け多そう

・先手必勝を調べる

・先頭と最後尾に数字ｘがいくつ連続するかを調べればO(N)でわかる。

・後手必勝あるのか？と思ったらexampleにあった。優しい。好き。

・後手必勝：先手がn-k通りどこを0，1どちらに裏返しても必勝型になってしまう場合

・こちらもO(N)でわかる

F - Tokitsukaze and Strange Rectangle

まだやってない。やったら書くかも。覚えてれば。

やったので追記

問題：

二次元座標上にN個の点が与えられる。

任意の実数yB、xR、xLに対して、(y>=yB)&&(xL<=x<=xR)を満たす点(x,y)の組み合わせの個数を求めよ。ただし含まれる点の組み合わせが同じならyB,xR,xLが違ったとしても、1つと数える。

考察：

・y座標が上全部だから、y降順に見ていけば良さそう

・yB以上の点は、y座標が別でも区別する必要はなさそう

・方針：y降順でxの種類を見ていく

・あるyBに対して、y=yBである点を含む領域を足していく

・その点を1つも含まない場合、yB’＞yBで既に調べた領域である

・前の状態をもってコンビネーション？累積和っぽくして全探索？ここらへんでこんがらがって沼った

解説：

・左側*右側、segment treeで計算量削減

これくらいしか英文読解できなかった…

考察２：

・セグ木を使ってｘ座標の種類数を管理する

y座標を降順に見る

・ある点から見て左側にxLを置ける場合の数は、左側にある点の種類数。

・xRは同様に右側にある点の種類数

x座標を昇順に見る（ｓｅｔ管理なので）

・ある点ｑを調べるとき、左側にy=yBの点ｐを既に調べているとする

・そのときｐより左側にxLを指定する場合をダブルカウントしてしまう

・したがって直前に調べた点の右側で、いま調べている点の左側がxLを置ける場合の数

・以上のことを実装する

実装：

自分のとても読みづらいコードです。

Submission #57110724 - Codeforces

・segment treeを構造体で作っています。コピペポチー。今回はRMQ

・まず初めに座標圧縮をします。

・ｘ、ｙで出現した座標をsetでソートしつつ持つ。indexを振ってから点を指定し直すという方法を取りました。

・計算量悪いんですけど良い方法を知らなかったのでこうしました。N=2*10^5だしいいかなって思って。

・yに関しては座圧要らないと思います。xはセグ木のnodeが4*10^9くらいになると厳しそうかなと思って座圧しました

・点にindexふり直すときにyごとにxを整理します。

・メインループではyごとに見ます

・セグ木を全てのx座標で更新。もう一度x座標を昇順に見て、上の考察通りに計算します。試行錯誤のあとがコードに残ってますね。

・int befに前の点以前の点の数を記憶させて、って感じで処理してます

感想：

・整理してみるとかなりシンプルな実装ですね。

・以前のy、xと重複して領域を数えないためにどうするか。というのがうまく考察できなかったことが敗因です。

・左側と右側に分けて、どちらかを調べたか調べてないかで背反になるようにする。という考え方が自分ではしっくりきました

・両側で調べた調べてないを考えるとこんがらがります。セグ木を更新しながら計算して、右側は更新前の状態とかにしたんですけどうまくいきませんでした。

・セグ木に関しても慣れていないのですが、右側左側の計算の考察がうまくいったあとって感じですね。うーんなかなか難しいです。

感想：

英語はもう嫌なんやー

Ｂ，Ｃは考察軽めな分、かなり実装重く感じました。Ｂに20分、Ｃに40分かかってしまいました。反省。

Atcoderは途中で撤退するくらいの時間感覚なので、120分フルで取り組んだCodeforcesはかなり疲れました。

ただ実装力鍛えるにはもってこいっていう意見には納得。(Twitterで見かけた)

個人的にコンテストは精進より集中できて効率良いです。夜中だから無理しない程度に、でもできるだけ参加しようと思います

ばーい