CodeChef May Lunchtime Interactive MST

問題リンク

www.codechef.com

概要、制約、解法

省略。

解が存在する条件

グラフに橋が存在する場合、どのように全域木をとっても必ず橋が含まれる。

この問題では、異なる橋を区別することができない。 そのため、グラフに橋が2つ以上あれば不可能。

逆にそれ以外なら必ず可能である。

 w=\left\{1,2,3,\dots, m-1,m\right\}として、それをシフトしつつaskすればいい。

なぜクエリの値をシフトすれば解けるのか?

値がシフトしたのではなく、コスト最大の辺が最小になったと考えるとわかりやすい。

コスト最小の辺、ここではコスト1の辺は必ず最小全域木を構成する辺に含まれる。

また、その辺が橋でない限りはコストmの辺が最小全域木に含まれることはない。

これらはプリム法、クラスカル法から導き出せる。

逆に、コスト1の辺は必ず最小全域木に含まれる。

よって、それぞれの辺eのコストがmのときのクエリと1のときのクエリの応答を比較すればよい。

これらの応答をそれぞれ X, Yとすると、 Yに含まれていて、Xに含まれていない要素がeである。

このような要素は1つしかない。なぜならその他の辺の相対的なコストは変わらず、また、同じコストの辺が存在しないからである。 (これもプリム法、クラスカル法の仕組みを考えたら理解しやすい)

WAしたときの心構え&コンテスト本番でやらかしたミス集

自分用メモ

1人でも救われる人がいるかもしれないので公開

随時追加...はしたくないけど、やらかし次第追加

WAしたときの心構え

REとTLEはわからん

提出前

1つくらいはテストケースを自作

コーナーケース、特にn=1,2

解法の正当性は?

コーディングしながら考えない、考えてからコーディングする

1WA

深呼吸

初手方針にこだわりすぎない

途中まで書いたコードを消さない、コメントアウトする

方針を変更したとしてもその正当性の証明と、初手方針のhackケースを見つけるまではコーディングしない(初手方針のhackから原因究明できる?)

解法がおかしい?コードのバグ?片方に固着しない、両方を交互に考慮する

3WA

その問題は保留で次に進む

おそらく誤読or誤解(特に英語コンテスト)

出力形式を満たしている?(Yes/No、出力行数、特にコーナーケース)

0TLEならば、明らかな論理エラーがあるとは考えにくい?

5WA

n=3くらいのサンプルを全部試す、これで気づけるはず?

サンプルが弱いor偏っているため偶然一致しているだけの可能性

WA for Pretest 5とかならnは小さいはず?

明らかに解いている人数が多い場合は誤読

変なミスまとめ

誤読

anyをmaxと誤解

(a_i, b_p_i)と(a_p_i, b_i)が逆(サンプルが偶然一致)

ハミルトン閉路を解こうとした(NP完全)

intを集合としてソートするときはpopcountで比較

オイラーツアーの配列の要素A[i]と頂点iは別

論理エラー

幾何、3点の直線判定

バグ

+と*

コーナーケースでのYes/No忘れ

出力行数忘れ

ifとwhile

TCO 2021 Round 2A Hard TwoPolarStations

easyが意味不明だった回。意味わからなさ過ぎて面白いので必見。 hardはARCで出てきそうな数え上げ。

問題リンク

community.topcoder.com

概要

図で見たほうがわかりやすいと思う。この場合n=6, k=3である。

f:id:tabr:20210523043142p:plain

上図のような頂点数n+2、辺数2n+1のグラフが与えられるので、ありうる全域木の個数を数え上げる。 厳密に述べると、

  • 頂点0からn-1はループになっている。
  • 頂点0からkまでがnと繋がっている。
  • 頂点k+1からn-1までがn+1と繋がっている。
  • 頂点nn+1も繋がっている。

制約

  •  k \leq n \leq 10^{9}

考察・解法

nn+1との間の辺を使用するかどうかで場合分けする。

使用しない場合

f:id:tabr:20210523045233p:plain

上図のように、2つのグラフにわける。 頂点0\ ~\ k,\ nとの全域木のありうる組み合わせ数をX_nとし、 頂点i\ ~\ k,\ nとの全域木のありうる組み合わせ数をY_nとする。

ただしYの場合、頂点0\ ~\ i-1は一直線につなぐ。こうすることで2つの連結成分に分解できる。X_{n+1}も同様に定義する。

つぎに、2つにわけたグラフを繋ぐ。  Y_nY_{n+1}との場合では残り辺数が不足しているため、全域木を構成することはできない。 しかしそれ以外の場合は常に可能で、対称性を考慮すると、求める値は (X_n \times X_{n+1} + X_n \times Y_{n+1} + Y_n \times X_{n+1})\times 2である。

使用する場合

f:id:tabr:20210523044045p:plain

実質的に上図のようなグラフに帰着できる。さらに、0n-1を繋ぐかどうかでも場合分けする。 繋がない場合はX_n、繋ぐ場合はY_n\times 2になる。

XYの数え上げ

O(n)のdpに帰着できる。これを行列累乗で高速化する。以下のコードを参照。pairのfirstがX、secondがY

pair<mint, mint> calc(int n) {
    if (n == 0) {
        return {0, 0};
    }
    matrix<mint> m(2);
    m[0][0] = m[1][0] = m[0][1] = 1;
    m[1][1] = 2;
    m = power(m, n - 1);
    return {m[1][0] + m[1][1], m[0][0] + m[0][1] - 1};
}

struct TwoPolarStations {
    int count(int n, int lo, int hi) {
        int k = hi - lo + 1;
        mint res = 0;
        auto p = calc(n - k), q = calc(k);
        res += p.first * q.first + p.first * q.second + p.second * q.first;
        res *= 2;
        auto r = calc(n);
        res += r.first + r.second * 2;
        return (int)res.value;
    }
};

実験するとフィボナッチ数が出てくるのでうまく公式化(O(1)解法)できそう?

Google Code Jam 2021 Round2 D - Retiling

問題リンク

codingcompetitions.withgoogle.com

概要

'M''G'の2色に塗り分けられた H \times Wのタイルが、初期状態 Xと完成形Yの2通り与えられる。 できるだけ低コストでタイルを塗り替えたい。 可能な操作は以下の通り。

  • コストFでタイルの色を変更する。
  • コストSで隣接するタイルをスワップする。

制約

  •  H, W \leq 10
  •  F, S \leq 10^{6}

考察・解法

X[i][j] == 'M' && Y[i][j] == 'G'を満たす場所の個数をAX[i][j] == 'G' && Y[i][j] == 'M'を満たす場所の個数をBとする。 また、X[i][j] == 'M' && Y[i][j] == 'G'を満たす場所をAの場所と呼ぶことにする。 考察を進めると以下のことがわかる。

  • 2つの隣接するとは限らないタイルの交換は、それらのマンハッタン距離をdとすると、 \min(2 \times F, d \times S)で行える。

  • 上記の交換は同じ色のタイルに適用する必要はない。

  •  |A-B|箇所のタイルが交換できずに余るので追加のコスト |A-B| \times Fが必要である。

これらの事実に気づけると初期状態と完成形の2部グラフ上の最小費用流に帰着できる。

for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        if (x[i][j] != y[i][j]) {
            if (x[i][j] == 'M') {
                fg.add(source, i * w + j, 1, 0);
            } else {
                fg.add(h * w + i * w + j, sink, 1, 0);
            }
        }
    }
}
for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
        if (x[i][j] != 'M' && y[i][j] != 'G') {
            continue;
        }
        for (int k = 0; k < h; k++) {
            for (int l = 0; l < w; l++) {
                if (x[k][l] != 'G' && y[k][l] != 'M') {
                    continue;
                }
                long long cost = abs(i - k) + abs(j - l);
                cost *= s;
                cost = min(cost, 2 * f);
                fg.add(i * w + j, h * w + k * w + l, 1, cost);
            }
        }
    }
}

なぜ \min(2 \times F, d \times S)で交換が可能か?

2つのタイルの色を変更することで実質的にタイルを"交換"したとみなせる。 そのため 2\times Fで交換可能といえる。 また、タイルの交換はちょうどd回のスワップで行える。 これは、例えばMGMMGGGMGGGMMGGGMMにするのに必要な回数を実験する、といった方法で予想できる。 TODO? 厳密な証明