AGC025参加記

問題: https://beta.atcoder.jp/contests/agc025
sub: https://beta.atcoder.jp/contests/agc025/submissions?f.User=skjmp

A

制約 N<=1e5 を見ると O(n) が通りそう
A+B=N を満たすAとBを全探索するとき、Aを決めるとBが決まる(B=N-A)なので全探索にはO(n)回かかりそう

なので全探索を考えます。

for(int i=1;i<=n/2+1;i++){
    int A=i;
    int B=N-A
    //TODO 「整数の各位の桁の和」の最小値を更新する
}

「整数の各位の桁の和」を求める処理をketawa関数に書くとすると

int mi=INT32_MAX;
for(int i=1;i<=n/2+1;i++){
    int A=i;
    int B=N-A
    mi=min(mi, ketawa(A)+ketawa(B));
}

ketawa関数は整数を10で割った時のあまりがその整数の1の位の値になることを考えると

int ketawa(int n) {
    int cnt = 0;
    while (n > 0) {
        cnt += n % 10;
        n /= 10;

    }
    return cnt;
}

それで投げたら通りました。この時ketawa処理にO(logn)かかるため全体の計算量がO(nlogn)になっていたことには気づいていません。

B

mod演算が苦手なのでCを読みます

C

A(高橋)くんとB(青木)くんが最適に動いたときスコアがどうなるか的な問題が来ました。何もわからないのでサンプルをノートに書いてシミュレーションします。方眼ノートが便利でした。高橋くんの気持ちになってサンプルをシミュレーションすると、
* 自分が渡された区間内にいたら動かない
* 渡された区間が右にあったら区間の左端に移動する
* 渡された区間が左にあったら区間の右端に移動する

が最適ムーブな気がしてました。ほんとに最適かな？って思ったんですが、
* 同じ方向に連続して動く場合、今端を超えて動いても後で動いてもスコアは変わらないこと
* 違う方向に動く場合は、端を超えて動くとスコアが悪くなること
* 今動く必要がない場合、動く必要がある区間が渡されてから動いてもスコアが変わらなそうなこと

から高橋くんのムーブはそういうことにしました。

次に青木くんのムーブを考えると、

0
   --           //1番目に渡す区間(区間1)
      ---       //区間2
           --   //区間3

のような区間の渡し方は、1番目に渡す区間が2番目に渡す区間の中継地点になっているので、嬉しくない気がしてきます。

0
      ---       //1番目に渡す区間(区間1)
   --           //区間2
           --   //区間3

のような区間の渡し方は、高橋くんが渡された区間の近い方の端にタッチすることを考えると、高橋くんがジグザグに動いてくれてスコアが稼げそうです。

高橋くんがジグザグに区間を往復する場合、
* 区間の右端に触る->区間の左端に触る->区間の右端に触る...
* 区間の左端に触る->区間の右端に触る->区間の左端に触る...
の2通りがありえます。

今、高橋くんが右端左端右端...の順で区間に触ることを考えると、高橋くんが一番長い距離をジグザグに走る場合、高橋くんへの区間の与え方は
1. 区間の右端が、残っている区間の中で一番右にある区間を渡す
2. 区間の左端が、残っている区間の中で一番左にある区間を渡す
3. 区間の右端が、残っている区間の中で一番右にある区間を渡す
4. ...

になりそうです(お気持ち)。

そういうことで与えられた区間を左端でソートしたものと右端でソートしたものをそれぞれ持って、右左右...のパターンの場合のスコアと左右左...のパターンの場合のスコアをシミュレーションします。そして大きかった方を答えにします(軽く書いていますが実装に40分以上かかっています)。

シミュレーションの処理に、区間内に高橋くんがいた場合の処理を書き忘れていると、サンプルが通りません(ありがとうAtCoder!)。

シミュレーション前処理のソートがO(nlogn)
シミュレーションがO(n)
N<=1e5

なので計算量的にも問題なさそうです。

投げます。通りました。やった！俺はやったぞ！

D

なにもわかりません。