競プロメモ

sankantsu

負辺を含む TSP

WF で事前に頂点間最短距離を求めておくのがポイント

デバッグ

事前に解説を読んでいたが、2 ケース WA (WA)

解説を参考に、dp の更新で inf guard を入れると通る。
直接的な原因がわからずデバッグに手間取ったが、どうやら負辺のせいで到達不能な場合でも inf よりコストが減っているように見えるケースがあるのが原因らしい。

ans のチェックを緩めると通る (AC)

sankantsu

弦がひとつでも交差しているかどうか?

円弧を無視して直線化して、今どの弦の "内側" にいるかをスタックで判定すれば解ける。

デバッグ

おおまかな方針は自力で思いついたので提出してみたが、1ケースWA (WA)

原因はこんな感じで、stack に積まれている最内の弦よりは外にいるが、それより外側の弦と交差するのをチェックしていなかったこと。

stack pop していった直後も交差をチェックするようにすると通った。(AC)

とはいえ、辺ごとに積むより解説のように頂点ごとに積んだほうがすっきりしている感じはする。(AC)

sankantsu

先頭のみ大文字、残り小文字になっているか判定するだけ

難しくはないが、最初下のようなコードを書いてしまってちょっと詰まった。

bool check = true;
rep(i,s.size()) {
    if (i == 0 && !('A' <= s[i] && s[i] <= 'Z')) {
        check = false;
    }
    else if (!('a' <= s[i] && s[i] <= 'z')) {
        check = false;
    }
}

1 文字目の判定は一個目の条件だけで十分だと思ったが、ここで通ると次の条件もチェックされてしまうので、1 文字目の判定は else if に入らないように i > 0 のチェックが要る。(AC)

sankantsu

1000 桁の掛け算の一致をどうやるか
単純な多倍長整数演算だと基本 TLE する。

代わりに、大きめの整数 (できれば素数) の mod でチェックすれば良いらしい。
解説のことばを借りれば、厳密なチェックをだいたい衝突しない hash チェックで代替するような感じ。

素数 1 個だと false positive が出るので、いくつかの素数でチェックする。
素数の密度は意外と高いので、生成はたんにランダムでいくつか数をつくって素数判定すれば OK。

実装テクニックとしては、素数複数個使う際に (1000 桁の) 整数ひとつを、素数の mod をとった vector と同一視するとやりやすい。(AC)

sankantsu

K 番目に金額が小さい買い方を求める。

1 から i - 1 番目までの買い方がわかっているとき、これらのいずれかに 1 つの商品を足したものの中に i 番目の買い方があるので、構成的に 1 から K 番目までの買い方を作っていけば良い。

最初解説を見たとき正当性の説明がなんとなくしっくりこなかったので、少し考えた。
K 番目の買い方を K-1 番目までの買い方から構成するというよりは、すべての買い方に順序がついているということを前提に考えて、「K 番目から任意の商品をひとつ外した買い方は必ず K - 1 番目以内にあるはずだから、すでに列挙した中にある」という発想で考えたほうがわかりやすいと思った。

sankantsu

1次元グリッド上をマスにかかれている数の倍数だけ左から右に進めるとき、移動方法の数を数える

基本的には左から dp で各マスへの到達方法を数えていけば良いのだが、各マスからの移動方法が最悪 $N$ 通りあるので、安直に書くと $O(N^2)$ になってしまう。
自力ではそこから改善する方法が全くもって思い浮かばなかった。

マスからの移動方法が多くなってしまうのは、マスにかかれている数字が小さいときである。この状況をうまく扱う方法を考えるのが第一歩になる。
このときは、実はマスの数字が同じものを共通化して考えることでうまく処理できる。
具体的には、今のマス $i$ から $j$ マス飛びで移動する方法の数を $S$ [ $j$ ][ $i$ ] としておくと、

$\mathrm{dp}$ [ $i$ ] += $\sum_j$ $S$ [ $j$ ][ $i$ ] (1回の移動距離としてありうる移動方法すべてについて今のマスへの到達方法としてカウントする)
$S$ [ $A_i$ ][ $i + A_i$ ] += dp[ $i$ ] ( $A_i$ マス先に今のマスから $A_i$ マス単位での移動が可能であることを記録する)
$\forall j$ $S$ [ $j$ ][ $i + j$ ] += $S$ [ $j$ ][ $i$ ] (今のマスに $j$ マス飛びで移動可能なら、今のマスから $j$ マス先にも $j$ マス飛びで移動可能である)

2, 3 番目のカウント方法は、今のマスを起点とする移動については直接的には 1 つ先で到達可能なマスだけに記録しておいて、実際にそのマスに到達してからさらにその次のマスへ遅延してカウントしているというように考えるとわかりやすかった。
この方法で dp を計算すると、マスの数字の最大値を $D$ として $O(DN)$ の計算量で計算できる。
しかし、今回の設定では $D = N$ であるから全部の移動についてこの方法で計算していたら結局 $O(N^2)$ になってしまう。

ここでもうひとひねり必要で、

大きい移動距離の移動は、各マスから先のマスへの移動方法を直接カウント
小さい移動距離の移動は、移動距離ごとにまとめて遅延カウント

というように組み合わせることで、全体の計算量を少なくできる。
$D$ 以上の移動は 1 の方法で、 $D$ 以下の移動は 2 の方法でカウントすると全体としての計算量は $O(N/D + DN)$ となり $D \sim \sqrt{N}$ にすると $O(N\sqrt{N})$ になって最適である。

区間の分割について使う平方分割は知っていたが、異なる計算量の手法を組み合わせるときも "平方分割" 的な発想が出てくるというのは新鮮に感じて、とても学びのある問題だったと思う。

sankantsu

等間隔に存在する点のうち、特定の区間内に存在するものの数を数える。

見た目は小学校の算数のようで非常に簡単そうなのだが、いざ実装しようとしてみるとマイナスの数の割り算の仕様などのせいでわかりにくい場合分けが発生して意外と面倒だった。
方針としては公式解説にあるとおり、(r 以下にある木の番号の最大値) - (l 未満にある木の番号の最大値) を求めれば良い。

結局自力で考えたのは下のような解答なのだが、正解に至るまで 30 分近く考え込んでしまった。
境界値の扱いがややこしいし、どこで -1 するかなどわかりにくくいかにも間違えそうである (実際 1 回境界値の扱いを間違えて WA を吐いた)。

int main() {
    long a, m, l, r;
    cin >> a >> m >> l >> r;

    long k1 = (a < l) ? (l - 1 - a)/m : (a - l)/m*(-1) - 1;
    long k2 = (a <= r) ? (r - a)/m : (a - r - 1)/m*(-1) - 1;
    cout << k2 - k1 << endl;
}

求めたい値が、floor 関数として表現できることに気づくと、少し見通しがよくなる。
公式解説によれば、有理数に対する floor 関数は以下のように実現できるらしい。

// floor(a/b) を計算する。(b > 0)
long floor_rational(long a, long b) {
    long r = (a % b + b) % b;  // a ÷ b のあまり (0 <= r < b)
    return (a - r)/b;
}

マイナス値に対する % 演算がマイナス値を返す仕様のためにあまりの計算が少しややこしいが、このあたりは idiom として身につけてしまうか、ライブラリ化しておくのが良さそうである。
この関数を使うと、floor_rational(r - a, m) - floor_rational(l - 1 - a, m) で答えが計算できる。