あいさつまわり [パソコン甲子園2020 予選 C]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0430

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0430/review/5787700/hamayanhamayan/C++14

今回の問題はどういう順番で家を訪ねていくかというのを考えていくものであるが、
全組合せを見ていく方法は実装も大変だし、計算量も間に合わないので、うまくやる必要がある。
今回は、貪欲法をつかって解いていこう。

貪欲法

貪欲法とは一定のルールに従って問題を解くことで最適解を得ようとする方針である。
一直線上に

1   2   x0     3      4  

みたいに位置取りがなされている場合にどうやって回るのが最適っぽいかを考えてみる。
左右に連続的な移動しかできないということと、末端に必ず移動しないといけないということを考えると、
x0から左端の1に向かってそれから右端の4に向かうか、x0から右端の4に向かってそれから左端の1に向かう
のが最適となりそうである。

よって最適解は、以下の2操作のうち、移動距離が小さい方になる。

x0 → 左端 → 右端
x0 → 右端 → 左端

まずは、左端mi, 右端maを計算して、2点間の距離は差の絶対値となるので、abs関数をうまく使いながら
貪欲法で最適解を求めていこう。

int N, x0, x[101];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> x0;
    rep(i, 0, N) cin >> x[i];

    int mi = inf;
    rep(i, 0, N) chmin(mi, x[i]);

    int ma = -1;
    rep(i, 0, N) chmax(ma, x[i]);

    int ans = min(abs(x0 - mi) + abs(mi - ma), abs(x0 - ma) + abs(ma - mi));
    cout << ans << endl;
}

商店街へのお出かけ [パソコン甲子園2020 予選 B]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0429

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0429/review/5787654/hamayanhamayan/C++14

与えられた判定問題を実装していく、実装問題となる。
条件をプログラムに落とすときに、色々混乱してしまうかもしれないので、そういう場合は変数に分かりやすい
名前を付けたりしてまとめていこう。

答えは条件にあるように4パターンを条件分岐で実装してもいいのだが、少し技ありな実装を自分は行っている。
ちょうど二人ともたどり着けるとき3は1+2となっているので、ヤエちゃんがたどりつけるなら答えを+1,
タケコちゃんがたどりつけるなら答えを+2とすることで、条件を満たす。
こうすることで4パターンに分岐させるよりもやや良い感じになる。

これ以降は補足だが、この部分はプログラミングではフラグ操作とも呼ばれる。
ビット操作とも言ったりするが、下位1ビットがヤエちゃんがたどり着けるかのビットになっており、
下位2ビットがタケコちゃんがたどり着けるかのビットになっている。
競技プログラミングをやっていくにあたってビット操作を意識する場面があったりするので、
そういう観点でも考えてみるといいと思う。

int w, m, s;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> w >> m >> s;

    int yae2Joe = s;
    int takeko2Joe = w - s;

    int ans = 0;
    if (yae2Joe <= m) ans += 1;
    if (takeko2Joe <= m) ans += 2;
    cout << ans << endl;
}

緯度経度 [パソコン甲子園2020 予選 A]

https://onlinejudge.u-aizu.ac.jp/challenges/sources/PCK/Prelim/0428

解説

https://onlinejudge.u-aizu.ac.jp/solutions/problem/0428/review/5787569/hamayanhamayan/C++14

基本的な入出力を問うような問題。
競技プログラミングを始めるには、言語を決めて、入出力のやり方を覚える所がスタート地点になる。
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ - Qiita
完全初心者の場合はこのあたりや、色々出ている本から始めていくといいと思う。

今回の問題では3600で割ることで答えを得ることができる。
「計算結果の小数点以下は切り捨てる」という条件があると思うが、これは変数を整数型にしておいて、整数で割れば、
自然と答えは切り捨てになるので、何も考えずに実装すると勝手にそうなる。

int La, Lo;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> La >> Lo;

    La /= 3600;
    Lo /= 3600;

    cout << La << " " << Lo << endl;
}

Substrings [AtCoder Beginner Contest 214 F]

https://atcoder.jp/contests/abc214/tasks/abc214_f

前提知識

• 動的計画法

解説

https://atcoder.jp/contests/abc214/submissions/25062984

今回の問題は部分列DPを見たことが無いと難しいかもしれない。
こちらを理解しておくことで、今回の問題をスムーズに理解できる。

部分列DP

部分列DPについては、
部分列 DP --- 文字列の部分文字列を重複なく走査する DP の特集 - Qiita
が最も細かい。
補足であるが、この部分列DPについてはDEGwerさん資料でgreedyからの帰着にて触れられており、
それ以外にも多数の重要典型がまとめられているので、必見である。
「数え上げテクニック集」を公開しました
DEGwerさんの数え上げテクニック集問題まとめ - はまやんはまやんはまやん

さて、以降部分列DPについては理解できているものとして話を進める。
真面目に部分列DPを説明してもいいのだが、先人の記事を参照する方が恐らくwin-winだ。
この問題は部分列DPの2番目の問題として最適である。1番目の問題として取り込んでも、それなりに問題ない。

今回の問題

クエリを見直してみよう。
基本的には印がついている場合だけ文字を残してできる部分列を同じ文字については
同一視して数え上げるというのが要求事項となる。
これはまさに部分列DPの典型問題として取り上げられているものである。
違いは選択できる文字が連続してはいけないということになる。

今回のアルゴリズム

ベースは部分列DPと同様である。

dp[i][lst] := i文字目までの文字を使って最後がlstであるような文字列の組み合わせ
として、文字列選択をする場合は、「貪欲に」先頭から文字を使う場所を選択することにする。

これだと全く同じなのだが、遷移時にもう一つ条件を付け加えることにする。
貪欲に文字を選択した場合に隣の文字になってしまったら、もう一度貪欲に文字を選択して遷移先を決める。
つまり、

baa  
^  

と、bを選択している状態の場合、次の文字としてaを使うことを決めて、貪欲に遷移すると、
1つ隣となるが、これだと条件を満たさなくなるので、もう一度同じ文字aで貪欲に遷移させて、

baa  
  ^  

のように遷移させることにする。
このように必要なら更に遷移させることで、貪欲に選択して、かつ、隣でない要素を素早く見つけることができる。

実装

部分列DPの実装で厄介な所が、文字列について次にとある文字が来る場所を見つける部分である。
自分はこの辺は昔に実装してStringMasterとしてまとめている、今回貼ったのはその一部である。

sm.getNext(idx, char) := 文字列のidx番目以降で最初に文字charがある添え字

dpというか累積和的な感じというかで配列を準備して、O(1)で以上の関数が答えられるようにする。

string S;
int N;
mint dp[201010][26];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S;

    StringMaster sm(S);
    N = S.length();

    rep(nxt, 0, 26) dp[sm.getNext(0, char('a' + nxt))][nxt] = 1;
    rep(i, 0, N) rep(lst, 0, 26) rep(nxt, 0, 26) {
        int i2 = sm.getNext(i + 1, char('a' + nxt));
        if (i + 1 == i2) i2 = sm.getNext(i2 + 1, char('a' + nxt));
        dp[i2][nxt] += dp[i][lst];
    }

    mint ans = 0;
    rep(i, 0, N) rep(lst, 0, 26) ans += dp[i][lst];
    cout << ans << endl;
}

Sum of Maximum Weights [AtCoder Beginner Contest 214 D]

https://atcoder.jp/contests/abc214/tasks/abc214_d

前提知識

• （主客転倒）
• UnionFind

解説

https://atcoder.jp/contests/abc214/submissions/25065159

見た目はかなり難しい。
方針が分かれば実装はかなり簡単で済むのだが、考え方は難しい。

何がモチベーションとなるか

今回の問題はすべての頂点間に対する処理になるので、すべての頂点間の列挙だけでO(N²)となる。
愚直にやっていくと、

すべての頂点間の組み合わせについて f(i,j) の総和

が答えになる。
だが、ここで役立つ条件としてf(i,j)は重みの種類だけパターンがある。
つまり、f(i,j)を全探索することは可能であるということである。
よって、

すべてのf(i,j)について f(i,j)×それを満たす頂点間の組み合わせ の総和

を計算することにしよう。
この組み合わせを高速に計算できれば、計算量が間に合いそうだ。
このように観点を変えて計算することを主客転倒と（一部の人は）呼んでいる。
まあ、名前にそれほど意味は無くて汎用的に使える思考法という感じである。
あの〜、お詫びと言っては何ですけどちょっと数え上げでよく見るらしい「主客転倒」の解説今から書くんで… - physics0523's 精進ログ

その組み合わせをいかに求めるか

さて、この組み合わせをいかに求めるかという部分に主軸を置いて考えてみよう。
f(i,j)がとある辺kの重みw[k]である場合について考えてみる。
u[k] <- w[k] -> v[k]
という辺があって、これを単純に通る頂点の組について考えると、
u[k]側の頂点の個数×v[k]側の頂点の個数となる。
だが、これでは別のw[k]以上の頂点が含まれる可能性がある。
よって、求めたい組合せは

u[k]側のw[k]以下の辺を使って到達可能な頂点の個数×v[k]側のw[k]以下の辺を使って到達可能な頂点の個数

となる。この式まで理解することが完全理解につながる。
よくわからない場合はグラフを書いて理解してみよう。

到達可能な頂点の個数

これだけを見て考えてみると、一般的にはUnionFindによって実現ができそうだなと思い浮かぶ。
その方向性で考えると、工夫をすることでUnionFindを使ってこの個数を高速に求めることができる。

UnionFindをうまく使って要求を満たす

w[k]の辺を処理する場合は、w[k]以下の辺について結合処理がなされている必要がある。
よって、辺の評価は重みが小さいものから順番に、
式の計算→結合処理→式の計算→結合処理→…
という風にやっていけば、結合部分（連結成分）に含まれる頂点数は高速に求まるので、
要求されている計算を行うことができる。

int N;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    vector<tuple<int, int, int>> edges;
    rep (i, 0, N - 1) {
        int u, v, w;
        cin >> u >> v >> w;
        u--; v--;
        edges.push_back({ w, u, v });
    }
    sort(all(edges));

    UnionFind uf(N);
    ll ans = 0;
    fore(edge, edges) {
        int u, v, w;
        tie(w, u, v) = edge;

        ans += 1LL * w * uf.getValues(u) * uf.getValues(v);
        uf(u, v);
    }
    cout << ans << endl;
}

Distribution [AtCoder Beginner Contest 214 C]

https://atcoder.jp/contests/abc214/tasks/abc214_c

解説

https://atcoder.jp/contests/abc214/submissions/25034924

今回の問題は少し制約を緩めたものから考えるのがよい。
円周上というのをやめて一直線上で動けるということを考えることにすると、
解法を思いつく人も結構いるかもしれない。

円周をやめる

すると、DPで解けそうな感じがしてくる。
（DPでなくてもいいのだが、DPのコンテキストに乗せると理解が早いと思ってそうした）

dp[i] := i番目に宝石が来る最短時間

1番目のすぬけ君は宝石を直接もらうしかないので、dp[0] = T[0]
それ以降は前のすぬけ君からもらうこともできるので、dp[i] = min(T[i], dp[i - 1] + S[i - 1])となる。
ここが理解できているとかなり解法に近づけている。

円周を入れる

例えば 1 2 3 4 5とすぬけ君がいて、4->5->1->2と宝石が動いて2番目のすぬけ君が最適に受け取るという
ルートもあり得る。なので、問題にもあるように円周を戻してどうなるか考えてみる。
DP構造もループさせてみよう。
つまり、dp[0] = min(T[0], dp[N - 1] + S[N - 1])で更新ができるということである。
仮にこれでdp[0]がより良い結果となった場合、それがdp[1]にも影響する可能性がある。
なので、1度DPを行った場合に2周目を行う必要がある。

しかし、3周目以降は行う必要が無く2週目までで問題ない。
これは1周を超えて宝石を渡すのは自明で無駄な行為であるからである。

DPは必要か？

DPの方が分かりやすい場合はこれで答えてもいいし、DPの更新を見てみると1つ前の要素しか見ていないので、
1つ前の要素、より直接的な表現をすると、これまでの最適解を保持しながら2周分更新処理をやっていけば
答えが求まる。自分の実装はそうなっている。

int N, S[201010], T[201010];
int ans[201010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> S[i];
    rep(i, 0, N) cin >> T[i];

    int mi = inf;
    rep(i, 0, N) {
        chmin(mi, T[i]);
        ans[i] = mi;
        mi += S[i];
    }
    rep(i, 0, N) {
        chmin(mi, T[i]);
        chmin(ans[i], mi);
        mi += S[i];
    }

    rep(i, 0, N) printf("%d\n", ans[i]);
}

How many? [AtCoder Beginner Contest 214 B]

https://atcoder.jp/contests/abc214/tasks/abc214_b

解説

https://atcoder.jp/contests/abc214/submissions/25065793

今回の問題は枝刈り全探索という方針を用いる。
全探索をしていくのだが、自明な「枝刈り」、つまり、探索を途中でストップすることで、
無駄な探索を大幅に省くことができて、高速化でき、ACできるということになる。
色々な場面でこのような方針は適用することができるが、その有効性を学ぶのによい問題であると思う。

全探索

枝刈りしない全探索を書く。
といっても既に一部枝刈り済みとも取れるが、a,b,cの範囲を雑に指定して探索していくことを考えてみよう。
a+b+cの総和がS以下である必要があるので、a,b,cは少なくとも0～Sの範囲になっているはずである。
よって、a,b,cを0～Sの範囲でループさせる3重ループを書くので、全部で10⁹通りの組み合わせを確かめていく。
競プロでは組み合わせは多くても10⁷通りくらいしか探索できないので、これでは間に合わない。
別の良い方をすると計算量がO(S³)となるので間に合わない。

「枝刈り」

ある一定のルールで探索をストップすることにする。
C++で言えばbreakを使ってループを途中で抜けることにする。
その一定のルールとは「a+b+c≦S」か「abc≦T」のどちらかが満たされなくなったら、即ループを抜けて終了する。
これだけで大幅に探索状態が削減されてTLE（計算時間超過）からACにすることができる。

気持ち沢山の探索範囲を減らせそうな感じはする。
特にabc≦Tという条件が割と厳しい。少し緩いab≦Tという条件で考えてみる。
T=100であるとき、a=1ならばb=1...100の100通りだが、a=2ならばb=1...50の50通りと半減してしまう。
aが大きくなれば使えるbはより急激に少なくなるし、abc≦Tならなおさらである。

より厳密な話

より厳密にこの枝刈りに正当性を与える知識をここに書いておく。
高度合成数 - Wikipedia
高度合成数という話があり、約数の個数は一般にかなり小さくなり、この小ささを利用してアルゴリズムを
作っていく問題も多くある。
abcの組はT以下の数の因数分解の結果となる。
Tの上限は10000であり、その場合の約数の個数の最大は72個なので、abcと3つの因数に分解する組合せも
かなり少なそうという仮定が立つ。
ここまで思考が進んでいれば、肌感でかなり間に合いそうな感じがする。
心配なら今回の問題ではS=100, T=10000で計算量が最大になるので、
これでコードテストを使ってストレステストしてもいい。

int S, T;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> T;

    int ans = 0;
    rep(a, 0, S + 1) rep(b, 0, S + 1) rep(c, 0, S + 1) {
        if (S < a + b + c) break;
        if (T < a * b * c) break;
        ans++;
    }
    cout << ans << endl;
}