ABCDの4完。Eを終了2分前に提出するもWA

A - Curtain

A-2Bですね。Max(0,A-2B)と書くとちょっとカッコイイ。

B - TAKOYAKI FESTIVAL 2019

N=50なので全探索いけますね。

C - Slimes

一文字前と比較して違う文字であればカウント

D - Triangles

許される計算量から逆算しました・・・

$N\leq 2*10^{3}$ → $N^{2} \log N$ ならいける→a,bを決める→cの条件は $\max(a-b,b-a) \lt c \lt a+b$ →cを二分探索。

こまごまと条件付けたけど $a\leq b\leq c \lt a+b$ で良いみたいだ。(a=L[i]、b=L[j]、c=[L[j+1]、upper_bound(a+b-1)))
a+bは単調増加であることを利用すれば計算量を落とせるみたいです。

E - Travel by Car

サイズ的にワーシャルフロイド使えそう→最短距離出しても燃料補給数と直接は結びつかない→ダイクストラで最短距離を進みながら補給数カウントしていけばいいんじゃないか？→距離がLを超える道が選ばれる可能性あるやん→Lを超える道は切り落としとこ→やった！入力例通った！→提出！(終了2分前)→WA！→ｸﾞﾜｰｯ！ｻﾖﾅﾗ！しめやかに爆発四散！

ワーシャルフロイド法を使って解く場合
1回ワーシャルフロイドして最短距離を出す。L以下でいける距離は1とみなす。
もう1回ワーシャルフロイドすれば燃料Lでいける最大範囲を辿っていくので距離が補給回数+1になる。
ダイクストラ法を使って解く場合
補給回数と残燃料で探索する。補給回数が少ない方、補給回数が同じ場合残燃料が多い方を優先探索。これを各点について行う。

敗因

ワーシャルフロイドを使って解く方法を早々に捨てた
距離が直接答えに結びつかないことはわかっていたのに距離でダイクストラ法を使った
$O( (M+N)\log N)$ の方法を使った。 $M=N(N-1)/2$ で各点についてなので計算量は $O(N^{3} \log N)$ になりTLE。 $O(N^{2})$ の方法を使えば時間内で解ける。

グラフの性質(密か疎か)にも気を付けないといけませんねえ

F - Distinct Numbers

解説見ながら*1

$a_{i}$ を数列 $A_{i}$ に現れる $i$ の個数とする。このとき、

$TK \leq \sum_{i} \min(a_{i}, T)$ が成立するなら $K$ 枚食うのを $T$ 回できる

$a_{i} \lt T$ の範囲は累積和で求まる。 $T \leq a_{i}$ の範囲はTx個数。境界を二分探索で求める。

//条件判定(S[i]は累積和。aiはソート済み)
Func<long, long, bool> ok = (T, K) =>
{
    long i = ~Array.BinarySearch(ai, T, new lower_bound<long>());
    long sum = S[i] + T * (N - i);
    return T * K <= sum;
};

各 $K$ について条件を満たす上限の $T$ を二分探索で求める。

long l = 0, r = N / K + 1;//l:ok, r:ng
while (l + 1 < r)
{
    var T = (l + r) / 2;
    if (ok(T, K)) l = T;
    else r = T;
}
WriteLine(l);

条件判定の計算量が $O\log N$ 、上限を求めるのに $O\log N$ 、これを各 $K$ についてなので $N \log^{2} N$ 。これも単調性を利用すると計算量を落とすことができます。(ソートの計算量が $O(N \log N)$ なので効果は地味かも)

判定の証明

$a_{i} \leq T,\,\,\, \sum_{i} a_{i}=TK$ から開始*2。

ここから $K$ 枚食うと、 $a_{i} \leq T-1,\,\,\, \sum_{i} a_{i}=(T-1)K$ となる。
ここから $K$ 枚食うと・・・を繰り返すと結局 $K$ 枚食うのを $T$ 回繰り返せることがわかる。

細かい部分

$a_{i} = T$ である $a_{i}$ は最大でも $K$ 個なので、 $K$ 枚食うと $a_{i} \leq T-1$ となる。 $\sum_{i} a_{i}-K=TK-K=(T-1)K$

ところでカード食う高橋くんは何者なんでしょうね？

*1:解説をちゃんと理解できてるかはしらぬい

*2: $T \lt a_{i}$ でも問題なしだけど便宜上

trsing’s diary

勉強、読んだ本、仕事で調べたこととかのメモ。

AtCoder Beginner Contest 143参加メモ