Educational Codeforces Round 26
久しぶりにブログを書きます。
４完でした。D問題のDPを通せたのは個人的になかなか成長したのではないかと思える回でした。
A. Text Volume
問題概要
いくつかの単語で構成される文が与えられる。
各単語の音量はその単語に含まれる大文字の数で決まり、その文の音量はそれらの単語の音量の最大値で決まる。
与えられた文の音量を求めよ。
感想
これはそのままやるだけですね。強いて言うなら、最初大文字判定を'A' <= chみたいに書いててバグらせたのがアレでした。
asciiコードでは大文字が先に割り振られてるので'A' <= chだと小文字も全部カウントしちゃうんですね。
なので書くとしたらch <= 'Z'じゃないとダメでした。そもそも横着せずにちゃんと'A' <= ch && ch <= 'Z'と書いておけばよいですね。
D言語パワーを使ってスマートに書くとこんな感じ。
void main() {
readln;
readln.split.map!(w => w.count!(isUpper)).reduce!(max).writeln;
}
そもそもisUpperっていう大文字判定関数みたいなのがありました。
B. Flag of Berland
問題概要
R, G, Bのみで構成される旗が与えられる。
それがロシアとかイタリアみたいな国旗になっているか判定せよ。
感想
場合分けでゴリ押しました。結構めんどくさくて、めんどくさかったです。
丁寧に場合分けしないとコーナーケースとかで落とされて、割とHackで落とされた人が多かったみたいです。
長いだけなのでコードは省略します。
C. Two Seals
問題概要
a * bの土台となる長方形がある。n枚のシールを持ってて、シールiはx[i] * y[i]の長方形である。
この土台に２枚のシールを貼りたい。シールははみ出しちゃダメで、各辺は土台の辺と並行になるように貼らなければならず、２枚のシールが重なってもいけない。
このとき貼れる２枚のシールの面積の総和の最大値を求めよ。貼れる２枚が無いときは0とせよ。
制約
- 1 <= n, a, b <= 100
- 1 <= x[i], y[i] <= 100
感想
nが小さいので２つのシールの全ての組合せを試すO(n^2)解で十分間に合うのでそれをやりました。
１つのシールを左上隅に固定して貼ったとすると、２つの長方形を重ねたような多角形が残るので
そのどちらかの長方形に収まるようにもう一方のシールを貼れるか、みたいな判定をするみたいな。
int n, a, b; int[] x, y; void main() { scan(n, a, b); x = new int[](n); y = new int[](n); foreach (i ; 0 .. n) { scan(x[i], y[i]); } bool check(int U, int V, int u, int v) { return (u <= U && v <= V) || (u <= V && v <= U); } int ans; foreach (i ; 0 .. n) { foreach (j ; 0 .. n) { if (i == j) continue; if (x[i] <= a && y[i] <= b) { if (check(a - x[i], b, x[j], y[j]) || check(a, b - y[i], x[j], y[j])) { ans = max(ans, x[i]*y[i] + x[j]*y[j]); } } if (x[i] <= b && y[i] <= a) { if (check(a - y[i], b, x[j], y[j]) || check(a, b - x[i], x[j], y[j])) { ans = max(ans, x[i]*y[i] + x[j]*y[j]); } } } } writeln(ans); }
D. Round Subset
問題概要
n個の整数 a_1, ..., a_n が与えられる。
この中からk個選んで全ての積を取ったときの末尾の連続する0の個数を最大化したい。
その最大値を求めよ。
制約
- 1 <= k <= n <= 200
- 1 <= a_i <= 10^18
感想
まず、k個選んだときの末尾の0の個数がどうやって決まるかって話ですがこれは10で何回割れるかっていうことなので
各整数が2を何回含むか、5を何回含むかを前処理で求めておいて、選んだk個のそれらの値をそれぞれ足して、最後にminを取ることで求まります。
それで最大値問題ってことで最初は二分探索かなーとか思って考えてました。何か平均最大化問題みたいな感じで基準を定めてうんたらかんたらみたいな。
あれも「n個からk個とるとき」って感じだったのでそういうパターンかなって思ったのですがどうにも上手くいきそうにありませんでした。
それで次に考えたのがDPでした。「n個からk個とるとき」みたいな問題をDPで解いたことあったなあーとか思い出したので。
なんかちょっとぱっと出てこないんですがありますよね。dp[ここまで見た数][ここまでで選んだ数]みたいなDP問題。
ただこのまま
dp[ここまで見た数][ここまでで選んだ数] = (2の数, 5の数)
として、min(2の数, 5の数)が上回るとき更新、みたいにするとちょっとまずそうだなって思います。
例えば
3 2
4 10 25
みたいなケースで上手くいかなくなるはずです。
だからこのままではまずいけど、
dp[ここまで見た数][ここまで選んだ数][ここまでで取った5の数] = (2の数)
にして、2の数が大きくなるとき更新、にすると上手くいきそうっていうのは何となく分かるかなと思います。
別にこうじゃなくて
dp[ここまで見た数][ここまで選んだ数][ここまでで取った2の数] = (5の数)
としてもいいんですけど、状態数はなるべく少なくしたほうが計算量も少なくなるのでこれより上の奴のほうがいいと思います。
それで実際計算量は大丈夫なのでしょうか？
ここまで見た数 = 200,
選んだ数 = 200,
ここまで取った5の数 = 200 * 25
が最大ケースっぽいのでこれを掛け合わせると2 * 10^8くらいになるっぽいです。
Pythonだとまず間違いなくTLEしますが、Dの力を信じてサブミットするとあっさり300msぐらいで通っちゃいました。凄い速い。
実際DPテーブルを2 * 10^8作るとMLEしそうなので、１個目の変数は１個前しか参照しないから2個でいいっていう奴をやってます。
int n, k; long[] a; void main() { scan(n, k); a = readln.split.to!(long[]); auto two = new int[](n); auto five = new int[](n); foreach (i ; 0 .. n) { while (a[i] % 2 == 0) { a[i] /= 2; two[i]++; } while (a[i] % 5 == 0) { a[i] /= 5; five[i]++; } } int lim = n * 25; auto dp = new int[][][](2, k + 1, lim + 1); fillAll(dp, -1); dp[0][0][0] = 0; foreach (i ; 0 .. n) { foreach (j ; 0 .. k + 1) { foreach (f ; 0 .. lim + 1) { if (dp[i & 1][j][f] == -1) continue; dp[(i & 1) ^ 1][j][f] = max(dp[(i & 1) ^ 1][j][f], dp[i & 1][j][f]); if (j + 1 <= k) { dp[(i & 1) ^ 1][j + 1][f + five[i]] = max(dp[(i & 1) ^ 1][j + 1][f + five[i]], dp[i & 1][j][f] + two[i]); } } } } int ans; foreach (f ; 0 .. lim + 1) { ans = max(ans, min(f, dp[n & 1][k][f])); } writeln(ans); }
AOJ/Atcoder-JOI
何かここの難易度5 ~ 6ぐらいに良い感じのDP問題がたくさんあるのでオススメです。
これで少しDPに慣れていたおかげでこの問題が解けたかなと思ってます。
E. Vasya's Function
問題概要
f(a, 0) = 0
f(a, b) = f(a, b - gcd(a,b)) + 1 (b > 0)
という関数がある。f(x, y)の値を求めよ。
制約
- 1 <= x, y <= 10^12
感想
少し言い換えると「(a, b) -> (a, b - gcd(a, b))という操作がbが0になるまで何回出来るか？」という問題になることが分かります。
最悪実際にシミュレーションするって解がありますがx, yがめちゃくちゃでかくなるので明らかにTLEしそうでやりたくないですよね。
x = 1だったらy回シミュレーションしなきゃいけないわけだし……
それでaが素数のときはf(a, b) = a / b + a % bで～とか考えましたが結局全然分からなかったので答えを見ました。
操作で変化するのはbだけで、古いgcd(a, b)は新しいgcd(a, b)に必ず含まれているってのがポイントらしかったです。
まずaに含まれる互いに異なる素因数を列挙しておいて、
次にg = gcd(a, b)を求めて、このgcdが変化するときっていうのはaに含まれる素因数を新たに巻き込むときってことなので
そこまでにかかるステップ数を求めて、最後にそれらの最小値を取って、答えに加算して、また最初に戻って……
ってのを繰り返すみたいです。難しいですね。
計算量的には上の一回のループがaに含まれる異なる素因数分かかって、ループする回数はgcdが倍倍倍で増えていくからlogぐらいでみたいな感じであんまりかからなさそうです（雑計算）
結局最初にaの素因数分解にかかる時間が一番大きいような気がします。
import std.stdio, std.string, std.conv, std.algorithm; import std.range, std.array, std.math, std.typecons, std.container, core.bitop; import std.numeric; immutable long inf = 10L^^13; long x, y; void main() { scan(x, y); auto xf = factrize(x); debug { writeln("xf:", xf); } long ans; while (y > 0) { long g = gcd(x, y); if (g == x) { ans += y / g; break; } long m = inf; foreach (p ; xf) { long mp = (y - (y / (p * g)) * p * g) / g; if (0 < mp && mp < m) { m = mp; } } ans += m; y = y - m * g; } writeln(ans); } auto factrize(long x) { auto res = new long[](0); for (long p = 2; p*p <= x; p++) { if (x % p == 0) { res ~= p; while (x % p == 0) { x /= p; } } } if (x > 1) { res ~= x; } return res; }
Educational Codeforces Round 23
参加しました、３完でした。Cはもうちょっと早く解けたかったな、という感想ですがなかなか難しいものです。
Dは結構考えたんですが全然分からず、解説見て勉強になりました。典型問題らしいです。
A.o
B.o
C.xo
そういえば今回はpythonじゃなくて個人的に流行のD言語で参加しました。なので掲載コードもD言語です。
ブログタイトル詐欺みたいになってますが、そんなに見てる人いないだろうしいいかな。
pythonのコード期待してる人がもしいたら申し訳ないですが。
A. Treasure Hunt
問題概要
あなたは２次元座標上で(x1, y1)にいる、(x2, y2)に行きたい。
移動手段は謎のポーションで、それを使うと現在位置から相対位置で(x, y), (-x, y), (x, -y), (-x, -y)ずれたところのいずれかの場所に行ける。
このポーションは無限に使えると仮定してよい。(x1, y1)から(x2, y2)に行けるか判定せよ。
感想
現在位置は(0, 0)と仮定しても一般性を失わないので、(0, 0)から(a, b)に行けるか判定する問題だと思うことにします。
とりあえず、aがxの倍数とか、bがyの倍数じゃないと行けなさそうだなっていうのは分かります。実際そうでないときは行けません。
問題はこの条件が必要十分条件であるか、つまり「aがxの倍数かつbがy倍数ならば行ける、そうでないなら行けない」と言えるかということですが、自信が無いですよね。
実際この問題の例２がそれを否定してくれる例になっています。aがxの倍数でbがyの倍数なのにNOらしいです。
こういうのは考えてても仕方ないのでグラフに書いてみるといいと思います。原点から幅優先探索的にポツポツと行ける点を描いてみると何となく法則が見えてきたり来なかったりします。
ちょっと図を作るのがめんどくさいので省略しますが、適当に作ってみると行ける点が互い違い、というか何か周期２でズレてたりするのが分かるかと思います。
周期２が何となく見えるので偶奇が必要になりそう、という発想ができたら、x/aとy/bの偶奇が一致してないと行けなさそうだということも分かって、これが必要十分条件になることが何となく分かります。
なんで？ってことですが、a/xしてb/yするってことは１つのステップで行けるところが(+1, +1), (+1, -1), (-1, +1), (-1, -1)であると考えることに等しくなって、この移動方法は偶奇を保存しながら進むからです。
って後付で説明するのは簡単（それでもちょっと難しい気がする）ですが、最初のサブミットに17分かかってるのでAの割に難しかったです。
というわけでコードです
import std.stdio, std.string, std.conv, std.algorithm; import std.range, std.array, std.container, std.math, std.typecons; int x1, y1, x2, y2; int x, y; void main() { scan(x1, y1, x2, y2); scan(x, y); if (abs(x1 - x2) % x || abs(y1 - y2) % y) { writeln("NO"); return; } int xd = abs(x1 - x2) / x; int yd = abs(y1 - y2) / y; if ((xd - yd) & 1) { writeln("NO"); } else { writeln("YES"); } } void scan(T...)(ref T args) { auto line = readln.split; foreach (ref arg; args) { arg = line.front.to!(typeof(arg)); line.popFront; } assert(line.empty); }
pythonに慣れているとかっこがいっぱいあるのが若干気になりますが、慣れてくると気にならなくなると思ってます。
ここで定義してるscanってのが結構便利で可変長引数で変数が受け取れて、それらの型に合わせていい感じに標準入力から値を読み込んで保存してくれる奴です。他の人が使ってたのを丸パクリしました。
テンプレートってやつらしいですが、正直あんまり良く分かってません。けど便利です。
他のC++のコードとか見るとマクロだらけだったりしますが、D言語はそんなにマクロとか使わなくてもいいので結構スッキリ書けて良い感じです。
B. Makes And The Product
問題概要
要素数nの配列aが与えられる。a[i]*a[j]*a[k]が最小値となるような３つ組(i, j, k)(i < j < k)が何通りあるかを求めよ。
制約
- 3 <= n <= 10^5
- 1 <= a[i] <= 10^9
感想
愚直に全ての３つ組(i, j, k)について試して数え上げようとするとこれはO(n^3)になってしまい明らかに間に合いそうにありません。
でも３つの積a[i]*a[j]*a[k]が最小値になるときってどんなとき？と考えると、a[i] > 0ですから明らかに小さい順に3つ取ってきてそれを掛け合わせたときだな、と分かるとそんなに難しくはなさそうです。計算量に余裕があるのでとりあえずソートしておきます。
ただ、単純に、例えばa[0] < a[1] < a[2] < a[3] < ... みたいになってれば明らかに1通りしかありませんが、a[0] = a[1] = a[2] = a[3] = ... < a[j] < ...みたいになってたりするとちょっとめんどくさそうです。
ここは最小値が何個あるかで場合分けしてしまうのがよさそうです、そんなに数も多くないですから。
ここでaに含まれるa[2]の数をxと置いておきます。理由は見ていけば分かります。
最小値が1個だけのとき
つまりa[0] < a[1] ...のときですがこれは次に小さい要素に依存します。
a[1] < a[2]なら、最後に入るのはa[2]と同じ値であれば組合せとしては何でもよいので答えはxになります。
a[1] = a[2]なら、最後の２つの選び方が何個あるか、ということになり、これは組合せとしてxC2、つまりx * (x - 1) / 2個あります。
最小値が2個だけのとき
このときは、a[0] = a[1] < a[2]となっています、これは最後に入るのがa[2]と同じ値のものであればよいというさっきと同じ論法でx通りになります。
最小値が3個以上あるとき
このとき、a[0] = a[1] = a[2] ...となっています。これは最初の３つの値と同じ値であればどの３つの組合せでもよいので、xC3、つまりx * (x - 1) * (x - 2) / 6通りになります。
というわけで、入力された配列を最初にソートしておいて、次にa[2]の数を数えて、最後は上の場合分けに沿って答えを求めればよい、ということになります。
「最小値を取るのは小さいほうから３つ取ったとき」ということはほぼ明らかですから、後は考えられる全ての場合を考えて答えを求めればよいという感じなので、個人的にはAより簡単かなと思いました。
ソースコードはこんな感じです。
import std.stdio, std.string, std.conv, std.algorithm; import std.range, std.array, std.container, std.math, std.typecons; int n; int[] a; void main() { scan(n); a = readln.split.to!(int[]); a.sort(); long ans, x; x = a.count(a[2]); if (a[0] < a[1]) { if (a[1] < a[2]) { ans = x; } else { ans = x * (x - 1) / 2; } } else if (a[1] < a[2]) { ans = x; } else { ans = x * (x - 1) * (x - 2) / 6; } writeln(ans); } void scan(T...)(ref T args) { auto line = readln.split; foreach (ref arg; args) { arg = line.front.to!(typeof(arg)); line.popFront; } assert(line.empty); }
int型ではオーバーフローする可能性があるのでlong型を使わなければいけないことに注意しないといけませんね。
python使ってたら多倍長整数なのでオーバーフローとかほぼ何も考えずにやってたので、その辺は少し慣れないと大変そうです。今はよくオーバーフローさせてバグを生みだして辛い思いをしています。
ちなみにこの問題はソートしなくても小さい方から３つの値だけ分かればよいので、O(N)で解くこともできるんですがちょっとめんどくさいですね。計算量的にO(NlogN)でも余裕なのでO(N)で解こうとしなくてもいいんですが。
そういえばAtcoderで似たような問題を解いたことがありました。ABC057-Dですね。
D: Maximum Average Sets - AtCoder Beginner Contest 057 | AtCoder
C. Really Big Numbers
問題概要
正整数xがx - (xを十進数で表したときの桁和) >= sであるとき、xをほんとに大きい数と呼ぶことにする。正整数n, sが与えられるので、n以下の正整数にほんとに大きい数がいくつあるか答えよ。
制約
- 1 <= n, s <= 10^18
感想
まず制約を見て総当たりで数え上げはとても無理だということは分かります。
実は最近桁DPというものを覚えたので、それを応用できないかと最初に考えました。18桁の桁和って高々18 * 9程度にしかならないので何かそれを状態に持たせるといいんじゃないか、みたいな。
dp[今まで見た桁数][n未満フラグ][ここまでの桁和]で数え上げるみたいな。でも最終的に桁和がmの整数が～個ありました、みたいな情報だけ分かってもどうしようもないんですよね。元の整数が何だったか分からないと判定できないので。だからこれはダメそうでした。
それで、まあ仕方ないのでとりあえず規則性見つけてみるかと思って、1～30ぐらいで考えると、10増えると(それ - それの桁）が9増えるんですよね。だから(s + 8) / 9 * 10以上の整数は全部オッケーかあ、みたいに考えて適当に出したら不正解でした。
「あれ？」って思ってバグかなあと思ってたんですが、localで適当にpythonで愚直コード書いて見てみると、9増えるのは下1ケタが繰り上がったときだけで、99 -> 100みたいなときは+18でした。さらに999 -> 1000のときは+27だったり。
ここで結構うわーってなってこれを数学的にどう処理したらいいんだ……みたいなこと考えて思考停止して停滞モードになりました。
でも別に数学的に解を求める必要は無いんですよね、これ数学コンテストじゃないから。
（それー桁和）の結果をよく観察してみると、これは単調増加関数になってます。ということは、二分探索が使えるじゃん！って気づくとなんだーって感じで二分探索書いて通しました（ほんとはそっからさらにバグらせてアレな感じでしたけど……）
このとき結構焦ってたので単調性を示せなかったのですが、落ち着いて考えるとそれ自体が+1されたとき、桁上りが無かったら桁和も+1で変化無し、桁上りがあると例えば09->10なら桁和は-8されて、099->100なら桁和が-17されて、となってるので（それー桁和）は桁上りした回数*9増えるので単調増加関数であることが分かりますね。
というわけで無事二分探索で正しく解が求まることが分かりました。
import std.stdio, std.string, std.conv, std.algorithm; import std.range, std.array, std.container, std.math, std.typecons; long n, s; void main() { scan(n, s); if (calcdif(n) < s) { writeln(0); return; } long top, btm, mid; top = n; btm = 0; while (top - btm > 1) { mid = btm + (top - btm) / 2; if (calcdif(mid) >= s) { top = mid; } else { btm = mid; } } long ans = n - top + 1; writeln(ans); } long calcdif(long x) { return x - digitsum(x); } unittest { assert(calcdif(0) == 0); assert(calcdif(1) == 0); assert(calcdif(9) == 0); assert(calcdif(10) == 9); assert(calcdif(13) == 9); assert(calcdif(34) == 27); assert(calcdif(99) == 81); assert(calcdif(100) == 99); assert(calcdif(315) == 306); assert(calcdif(1000) == 999); } long digitsum(long x) { return x > 0 ? digitsum(x / 10) + x % 10 : 0; } unittest { assert(digitsum(123) == 6); assert(digitsum(0) == 0); assert(digitsum(1) == 1); assert(digitsum(100) == 1); assert(digitsum(375826) == 31); assert(digitsum(98) == 17); } void scan(T...)(ref T args) { auto line = readln.split; foreach (ref arg; args) { arg = line.front.to!(typeof(arg)); line.popFront; } assert(line.empty); }
D言語はunittestっていうのが書けて、コンパイルするときに
dmd -unittest main.d
みたいにオプションをつけると実行時にunittestでassertチェックしてくれます。
関数作ってそれがバグってるとどの処理でバグったか分からなくなり面倒なことになるので、関数を作ったらunittestを書く、ってのは結構いいと思います。ただtest作るのも面倒なのでどこまでちゃんとやるかはトレードオフですが……
もちろん向こうの環境で実行されるときはオプション無しでコンパイルされるので書いたunittestは消さなくても大丈夫です（ブログとかに乗せるときは消したほうが見やすいと思いますが、ここではD言語の紹介も兼ねて）
あ、そういえば二分探索の書き方もオーバーフローが起こらないような書き方に直してますね。python感覚で普通に
mid = (top + btm) / 2
って書いちゃうとtop側にどんどん収束していくような場合、topの初期値が大きすぎるとオーバーフローすることがあるみたいですね。
なので
mid = btm + (top - btm) / 2
って書いたほうがオーバーフローが確実に起こらずに良い書き方みたいです。
D. Imbalanced Array
問題概要
要素数nの配列aが与えられる。配列内の区間[a[l], a[l+1], ..., a[r]]に対して、（その区間内の最大値 - その区間内の最小値）をその区間のimbalance valueと呼ぶことにする。
aの全ての区間のimbalance valueの総和を求めよ。
制約
- 1 <= n <= 10^6
- 1 <= a[i] <= 10^6
感想
愚直に全ての区間のimbalance valueを求めて足しあげようとすると最低でもO(n^2)はかかります、これではTLEしてしまいます。
こういうのを考えるときの定跡（？）として、区間に着目するのではなく点に着目する、つまり各要素が何回足し引きされるのか、を考えて上手い事処理するとO(n)とかO(nlogn)で解けそうです。
区間に着目するのではなく点に着目して計算量を落とすという考え方の類題としては例えばこんなのとか、区間じゃなくて部分集合になってますが点に着目するというのは一緒です
http://codeforces.com/contest/810/problem/C
じゃあ各要素が何回足し引きされるのか考えてみます。
例えば足される回数は何回ぐらいでしょうか？
imbalance valueの定義からして、その要素を含む区間でかつその要素が最大値となる区間の個数であることは分かります。
例えば a = [3, 1, 4, 1, 5, 9, 2, 6, 5] だったとして、a[2] = 4が最大値となる区間は何個あるか数えてみると
[4], [1, 4], [4, 1], [1, 4, 1], [3, 1, 4], [3, 1, 4, 1]
で6通りあるので、a[2]は6回足されることが分かりました。
この個数をなるべく速く求めることが目的です。
もうちょっと考えるとその要素を含む区間の個数は（左端の選び方）×（右端の選び方）で求められることが分かります。
a[2] = 4だったら、左端は0, 1, 2の3通りあり、右端は2, 3の2通りあるので3 * 2 = 6通りで、確かに一致しています。
この（左端の選び方）は要素iから左に動かしていってa[i]が最大値であり続けられる境界が分かれば後は引き算で求められることが分かります。右端ならその逆です。
実際はa[i]と同じ要素が出てきたときどうすればいいか考えなきゃいけませんがimbalance valueを考えるときに「複数個あるときは最も左端の最大値を取る」と暗に定義しておけば、左端に伸ばしていくときはa[i]と等しい要素が出てきた時点でアウト、右端に伸ばしていくときはa[i]と等しい要素が出てきてもまだ伸ばせる、と考えればいいことが分かります。
……とまあ、このあたりまではコンテスト中に考察できたのですが問題はその境界をどうやって速く求めるか？っていう話ですよね。ほんとに愚直に伸ばしていったらO(n^2)かかってしまうので意味がありません。
それで何か累積maxとか取って二分探索すればO(nlogn)でいける？みたいに考えてたんですが、普通に間違っており、どうしようもありませんでした。
考察的にはかなりいいとこまで行ってるのでオーバーしてもちょっと考えたりしたんですが、何かセグ木とか使うのかなあ……とか考えていい感じの答えが分からなかったので解説を見ました。
するとどうやらセグ木とかは全然使う必要が無く、スタックを使うだけでいけるらしいです。
各要素iについてそっから左に伸ばしていって初めてa[i]が最大値で無くなるところを格納する配列をleftmax[i]とします。アルゴリズムは以下のような感じです。スタックは添え字を詰めていくために使うものです。
- i = 0, 1, 2, ..., n - 1と左端から順に見ていく
- i = 0のとき、空のスタックに0をプッシュして、leftmin[0] = -1とする
- i > 0のとき、以下の一連の手順を繰り返す
- スタックが空でないとき、そのスタックの一番上に入ってる添え字をjとしてa[j]とa[i]を比較する、もしa[j] <= a[i]ならばスタックからjをポップしてa[j] > a[i]となるかスタックが空になるまで繰り返す
- 上の操作が終わった後、スタックの状態を見て空ならleftmin[i] = -1とし、そうでないなら、スタックの一番上に入ってる添え字jを対応付ける, leftmin[i] = j
- 最後にスタックにiをプッシュして、次の要素に移る
とこういう感じになってます。このアルゴリズムで簡単にleftminが求まってしまいます。計算量は各添え字は1回プッシュされ、高々1回ポップされる程度なので、n回ループでO(n)、スタックの操作でもO(n)なので全体でO(n)の計算量となっています。
右端がどこまで伸ばせるかを知りたいなら配列を逆順に読んでいくものに書き換えるだけです（ただしポップする条件の不等号が微妙に変わってa[j] >= a[i]になることに注意してください、これはimbalance valueの定義をするときに「複数の最大値がある場合は最も左端のものを取る」としたからです）
頭の中で考えただけではちょっとこれでなんで求まるのか分かりづらいですが、小さ目のケースを作って試してみると何をやっているのか分かると思います。
import std.stdio, std.string, std.conv, std.algorithm; import std.range, std.array, std.container, std.math, std.typecons; int n; int[] a; void main() { scan(n); a = readln.split.to!(int[]); int[] leftmin = new int[](n); auto st = Stack!int(n + 10); foreach (i ; 0 .. n) { while (!st.empty && a[st.top] > a[i]) st.pop; leftmin[i] = (st.empty ? -1 : st.top); st.push(i); } st.clear; int[] rightmin = new int[](n); foreach_reverse (i ; 0 .. n) { while (!st.empty && a[st.top] >= a[i]) st.pop; rightmin[i] = (st.empty ? n : st.top); st.push(i); } st.clear; int[] leftmax = new int[](n); foreach (i ; 0 .. n) { while (!st.empty && a[st.top] < a[i]) st.pop; leftmax[i] = (st.empty ? -1 : st.top); st.push(i); } st.clear; int[] rightmax = new int[](n); foreach_reverse (i ; 0 .. n) { while (!st.empty && a[st.top] <= a[i]) st.pop; rightmax[i] = (st.empty ? n : st.top); st.push(i); } long ans; foreach (i ; 0 .. n) { ans += 1L * (i - leftmax[i]) * (rightmax[i] - i) * a[i]; ans -= 1L * (i - leftmin[i]) * (rightmin[i] - i) * a[i]; } writeln(ans); } void scan(T...)(ref T args) { auto line = readln.split; foreach (ref arg; args) { arg = line.front.to!(typeof(arg)); line.popFront; } assert(line.empty); } struct Stack(T) { private: int N, peek; T[] data; public: this(int size) { N = size; data = new T[](N); } bool empty() @property { return peek == 0; } bool full() @property { return peek == N; } void push(T x) @property { assert(!full); data[peek++] = x; } void pop() @property { assert(!empty); --peek; } T top() @property { return data[peek - 1]; } void clear() @property { peek = 0; } int length() @property { return peek; } }
同じことを4回やってるのでちょっと長いですね、関数とか使って上手く書ける人は書いたらいいと思います。不等号とか読み順が逆になったりで微妙に関数化しにくい気がするんですがこの辺も何か上手くできるんですかね。分かりません。
これスマートなアルゴリズムだなーって思ったんですが、実はこれは典型問題らしくて、一般的にStock Span Problemというらしいです。他の人のソースコードをちらちら見てたら一番上にStock Span Problemというコメントがありました。
www.geeksforgeeks.org
見てみると確かに全く同じ問題であることが分かります。勉強になりました。
ちなみにD言語でスタックを使いたいときはわざわざ構造体作らなくてもSListってのがあってそれをスタックとして使うのが普通っぽいんですが、何か知らないですけどSListは結構遅くなっちゃうんですよね。キューも同じでDListってのがあるんですけどやっぱりこれも作ったほうが速くなります。何か公式にはDListのinsertはO(logN)って書いてあるんですけどそのせいですかね、普通はO(1)なんじゃないかと思っているんですけど、ど素人なので分かりません。分かる人がいたら教えてください。
久しぶりにブログ更新しました。
なんかこのブログこどふぉの記事の割合が多い気がします。Atcoderは日本語だし解説記事はもちろん解説動画まで上がるのであんまりブログ書くモチベにならないんでしょうかね。
後単純にAtcoderの問題のほうが難しいのでそもそもブログで解説できるほど習熟してないという面もありますね。
Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)
参加しました。今回はあのtouristが作問ということだそうです。
touristは競プロが一番強い人ですね。こどふぉやAtcoderでも1位にいるので意識していなくても覚えてしまいます。
結果はABCの3完でした。Cは割と解けてる人が少な目で、これを解けたのは嬉しかったです。レートも上がって青になりました。
ただAで問題をあまり理解できておらずミスしたり、CはCでちゃんと解けてるのにしょうもないミスで1WAしたりしてしまったのはちょっともったいなかったですかね。
Dは終わった直後は「もう少し時間あれば通せてたのに」と思ってましたが、嘘解法だったので時間あってもダメでした。
A.xo
B.o
C.xo
D.-
A. Is it rated?
問題概要
ある参加者のレートが直前と直後で変化していれば、そのコンテストはratedである。
また、もしコンテストがratedであり、かつより低いレートの参加者がより高いレートの参加者より上位になったならば、少なくとも１人のレートが変動する。
今あるコンテストが開催された。そのコンテスト直前のレートと直後のレートが、そのコンテストの上位者から順に与えられる。
上の仮定の下で、そのコンテストがratedであったか、unratedであったかを判定せよ。判定出来ない場合はmaybeと出力せよ。
考えたこと
愚直に１つずつ条件を確かめていけばよいです。
- １人でもレートが変動していれば、rated
- １人もレートの変動が無い場合、もしより低いレートの参加者がより高いレートの参加者より上位になっていれば、unratedでなければならない（このことは２番目の条件の対偶を取ると分かる）
- １人もレートの変動が無く、かつ上位から順にレートが降順（非昇順）に並んでいる場合、そのコンテストがratedであるかunratedであるかを問題文の仮定から判定することは不可能なのでmaybeとする
私は最初へんてこなコードを書いてしまったので1WAしてしまいました。
しっかりと条件をまとめられれば特に難しい問題ではなかったはずです。私は何となく、で書いてしまいましたが……。
import sys def solve(): n = int(sys.stdin.readline()) rats = [0]*n for i in range(n): ai, bi = map(int, sys.stdin.readline().split()) if ai != bi: print('rated') return rats[i] = ai for i in range(n - 1): if rats[i] < rats[i + 1]: print('unrated') return print('maybe') if __name__ == '__main__': solve()
B. T-Shirt Hunt
問題概要
Codecraft-17のコンテストが最近ありました。このコンテストの上位25人と、26 ~ 500位のなかからランダムに選ばれた25人の計50人にこどふぉのTシャツがプレゼントされます。
あなたは残念ながら25位以内には入れませんでしたが、p(26 <= p <= 500)位になれたので、Tシャツがもらえる可能性はあります。
そして今、the elimination round of 8VC Venture Cup 2017が行われています。
Tシャツのランダム25人はこのコンテストでの優勝者のスコアをsとして、以下の疑似コードで列挙される25人に与えられることになりました。
i := (s div 50) mod 475
repeat 25 times:
i := (i * 96 + 42) mod 475
print (26 + i)ここで、列挙される数字は26 ~ 500であり、かつ列挙される数字に重複は無いことが保証されています。
さて、あなたは今the elimination round of 8VC Venture Cup 2017でx点を持っており、現在トップです。
また、あなたはy(<= x)点以上あれば、このコンテストで優勝できると確信しています。
あなたはハックに成功すると+100点でき、またハックに失敗すると-50点でき、と点数を調整することができます。
このコンテストに優勝し、かつTシャツをもらうために必要な成功ハッキングの最小回数を求めてください。
なお入力で与えられるケースは必ずそのような解があることが保証されています。
考えたこと
まず、問題の読解に非常に手間取りました。今はやっとちゃんと理解できてますが、コンテスト中はcodecraftと8VC~のコンテストが別でpはcodecraftの順位でっていうのが全く分かってなく混乱してました。
それでも例を見て何となく何をすればいいかは分かって、これは総当たりをすればいいですね。
まず点数を50点刻みでy以上の値ギリギリまで減らしていき、そのたび疑似コードの通りに25人列挙してその中にpがあるかを確かめていきます。
もしこの過程でpが見つかれば、ハッキングに成功する必要は全く無いので0回になります。
そして、減らしていく方法で見つからなければ、次は50点刻みでxから増やしていってまた同じようなことをします。
50点刻みで変動させていくのでそのたびに疑似コードのiの初期値が1ずつ変化するので、高々475回やれば全ての初期値を試したことになりますから、計算量的には余裕です。
あんまりギリギリでやるのも怖いので、実際はもうちょっと余裕持たせたほうがよかったかもしれません（1000回とか）
import sys inf = 1<<60 def solve(): p, x, y = map(int, input().split()) for s in range(x, y - 1, -50): if p in list_tshirt(s): print(0) return for i in range(1, 476): s = x + i*50 if p in list_tshirt(s): print((i + 1) // 2) return def list_tshirt(s): res = [0]*25 i = (s // 50) % 475 for k in range(25): i = (i*96 + 42) % 475 res[k] = i + 26 return res if __name__ == '__main__': solve()
リストアップして、そのなかにpがあるかを確かめるのはsetでやったほうがいいですね。
C. Success Rate
問題概要
今日あなたはこどふぉでy回submitして、そのうちx回ACしました。このときAC率はx/yと表せます。
あなたには0以上1以下の好きな有理数p/q（既約分数）があります。あなたは適当に提出数を増やしてAC率をp/qにしたいと考えています。
AC率をp/qにするために必要な最小提出回数を求めてください、ただしどれだけ提出を増やしてもp/qにできないときは-1としてください。
考えたこと
何かかなり難しそうです。まず自明なケースを考えてみます。
まずp/q = 0のとき、これは明らかにx > 0のときは不可能です。分母を増やしてx/yを限りなく0に近づけることはできますが、0に等しくすることはできないからです。
x = 0のときは、これは最初からx/y = 0なので0回が答えになります。
同様にp/q = 1(p = q)のとき、x < yのときは不可能、x = yのとき0回となります。
じゃあ上記以外の場合、0 < p/q < 1のときは出来るのか？ということですが、何か直感的にはできそうな気がします。よく分かりませんが。
何か適当に数式を使って考えてみます。増やした提出数を、そのうちのAC数を
として
となる最小のを求めてくださいということですね。正式にはその組合せ
の中で
が最小になるようなものって感じですか。
tを増やしながらsを0 ~ tの範囲で動かして……という総当たりも考えられますがこれはどう考えてもTLEしそうでまずいです。何かもうちょっと上手い方法が欲しいです。
それで何か上の式を適当にいじったり、p/qとx/yの差を考えて……とかやってたんですがやっぱりなかなか上手い方法が見当たらず難航しました。
それでしばらくしてから、二次元平面にプロットして考えてみようという考えに至りました。
例えばp = 2, q = 5, x = 2, y = 10とするとこんな感じです。
原点を通る青の直線上にポツポツとある点が到達したい有理数p/qです。
そして青の領域で囲っているところが提出を増やしていくと行けるようになる点の集合です（実際にはこの青の領域上の格子点のみですが）
x, yが使われているので横軸がz, 縦軸がwとします。この図を見るとと
の交点を求めればそこから右の領域は
上の点を全て含んでいることに気が付きます。
だからまずこの交点を求めて、その交点のz成分以上のqの倍数を求めて、yを引けば、最小限必要な提出数が求まるということが分かります！
この例の場合だと15 - 10 = 5だなーと見ただけで分かりますね。
しかし上の図はq/p > x/y だから成り立つ図であって、q/p < x/yになるとちょっと様子が変わってきて、こんな感じになります。
例えばq = 2, p = 5, x = 7, y = 11としてみると以下のようになります。
今度は求めるべき交点がと
に変わったことが分かるかと思います。
このグラフからq/p = 0やq/p = 1がコーナーケースになってることも明らかに見てとることができます（平行なので直線が交わらない場合がある）
以上の考察から順番にまとめると
- q = 0(q/p = 0)の場合、x = 0なら0回、それ以外なら不可能
- q = p(q/p = 1)の場合、x = yなら0回、それ以外なら不可能
- q/p = x/yの場合は明らかに0回
- q/p > x/yの場合は
と
の交点のz成分を求めて、それ以上の最小のqの倍数を求めて、その値からyを引く
- q/p < x/yの場合は
の交点のz成分を求めて、それ以上の最小のqの倍数を求めて、その値からyを引く
といった感じでO(1)で求めることができるようになりました。
後は実際に方程式を解いてそれをコードにすると以下のような感じになります。
import sys def solve(): t = int(sys.stdin.readline()) for ti in range(t): x, y, p, q = map(int, sys.stdin.readline().split()) if p == 0: # p/q = 0 if x == 0: print(0) else: print(-1) continue if p == q: # p/q = 1 if x == y: print(0) else: print(-1) continue if p*y == x*q: # p/q = x/y print(0) elif p*y > x*q: # p/q > x/y z = (q*(y - x) + q - p - 1) // (q - p) ans = (z + q - 1) // q * q - y print(ans) else: # p/q < x/y z = (q*x + p - 1) // p ans = (z + q - 1) // q * q - y print(ans) if __name__ == '__main__': solve()
誤差に殺されないようにx/y > p/qの比較をx*q > y*pに書き換えたり、a/bの切り上げを(a + b - 1) // bで計算したりという若干の工夫がありますがやってることはシンプルです。
1回WAしてしまったのは、continueと書くべきところをreturnと書いてしまっていたからでした……もったいないです。
もうちょっと煮詰めると２つの交点のうち大きい方を取れば場合分けしなくてもいいということに気が付くので以下のような感じになります。
import sys def solve(): t = int(sys.stdin.readline()) for ti in range(t): x, y, p, q = map(int, sys.stdin.readline().split()) if p == 0: print(0 if x == 0 else -1) continue if p == q: print(0 if x == y else -1) continue z = max((q*(y - x) + q - p - 1) // (q - p), (q*x + p - 1) // p) ans = (z + q - 1) // q * q - y print(ans) if __name__ == '__main__': solve()
ちなみにグラフを描くのに使ったのはDesmosというサイトです。非常に使いやすかったです。
何かぐりぐり動かしてみると面白いので皆さんもやってみてください。
https://www.desmos.com/calculator/rvzdbbxkak
式で考えてるだけでは全然分からなかったのに、図に書いてみると急に明快に答えが分かって気持ちよかったです。
図に頼りすぎるのもちょっと危ない気がしますが、それでも図を書いてみるというのはやはり大事だなあと思いました。
D. Dynamic Problem Scoring
問題概要
VasyaとPetyaがこどふぉのあるコンテストに参加しました。そのコンテストは2時間で5問です。
このコンテストでは普段とは違う動的スコアリングという方法で点数付けでスコアが決まります。
この方法ではコンテスト前に各問題のスコアが決められるのではなく、コンテスト後に参加者に対する正解者の比を算出してその値によって問題のスコアが決められます。
より詳細には以下の表でスコアが決定されます。
| 正解者 / 参加者 | 問題の最大スコア |
| (1/2, 1] | 500 |
| (1/4, 1/2] | 1000 |
| (1/8, 1/4] | 1500 |
| (1/16, 1/8] | 2000 |
| (1/32, 1/16] | 2500 |
| [0, 1/32] | 3000 |
そして実際に正解者に与えられるスコアは、その問題の最大スコアをx, その問題を解いた時間をm(分）とすると、x * (1 - m/250)で与えられます。
さて、コンテストも終わりに近づき、残り2秒になりました。
VasyaはPetyaにどうしても勝ちたいので、Vasyaは10^9 + 7個もあるサブアカを使って問題の正解者/参加者を変化させて点数を調整することで、Petyaの点数を上回ろうと考えました。
Vasyaはサブアカを使って、自分が解けた問題をそのサブアカにACさせることができます。自分が解けなかった問題はACさせることができないことに注意してください。また、不正解にさせることは自分が解けたか否かに関わらず可能です。
ただ、あまり大っぴらにやるとバレそうなので出来るだけ少ないアカウントを使ってその目的を達成したいです。
Vasyaの提出状況、Petyaの提出状況、およびその他の参加者の提出状況が与えられるので、上の問いに答えてください。
ただしどれだけサブアカを使っても上回ることができない場合は-1と答えてください。
考えたこと
最初この問題を見たとき「何だこれは……」という感じで全くどうやって解けばいいか分かりませんでした。というかめちゃくちゃ複雑そうに見えました。
けど冷静になって考えるとそれほど難しくないような気がしてきました。アカウントを増やしたときの戦略はシンプルです。
自分の提出状況をv_i, petyaの提出状況をp_iとすると、
- v_i = -1のとき「自分は解けなかった」ので、問題iは不正解にさせることしかできない
- p_i = -1のときは「相手は問題iを解けなかった」ので問題iの価値を高めるとよい、すなわち問題iは不正解にすればよい
- p_i != -1かつ、v_i < p_iのとき「自分は相手より早く問題iが解けた」ので、問題iの価値を高めるとよい。よって問題iは不正解にすればよい
- p_i != -1かつ、v_i = p_iのとき「自分と相手は同時に問題iが解けた」ので、問題iで点数差は発生しない、よってどちらでもよい
- p_i != -1かつ、v_i > p_iのとき「相手は自分より早く問題iが解けた」ので、問題iでは相手に点数差をつけられている。よって問題iの価値は下げて、その点数差を出来るだけ小さくするべきである。つまり、問題iは正解させるとよい。
と、こんな感じですね。もっと簡潔に条件をまとめると
- p_i != -1かつv_i > p_iのとき、そのサブアカに問題iを正解させる
- それ以外の場合、そのサブアカに問題iを不正解にさせる
という戦略を取るのが最も良いことになります。
ただ問題はサブアカの数が10^9 + 7とめちゃくちゃ多いことですね。これでは全探索は出来ません。
しかし、アカウントを増やせば増やすほど有利になるはずです。つまり単調性が成り立っているということなので……二分探索すればlog(10^9 + 7)ぐらいで終わりますから余裕ですね！
……と、意気揚々と二分探索を書くとWAになります。
実は、「アカウントを増やせば増やすほど有利になる」という仮定、つまり単調性を仮定したことがどうやら間違っていたようです。
というのも、自分が問題iを解けずかつ相手が問題iを解けていた場合、サブアカを増やしてしまうと、自分が解けてないのでそのサブアカには問題iを不正解にさせることしかできません。（私はこの条件を見落としていました）
つまり、問題iの価値が高まってしまい、アカウントを増やしたのが逆効果になってしまっています。
だから「アカウントを増やせば増やすほど有利になる」というのは嘘だったわけですね。
じゃあどうすればいいんだ……と思いますが、ここで制約をよく見るとコンテスト参加人数が高々n <= 120です。
そして、動的スコアリングの表を見ると、実は10^9 + 7人も追加しなくてもよいことが分かります。
まず、アカウントを増やしてやりたいことは「問題iの価値を高める（難化させること）」「問題iの価値を低める（易化させること）」です。
n = 120のとき、前者は120/120 = 1から最も問題の価値をあげようとすると、必要な人数は120 / (120 + m) <= 1/32を満たすmです。
後者は1/120から最も問題の価値を下げようとすると、必要な人数は(1 + m) / (120 + m) > 1/2を満たすmです。
これらを解くと、だいたい4000人もいれば十分だということが分かります。
つまり、10^9 + 7人いるけど実際は4000人まで増やしてダメだったらもうそれ以上増やしても無理なものは無理ということです。
これぐらいなら普通に下から全探索しても余裕で間に合うので全探索すればいいよってことになります。
ということですね、実際は計算間違いとかしてて4000じゃ足りない、なんてことがあると嫌ですからもうちょっと余裕のあるところまで回せばいいと思います（50000とか、速い言語ならもっと回してもいいと思います）
この問題要約すると「単純な戦略を決めて、後は全探索するだけ」なんですよね。それでもかなり正解者が少ない(div2だとがくっと落ちてました）のは面白いです。
「まず問題文を読むのが面倒」とか「実装が重い」とか「前３問で時間使い果たした」とかいろんな理由があるとは思いますが……
- 「オーダーのざっくりした計算量だけでなく、実際により詰めた具体的な計算量の解析も大事」
- 「基本は全探索」
- 「単調性も確認せず安易に二分探索に走ってはいけない」
などの教訓を得ることができる問題だなあと思いました。
特に私は二分探索が好きで最大・最小とか聞くとすぐ二分探索を使いたくなってしまうので気を付けたいと思いました。
import sys inf = 10**9 + 7 def solve(): n = int(sys.stdin.readline()) v = [int(vi) for vi in sys.stdin.readline().split()] # Vesya p = [int(pi) for pi in sys.stdin.readline().split()] # Petya cnt = [0]*5 for i in range(5): if v[i] != -1: cnt[i] += 1 if p[i] != -1: cnt[i] += 1 for i in range(n - 2): a = [int(ai) for ai in sys.stdin.readline().split()] for j in range(5): if a[j] != -1: cnt[j] += 1 for i in range(4000): if check(n, v, p, cnt, i): print(i) return print(-1) def check(n, v, p, cnt, m): tot = n + m solved = cnt[:] dif = 0 for i in range(5): if p[i] != -1 and v[i] > p[i]: solved[i] += m for i in range(5): if solved[i]*2 > tot: max_score = 500 elif solved[i]*4 > tot: max_score = 1000 elif solved[i]*8 > tot: max_score = 1500 elif solved[i]*16 > tot: max_score = 2000 elif solved[i]*32 > tot: max_score = 2500 else: max_score = 3000 if v[i] == p[i] == -1: pass elif v[i] == -1: dif -= max_score * (250 - p[i]) // 250 elif p[i] == -1: dif += max_score * (250 - v[i]) // 250 else: dif += max_score * (p[i] - v[i]) // 250 return dif > 0 if __name__ == '__main__': solve()
総評
touristが作問のコンテストということでどんな問題が出るのかなあ、と期待？していたのですが、全体的に「読むのが大変」「実装もちょっと大変」なコンテストだなあという印象でした。
正直言うと、強い人が作る問題って「問題文はシンプルで分かりやすい、しかし解くのは難しい。でも解法は思いつけばとてもシンプルに解ける」と、そんな感じの問題だろうなと思っていたからです。
特に今回のBとかDみたいな問題はまず出さないだろうみたいな謎の先入観があったので、少々意外でした。
Bは正直読むのがしんどいだけかな……という感じでしたが、Cは面白かったですし、Dも教訓が得られる良い問題だなあと思いました。
