はまやんはまやんはまやん

hamayanhamayan's blog

高速道路網 [パソコン甲子園2020 予選 H]

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

前提知識

解説

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

まずは問題の整理をしていく。
与えられている地点と道路はグラフとしてマッピングすることができる。
この条件で面白い部分がある。

「どのように道路をたどっていっても、同じ地点に戻ることはない。」

これはグラフにループ構造が無いことを示している。
よって、このグラフはDAGであることがこの条件から分かる。
DAGはループの無い有向グラフのことであるのだが、DAGであることの有用性の1つとしてDPが行えるということがある。

この問題の前に

DAG上での問題という前提で考えると何回も似たような問題を見てきた。
トポロジカルソートをした上で、その順番でDP更新をしていく。
今回は2種類のDPを作っていくのだが、ちょっと別の問題を使って理解を深めていくことにしよう。

「始点から各地点に行くまでに何通りの移動方法があるか」という問題を考えてみる

「始点から各地点に行くまでに何通りの移動方法があるか」

これはDPで計算が可能である。

dp[cu] := 始点から地点cuに行くまでに何通りの移動方法があるか

そのまんまなDPテーブルであるが、これを計算していけばいい。
トポロジカルソートをして、ソート順にDPを更新していく。
最初はdp[0] = 1として、更新時は地点cuから地点toへ移動可能だとするとdp[to] += dp[cu]とすればいい。

まず、これが理解できる所まで来ないと、この問題を理解することは難しい。
DPをしっかり理解していることと、トポロジカルソートをしっかり理解していることが必要なので、
そちらを学習してくるのもいいかもしれない。

では、これは理解できているものとして、もう少し進んだ問題を考える。

「始点から各地点に行くまでの全ての経路の長さの和は」

以下のように2つのdpを使って計算していこう。

comb[cu] := 始点から地点cuに行くまでに何通りの移動方法があるか
tot[cu] ;= 始点から地点cuに行くまでの全ての経路の長さの和

tot[cu], comb[cu]がすでに計算されているものと仮定して、tot[to], comb[to]をどう計算するか考えよう。
combについては先ほどと同じなので、comb[to] += comb[cu]でよい。
問題はtotであるが、これまでの経路の長さの和は考慮されるべきなので、tot[to] += tot[cu]は決まっている。
これで考慮されていない長さはcuからtoに移る長さの分となる。
長さは1で固定で、本数は丁度comb[cu]と一緒になっている(!)
なので、考慮されていない長さの分も足してtot[to] += tot[cu] + comb[cu]で更新ができる。
初期状態はtot[cu] = 0, comb[cu] = 1で始まる。

元の問題

さて、やっと元の問題に戻れる。
今回求めたい問題は「始点→地点i→終点」となる全ての経路の長さの和を求める問題である。
これを分割して求めることにする。
始点からの経路と終点への経路に分けて計算する。

始点→地点iに至る全ての経路の長さの和を求めるには、1つ前にやった問題をやれば求めることができそうである。
仮に地点i→終点の移動方法が1通りである場合は、1つ前にやった問題の結果をそのまま使用すればいいのだが、
複数ある場合は、その組み合わせ分だけ、その経路の長さの和が使われることになる。
なので、地点i→終点の移動方法も計算したくなる。

始点→地点iの計算は先ほどやったが、同じ問題を地点i→終点で計算するにはすべての辺の方向を逆転させて
同じ計算をすればいい。
辺の方向を逆転させることで経路が変化することはないので、これで問題ない。

答えのアルゴリズム

長々書いてしまった。答えを簡潔にここから書き始める。

始点→地点iについて、comb, totを計算する。これをcomb1, tot1としておく。
次に辺の方向を逆転させて、同じ計算をして、
地点i→終点について、comb, totを計算する。これをcomb2, tot2としておく。

各地点iについて、
始点→地点iの全ての経路の長さの和はcomb1[i] * tot2[i]で計算ができ、
地点i→終点の全ての経路の長さの和はcomb2[i] * tot1[i]で計算ができるので、
「始点→地点i→終点」となる全ての経路の長さの和はcomb1[i] * tot2[i] + comb2[i] * tot1[i]となる。

int N, M;
int u[2510], v[2510];
//---------------------------------------------------------------------------------------------------
pair<vector<ll>, vector<ll>> getCombination(int root) {
    vector<int> E[50];
    TopologicalSort ts(N);
    vector<int> ord;

    rep(i, 0, M) {
        E[u[i]].push_back(v[i]);
        ts.add_edge(u[i], v[i]);
    }
    ts.sort(ord);

    vector<ll> comb(N, 0), tot(N, 0);
    comb[root] = 1;
    tot[root] = 0;
    fore(cu, ord) fore(to, E[cu]) {
        comb[to] += comb[cu];
        tot[to] += tot[cu] + comb[cu];
    }
    return { comb, tot };
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, M) cin >> u[i] >> v[i], u[i]--, v[i]--;

    auto p1 = getCombination(0);
    rep(i, 0, M) swap(u[i], v[i]);
    auto p2 = getCombination(N - 1);

    rep(i, 0, N) {
        ll ans = p1.first[i] * p2.second[i] + p2.first[i] * p1.second[i];
        cout << ans << endl;
    }
}

加工機 [パソコン甲子園2020 予選 G]

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

解説

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

シミュレーション高速化していく問題となる。
加工後の高さをもっていきながらシミュレーションをしていきたい所ではあるが、盤面が大きすぎる。
なので、加工された部分のみを保持しながらシミュレーションを頑張っていくことにする。
各所、切削をしていくが、その切削によって表面積がどう変化したかという感じで、差分計算をしていくことにする。

初期状態

最初は、全部つるつるの状態なので、6面の表面積を足したものになる。
具体的には2WD + 2DH + 2HWが初期状態となる。

差分計算

切削をしていくが、その際の表面積の変化は周りの高さがどうであるかに依存することになる。
4面あるので、4面について場合分けを書いていってもいいが、実際にはやっていることはさほど変わらず、自分のように
dx, dyを使用して4面を同じコードでさばいていくことにする。

盤面をすべて持つことはできないので、mapで保持することにする。
map<int,map<int,int>>みたいにしてもいいのだが、mapはまあまあ重いので、配列でx座標については配列にして置いている。

中で3択の場合分けをしている

場合分け1: 盤面からはみ出してしまう場合

はみ出す場合は、そちら側は切削した分だけ表面積がなくなってしまうので、ans -= z[i]をしよう。
反対側の表面積があるのでは?と思うかもしれないが、そちらの側面もループであとで考慮するので、
このはみ出す方向に対する表面積としては減るだけ

場合分け2: まだ切削してない部分と面している

この場合は切削した分だけ表面積が増えるので、ans += z[i]すればいい。

場合分け3: 既に切削している部分と面している

この場合はちょっと複雑なのだが、差分計算でよくやる、「現状を消す→処理→現状を足す」ということをすればいい。
現状を消すの部分は、今切削している所と今見ている隣接している所の高さの差が現在生じている表面積になっているので、
ans -= abs(changed[xx][yy] - cur)とする。
これで、切削処理をするので、curがcur - z[i]となる。
それでから現状を足すので、ans += abs(changed[xx][yy] - (cur - z[i]))とする。

注意点

これで最終的にansを答えればいいのだが、オーバーフローに注意。
long longで全体的に計算すること。

ll W, D, H; int C;
int x[101010], y[101010]; ll z[101010];
map<int, int> changed[101010];
int dx[4] = { 0, 1, 0, -1 }, dy[4] = { -1, 0, 1, 0 };
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> W >> D >> H >> C;
    rep(i, 0, C) cin >> x[i] >> y[i] >> z[i];

    ll ans = 2 * W * D + 2 * D * H + 2 * H * W;

    rep(i, 0, C) {
        ll cur = H;
        if (changed[x[i]].count(y[i])) cur = changed[x[i]][y[i]];

        rep(d, 0, 4) {
            int xx = x[i] + dx[d];
            int yy = y[i] + dy[d];

            if (0 <= xx && xx < W && 0 <= yy && yy < D) {
                if (changed[xx].count(yy)) ans -= abs(changed[xx][yy] - cur), ans += abs(changed[xx][yy] - (cur - z[i])); // 場合分け3
                else ans += z[i]; // 場合分け2
            }
            else ans -= z[i]; // 場合分け1
        }
        changed[x[i]][y[i]] = cur - z[i];
    }

    cout << ans << endl;
}

One More aab aba baa [AtCoder Beginner Contest 215 C]

https://atcoder.jp/contests/abc215/tasks/abc215_c

解説

https://atcoder.jp/contests/abc215/submissions/25247677

今回要求されている問題を実装できるかという問題となる。
前半と後半でやればいい。

文字列Sの各文字を並べ替えて作ることが可能な文字列を辞書順にすべて列挙

こっちがほぼ本質。
並び替えて作れる文字列は順列の組み合わせ数となるので、8765432*1=40320通りとなる。
これは全列挙できる個数であるので、全列挙しよう。

C++であればdo-whileとnext_permutationを使えば、簡単に並び替えて作ることができる文字列を列挙できる。
これを使わない場合はdfsとかで頑張る感じになると思う。
「順列列挙」辺りのキーワードで探せば出てくると思う。

前からK番目にくる文字列を求める

こっちは単純に前からK番目を出力するだけ。

string S; int K;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> S >> K;

    vector<string> cands;

    sort(all(S));
    do {
        cands.push_back(S);
    } while (next_permutation(all(S)));

    cout << cands[K - 1] << endl;
}

Coprime 2 [AtCoder Beginner Contest 215 D]

https://atcoder.jp/contests/abc215/tasks/abc215_d

解説

https://atcoder.jp/contests/abc215/submissions/25246926

始めてこういう系統の問題を見る人は何から手を付けていいか分からないだろう。
gcdをして1になる数は基本的には互いに素である数となる。
だが、互いに素の数というのは少し列挙するのが厄介で、逆に観点を置いて考えることが競プロでは多いように思う。
(自分的にはですけど)
逆というのは、つまり、gcdをして1にならない数はどういった数であるかを考えてみる。

gcdをして1にならない数は?

gcd(6,k)について考えると、k=2,3,4,6,8,9,10,12みたいな数が1にならない数となる。
何か規則性というか、単純に考えることができないか?
gcdの求め方を中学までさかのぼって思い出してみると、素因数分解していることを思い出す。
6の素因数は2と3であり、それを倍数がkに含まれている。
これで単純に表現できそうだ。

gcd(x,k)!=1であるようなkというのは、xを素因数分解したときの素因数のいずれかの倍数となる。

素因数分解

よって、まずは素因数分解だが、これはO(sqrt(N))でやる方法がある。
ググると以下のようなサイトが見つかったが、他にもサイトがあるかもしれない。
素因数分解-数学アルゴリズム演習ノート-
より高速なアルゴリズムもあるが、O(sqrt(N))でC++なら今回は間に合う。

自分はenumPrimeOnly関数として、少しもじって素因数だけ持ってくるような実装にしている。
以下のng配列を用意する。

ng[x] := gcd(A[i],x)!=1となるiが存在する

すると、取得した素因数pにおいて、ng[p]=trueになる。
これをすべてのA[i]について行っていこう。

倍数について

これで素因数についてはダメなものはマーキングできたが、その倍数について考慮できていない。
このために、ng[p]=trueであれば、ng[2p], ng[3p], ng[4p], ...についてもtrueに変換していく。
実装を見ればやりたいことはだいぶ明らかなのだが、これをp=2から順番にやっていき、間に合うのかが問題。
この各iについて倍数を確認していくループは有名なもので、調和級数的な計算となりO(NlogN)になる。
競技プログラミングにおけるエラトステネスの篩・区間篩・調和級数計算量問題 - はまやんはまやんはまやん

これでngテーブルが完成するので、それを使って後は答えるだけ。

int N, M, A[101010];
bool ng[101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> M;
    rep(i, 0, N) cin >> A[i];

    rep(i, 0, N) {
        auto ep = enumPrimeOnly(A[i]);
        fore(p, ep) ng[p] = true;
    }

    rep(p, 2, M) if(ng[p]) {
        for (int y = p + p; y <= M; y += p) ng[y] = true;
    }

    vector<int> ans;
    rep(x, 1, M + 1) if (!ng[x]) ans.push_back(x);

    printf("%d\n", ans.size());
    fore(x, ans) printf("%d\n", x);
}

Chain Contestant [AtCoder Beginner Contest 215 E]

https://atcoder.jp/contests/abc215/tasks/abc215_e

前提知識

解説

https://atcoder.jp/contests/abc215/submissions/25245742

この問題はbitDPの応用問題となる。
とりあえずmod数え上げなので、DPがまず第一候補として挙がってくる。
コンテストの種類ごとでまとまりになっている必要があるので、以前やり終わったコンテストは利用できないということで、
コンテストに出たか出てないかという所でbitDP感がするし、コンテストも10種類ということでかなりそれっぽい。

bitDPについては説明しないので、理解してない場合はどこかで学習してきてほしい。

DP

正直、以下のDPテーブルが作れていればほぼ回答できているようなものである。

dp[i][msk][lst] :=
i回目のコンテストまで出場するかを決定していて、
出場済みコンテストの状況がmskで、
最後に出たコンテスト種類がlstである
場合の組み合わせ

mskだけだと条件判定に必要な連続で同じコンテストに出ているかの判定ができないので、最後にどのコンテストに出たかを
状態として含める必要がある部分が特徴的だが、bitDPではよく見られる条件。

どうやってこのテーブルを出したかという部分は何とも言えないが、必要そうな

  • いつもの何回目までか
  • コンテストに出たか出ないかを持っておく必要がある
  • 条件判定には最後に出たコンテストの情報が必要

という部分をまとめ上げて、制約を確認すると問題なかったから、遷移を考えると解けたという流れになる。

遷移

dp[i][msk][lst]からの遷移で考えると、

  • コンテストに出ない dp[i][msk][lst] -> dp[i + 1][msk][lst]
  • コンテストに出る
    • 出るが、mskに含まれていてlstと違ったら出れないので遷移できない
    • そうじゃない場合は出れるので、 dp[i][msk][lst] -> dp[i + 1][msk | (1<<nxt)][nxt]

mskに状態を追加する場合は、or計算で追加すると遷移分けをしなくてもよくなるので便利。

int N; string S;
mint dp[1010][1 << 10][11];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;

    dp[0][0][10] = 1;
    rep(i, 0, N) rep(msk, 0, 1 << 10) rep(lst, 0, 11) if (dp[i][msk][lst] != 0) {
        dp[i + 1][msk][lst] += dp[i][msk][lst];
        
        int nxt = S[i] - 'A';
        if ((msk & (1 << nxt)) && lst != nxt) continue;
        dp[i + 1][msk | (1 << nxt)][nxt] += dp[i][msk][lst];
    }

    mint ans = 0;
    rep(msk, 0, 1 << 10) rep(lst, 0, 10) ans += dp[N][msk][lst];
    cout << ans << endl;
}

Dist Max 2 [AtCoder Beginner Contest 215 F]

https://atcoder.jp/contests/abc215/tasks/abc215_f

前提知識

解説

https://atcoder.jp/contests/abc215/submissions/25244049

二分探索と尺取り法の知識はこれ以降の解説を理解するのに必須であるので、
分かっていない場合は学んでくることを勧める。

まずは二分探索を思いつく必要がある。
最小値の最大値とか、その逆とかは二分探索っぽいみたいな話があるが、今回もそれにちょっと似ている感じがする。
それもあって、二分探索から考えてみると、解法にたどり着いた。
この部分がまず1つ目の山となる。

二分探索

どういった条件で考えるかというと、

check(lim) := 異なる2つの点の距離の最大値がlim以下であるか

というのを判定問題として二分探索をしていくことにする。
仮に答えが10であれば、

...
check(8) = false
check(9) = false
check(10) = true
check(11) = true
...

のようになるので、境界線の上側が答えになる。

判定条件

「異なる2つの点の距離の最大値がlim以下であるか」というのは、このままだとあまり意味のある条件には見えないような感じがする。
なので、言い換えよう。

「異なる2つの点の距離の最大値がlim以下であるか」
というのは、「全頂点間で min (xの差, yの差)≦lim を満たす」である場合に満たされることになる。
minというのはちょっと面倒なので、もう少しばらすと、
「全頂点間で xの差≦lim または yの差≦lim を満たす」
となる。

正直、高速に計算できそうなやつに寄せて作っている条件なので、あまり納得感がないかもしれない。
この判定を高速に行っていく。

2軸を1軸に

x軸とy軸でそれぞれ考えるのは大変なので、どちらかでも何とかしたいものである。
今回の点の集合は特に順番に意味はないので、ソートをしても問題ない。
あらかじめx座標でソートしておこう。
こうすることで、距離の区間に変換しやすくなる。

具体的にはとある点iについてxの差がlim以下である点を考えると、ちょうどiを含む区間になることが分かるだろう。
とある点iについて、区間[L,R)についてはxの差がlim以下であるとすると、この区間については条件を満たすことになる。
逆に[0,L)の区間と、[R,N)の区間についてはxの差がlimより大きいことになる。
つまり、この区間に含まれる点はすべてyの差がlim以下である必要がある。
なので、この区間に含まれる点において、yの差がlimより大きいものがあるかを探すことで判定関数がfalseと返すかを決めることができる。

このように片方をソートすることで、問題を区間に変換することができ、区間内ではもう片方だけを考慮するだけで良くなったりする。
平面走査と呼んでもいい(し、まんまか)。

実装

すべての点iについて区間[L, R)を特定する方法として、尺取り法を用いる。
これはLもRもiが増えていくたびに広義単調増加していくのはイメージ付くだろう。
よって、尺取り法によって高速に区間[L, R)を特定できる。

[0,L)の区間と、[R,N)の区間についてはxの差がlimより大きいものがあるかを判定する方法について考える。
y[i]と最も距離がありそうな点というのは、その区間に含まれる最小のy座標と、最大のy座標となる。
なので、その区間において、y座標の最大値と最小値が得られればいい。
自分はSparseTableを用いた。これはざっくり言うと高速なセグメントツリーである。
取得がO(1)で行える。SparseTableを用いても、O(Nlog最大値)みたいな感じでNも2*105なので、セグメントツリーのO(Nlog2N)が
ちょっと怖くて、SparseTableにした。
だが、今思えば、先頭からと末尾からの区間なので、累積和としてmin/maxを用意するだけでよさそうである。

これで2つの区間の最大値と最小値を持ってきてy[i]との距離を測ってlimを超えていれば判定関数はfalseを返す。

int N;
vector<pair<int, int>> points;
SparseTableMin<int> stmin;
SparseTableMax<int> stmax;
//---------------------------------------------------------------------------------------------------
bool check(int lim) {
    int L = 0, R = 0;
    rep(i, 0, N) {
        while (R < N && points[R].first - points[i].first <= lim) R++;
        while (lim < points[i].first - points[L].first) L++;

        int ma = max(stmax.get(0, L), stmax.get(R, N));
        if (0 <= ma && lim < abs(ma - points[i].second)) return false;

        int mi = min(stmin.get(0, L), stmin.get(R, N));
        if (mi < inf && lim < abs(mi - points[i].second)) return false;
    }

    return true;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) {
        int x, y; cin >> x >> y;
        points.push_back({ x, y });
    }
    sort(all(points));
    
    vector<int> dic;
    rep(i, 0, N) dic.push_back(points[i].second);
    stmin.init(dic);
    stmax.init(dic);

    int ng = -1, ok = inf;
    while (ng + 1 != ok) {
        int md = (ng + ok) / 2;
        if (check(md)) ok = md;
        else ng = md;
    }
    cout << ok << endl;
}

テトラへドロン [パソコン甲子園2020 予選 F]

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

解説

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

かなり複雑な問題で何から手を付けたものかという感じだと思うが、規則性を見つけていこう。

規則性

まずは、△型のタイルは少し扱いにくいし、答えるときもxy座標で答えるので例で与えられている配色を
普通のタイルに当てはめて眺めてみよう。

y=5  YGRBYGRBYGRBYGRBYGRB  
y=4  BRGYBRGYBRGYBRGYBRGY  
y=3  YGRBYGRBYGRBYGRBYGRB  
y=2  BRGYBRGYBRGYBRGYBRGY  
y=1  YGRBYGRBYGRBYGRBYGRB  
y=0  BRGYBRGYBRGYBRGYBRGY  

さて、これを見て、何か思う所がないだろうかということなのだが、ここから規則性を見つけ出せないと
解くのは難しい。
簡潔でなくても、ある程度使えそうな規則性が見つかればそれをうまく使って答えることができる。
今回自分が見つけた規則性について説明する。

規則性①

y座標の偶奇が同じものは全く同じパターンを持つ。
よって、y=0,2,4は同じような並びだし、y=1,3,5も同じような並び。
なので、y座標は2で割った余りを使ってy=0,1のどちらかに移した状態で答えてしまっていい。

y=1  YGRBYGRBYGRBYGRBYGRB  
y=0  BRGYBRGYBRGYBRGYBRGY  

規則性②

x座標に着目すると4個毎に同じパターンがどちらも連続している。
よって、x座標も4で割った余りにして考えてしまって問題ない。

y=1  YGRB YGRB YGRB YGRB YGRB  
y=0  BRGY BRGY BRGY BRGY BRGY  

みたいな感じだったのが、

y=1  YGRB  
y=0  BRGY  

だいぶ簡潔になった。
もう少し言うとy=1はy=0を左右ひっくり返した形になっているのでyの偶奇を見て、
必要ならひっくり返した状態で答えてあげればいいので、特徴点だけあえて取り出すと

y=0  BRGY  

これが連続しているような感じになる。

そして、この2つの規則性は初期の色が何であっても成り立つ性質となる。
ここまで分かれば、次に問題になるのが初期の色が2つ分かっているときにy=0のx=0..3の配色が分かれば
高速に答えが出せることになる。

初期配色

この部分を自分はgetTable関数で実装している。
ここが正直一番説明が難しい。
やり方は色々あると思う。

初期配色の組み合わせは12通りしかないので、最悪根性で書き上げてもいいが、
手動全列挙はケアレスミス紙一重であることを忘れてはいけない。
自分は多少の手間があっても全列挙部分を減らすように努力することを勧める。

自分の実装では三菱の形で色をメモっておいて特定する方法で実装した。
dic配列を手動で作って定義している。
dic[c] := 色cを中心としたときに以下のような順番で色を記録したもの

 2  
1c3  

ちょうど左下にこの図形が現れて1に当たるのがc1で、cに当たるのがc2になる。
よって、dic[c2]を使って、この配色を回転させながらc1が1になるとき、回転させてc1が2になるとき、
c1が3になるときをループで確認していって、色を探していく。
これで色が

 b  
acd  

のように特定できたら、y=0の状態に合わせるためにacdbの順番で答えてやれば目的の初期配置が得られる。

char c1, c2;
int N, x[101], y[101];
//---------------------------------------------------------------------------------------------------
string getTable() {
    map<char, string> dic;
    dic['R'] = "BYG";
    dic['G'] = "YBR";
    dic['B'] = "RGY";
    dic['Y'] = "GRB";

    string res = "";
    res += c1;
    res += c2;
    rep(i, 0, 3) if (dic[c2][i] == c1) {
        res += dic[c2][(i + 2) % 3];
        res += dic[c2][(i + 1) % 3];
    }
    return res;
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> c1 >> c2;
    cin >> N;
    rep(i, 0, N) cin >> x[i] >> y[i];

    auto table = getTable();

    rep(i, 0, N) {
        x[i] %= 4;
        
        if (y[i] % 2 == 0) cout << table[x[i]] << endl;
        else cout << table[3 - x[i]] << endl;
    }
}