Codeforces Round #568 (Div. 2)
宴じゃ。2時間半長すぎ
A. Ropewalkers
やるだけです。ソートして、最小値と最大値を中央値から離せばよいです
B. Email from Polycarp
問題：意味不明。2つの文字列が与えられるのでナニカを判定する。
考察：
どうにか読解したあとサンプルを見ると解法が生えます
連続する同じアルファベットを座圧します
前から見て不一致はダメ
余りはダメ
2つ目の文字列のほうがそれぞれの文字数が多くないとダメ
みたいな感じらしいのでそうします。
C1. Exam in BerSU (easy version)
問題：これも問題文がわかりづらかったです。
N個の処理クエリがある。1つでかかる時間はTi。もしi番目の処理までに時間がM経過していたら処理は失敗する。i番目の処理を成功させるために、前の要素を任意に取り除くことができる。取り除く必要がある最小個数をそれぞれで求めよ。
考察：
頑張ってようやくしたつもりなんですけど、めちゃめちゃわかりづらいですね。
C1は全探索でよいです。
手順は
t0からtiまで足す。m以下なら0を出力
そうでないなら、t0からti-1を降順に並べて、m以下になるまで引いていく。
これで間に合います。答えも出ます。
C2の解法を出してたら無限にバグりましたし嘘解法でした。ペナ4という地獄。
C2. Exam in BerSU (hard version)
C1の制約の大きい版です。
考察：
大きい方からｘ個取ってs-mより大きくしたいです。(sはt0からti-1まで足したもの)
セグメント木を使いましょう。
あらかじめtiを降順に並べたものと、iをmapで管理しておきます。
降順に並べた状態でセグメント木でSumを取ります
もしiまでに出ていなければ0です。
どこまでを除外するかで二分探索をすればO*1くらいでしょうか。4sec.なので余裕だと思います。
F. Two Pizzas
雑に読んだので誤読があるかもしれません
問題：ピザがM個あり、具材が入っている。具材には10種類1～10がある。ピザを2つ選んでパーティを開きたい。N人の参加者がいて、それぞれ好みの具材がある。任意の好みの具材が、2つのピザのどちらかに入っているとき、その参加者は満足する。
満足する参加者を最大化したい。もしその組が複数ある場合、コスト最小なものを1つ選べ。
考察：
2つのピザで網羅する具材の種類を考えます。
具材は最大10個なので2^10を全て考えればよいです。
ある具材セットを持たせるピザを1つ、2つでコスト最小化します
次に、ある具材セットについて参加者何人が満足するかを計算します。
計算量が結構厳しいですが、間に合わなくはないと思います
最後に全ての具材セットを見て終わりです
サンプル合いません終わりです。
※通したので追記
ほぼ考察は上で言った通りです。
実装として
１：ある具材セットで満足する人数の前計算
２：ピザの入力。ピザ1つでカバーできる具材セット：最小コストを計算
３：ピザ2つをマージ。ピザ＆具材セットみたくすると10＾8で計算できる。
4：ピザ2つの具材セットに対して、ある具材セットを満足させられるか。1の結果を足していく。10＾6程度。
3は、10＾6に落とせます。なんかバグったので無駄に丁寧にやりました。
3がボトルネックなんですけど、4secなので間に合います。なぜか451msで終わりました。
ひたすら地道に実装すればよい問題ですけど、なかなか時間がかかって辛いですね。実装力欲しいです。
感想
個人的には超逆転劇で楽しかったです。
12分でAB通した後、Cで6ペナ踏んでDへ。
Dで2ペナ踏んだ後Eへ。Eで1ペナ踏むも何とか通す(1:16)
ここから23分でC1C2Dを通しました。最終的に12ペナ6完って感じでした。後半はかなり良かったです(初めからやれ)
ペナルティがどのくらいかよくわからないんすけど、時間と体力はかなり削られて厳しかったですね。
正解人数見た感じ、F飛ばしてG1でもよかったのかなと思いました。
ここらへんの戦略は難しいところです。
時間作ってFとG1は通すようにしたいです。
ではでは
*1:logN)^2)で求めることができます
次にｘ以上の値を除外するとき、i番目まででx以上の値を持つ処理の数を数えなければなりません
もう1つ0，1(現れたかどうか)のセグメント木を持つことでO(logN)で解決できます
以上でO(N(logN)^2)で解くことができました。
嘘解法：
はじめやってしまった嘘解法を記しておきます
今までに処理したti-1までの値をmultisetで管理し、s>mになったら大きい順に除外しました
しかしこの解法は間違いです。
m=10
t：5 9 2
このケースを考えます。
正しい解は、0 1 1だとすぐにわかると思います
嘘解法では0 1 2となってしまいます。
コンテスト中に気づけて良かった。5ペナは無駄じゃない
D. Extra Element
問題：N個の整数列が与えられる。要素を1つ削除した後、自由に並び替えて等差数列にできるか判定せよ。もしできるなら削除する要素のindexを出力せよ
考察：
まず昇順に並べます。差を数字毎の個数で管理して、場合分けを頑張れば解けます
端を削除する場合：残りの差がn-2個全て等しければOK
真ん中のn-2個のどれかを削除する場合：
隣との差のカウント-1
右隣-左隣をカウント+1
この操作で、n-2個の差を見ればよいです。
差のベクトルと、カウントするmapなどで解けます。
はじめに、値とindexを記録しておくことの注意しましょう(ここで2ペナ)
E. Polycarp and Snakes
問題：N*Mのグリッドがある。a,b,c…という模様の縁に平行な線分を引く。あとから重ねたら上書きする。この結果のみが与えられ、構築可能か判定せよ。可能なら例を1つ出力せよ
考察：
MAPの読み込みですが、aが0からにしたいので空である'.'は-1などにしておきましょう
各文字が現れる座標をsetで管理します
このとき、どちらもsizeが2以上になったら構築不可能です
アルファベットｋについて、片方のset.size()が1でｘとして、もう片方の最小値がy0、最大値がy1とします
(x,y0),(x,y0+1),...,(x,y1)は、kか、それ以上の数で上書きされていなければなりません。
愚直に調べます。構築で使う答えは(x,y0)(x,y1)になります。
全体で出てきた一番大きいアルファベットまで調べればよいです
ここで注意すべきコーナーがあります。
例えばbはあるが、aがないなどのケースです。
これはaより大きい場所を適当に指定すればよいです。
上から順に調べて、1つ上の結果をコピーしました。読み込みのときに最大のアルファベットの点を1つ記憶しても良いと思います。
O(NM+26max(N,M
