所感

500も結構自力ACできる

問題概要

0と1からなる文字列Sが与えられる。以下の操作を繰り返してSの要素をすべて0にできるような最大の整数Kを求めよ。

長さK以上の区間を選択し、0と1を反転させる。

取った方針

Sの長さ|S| をLとおく。
手元で実験をすると、左右L - K 個の数は任意にできることがわかる。(理由:K + 1個の区間を反転させてから任意にしたい場所以外のK個を反転させればよい)
残った2K-L 個の値は一度に反転させられなければならないので、すべて同じ数である必要がある。
すべて同じ数であるかどうかはO(L)で判定できるので、Kを二分探索すればO(LlogL)で解ける。

正しい方針

左右L - K 個の数は任意にできることはそのまま用いる。
0と1の変化点に注目すると、上記の方法で変化点をひとつづつ潰すことができるので、端から一番近い変化点を潰せるKを選択する。

得られた知見

・めぐる式二分探索
・区間を反転させる -> 自由にできる(できない)場所に注目

解くのに必要な要素

・区間を反転させる -> 自由にできる(できない)場所に注目

周辺調査によって得られた知見

特になし

2019-07-10

ABC133 E Virus Tree 2

所感

Cはカス

問題概要

木と数Kが与えられる。イカの条件で色を塗り分けるとき、塗り分け方の個数を求めよ。

二つの異なる頂点 x,y 間の距離が2以下ならば、頂点xの色と頂点yの色は異なる。

取った方針

あるノードに注目した時、距離が2以下である、とは、以下のノードの色が違えばよい。
- 親
- 親の親
- 兄弟(同じ親の子)
深さが2以下のノードにおいて、親と親の親はそれぞれ1つずつ存在するので(理由: 木なので)、親が同じノードにK-2, K-3...と順番に数を振っていくとそれはそのノードに塗れる色の個数になる。深さが1の時はK-1, K-2...と振ることに注意する。(親の親がいないので)
最後にそれらをすべて掛ければOK

正しい方針(解説の方針)

私はBFS で解説はDFS だけど使っている事実は同じ

得られた知見

・木において距離が2 -> 親の親 or 同じ親の子
・Cはカス

解くのに必要な要素

・BFS/DFS
・Cをバグらせないこと

周辺調査によって得られた知見

特になし

2019-07-01

ABC129 E - Sum Equals Xor

所感

0b1000 < 0b0111、言われてみれば死ぬほど当たり前なんだけど上から桁DP + 二進数で見えなくなっていたよね(言い訳)

atcoder.jp

問題概要

正整数Lが二進数表記で与えられる。
a + b <= L
a + b = a ^ b
なる(a, b)の組み合わせの個数を10⁹+7で割った余りを求めよ。

取った方針

a + b == a ^ b なるa + bを列挙して何かしらの法則性を見つけようとして死亡

正しい方針(解説の方針)

xor は繰り上がりのない二進数の足し算という情報系知識がある。
つまり、繰り上がりのない足し算(k桁目の値が両方1ではない)ならa + b == a ^ b となる。
これを考えつつ桁DPをする。(桁数が非常に多いこと、桁に関する条件があることから思いつく。)

dp1[i] := 上からi桁目まで確定していて、既にa + b < Lが確定している場合の数
dp2[i] := 上からi桁目まで確定していて、まだa + b < Lが確定していない場合の数
i桁目の時点でa + b < L が確定している ⇔
以降の値がすべて1になったとしてもa + b < Lである ⇔
i桁目までにL[k] == 1 && bin(a + b)[k] (binは数を受け取って二進数文字列を返す関数)なるkが存在するであることに気を付けて遷移を考えると、遷移はイカになる。i桁目を0にするには(0, 0)の1通り、1にするには(0, 1), (1, 1)の2通りがあることに気を付ける。

if (s[i] == '1') {
    //既にa+b<Lの場合は任意
    dp1[i] += dp1[i - 1] * 3;
    //a+bを0にする
    //Lのi番目が1でa+bのi番目が0のとき、 a + b < L  が確定する
    dp1[i] += dp2[i - 1];
    //1にする
    dp2[i] += dp2[i - 1] * 2;
}
else {
    //既にa+b<Lの場合は任意
    dp1[i] += dp1[i - 1] * 3;
    //a+bを0にするしかない
    dp2[i] += dp2[i - 1];
}

得られた知見

・桁数が大きい + 桁に関する条件 =>桁DP
・xor は繰り上がりのない二進数の足し算
・桁DP に詳しい記事:

drken1215.hatenablog.com

解くのに必要な要素

・xor は繰り上がりのない二進数の足し算(知識)
・桁 DP ・桁 DP に関連して、xの中身が何であったとしても8000 > 7xxx であるという当たり前の感覚

周辺調査によって得られた知見

特になし

2019-06-27

ABC128 E Roadwork

所感

やむと゛ぅはちえんセク゛きをてにいれた！
やむと゛ぅはさ゛あつをてにいれた！

問題概要

N個の道路工事とQ人の人間が与えられる。道路工事はS, T, Xの形で与えられ、それぞれS-0.5 からT-0.5 の時間座標Xを道路工事し通行止めにすることを表す。
人間はdの形で与えられ、時刻dに座標 0を出発し速度1で正方向に歩く。
人間が道路工事に出会うまで歩くとき、各人間の歩く距離を求めよ。

取った方針

横軸t(時間)、縦軸x(座標)なるダイヤグラムを書くと、Q本の直線とN本の直線の交点のうちxがもっとも小さいものを求める問題になります。
もう少し考察すると、(S, T, X)で表される工事はdが[S-X, T-X)に含まれる人間にのみ影響することがわかるので、t軸において、N個の区間とそれに対応する値xが与えられ、座標dを被覆する区間[S-X, T-X)に対応するXの最小値を求める問題になります。
これは確かにセグ木で殴れそうですが区間更新ができることを知らず死亡

解いた方針

セグ木は遅延評価をすると区間更新ができるようになることが知られています。
セグ木の概念をグラフィカルに理解するならここ
http://tsutaj.hatenablog.com/entry/2017/03/29/204841
遅延セグ木の概念をグラフィカルに理解するならここ
http://tsutaj.hatenablog.com/entry/2017/03/29/204841
遅延セグ木を一般化するならここ
http://beet-aizu.hatenablog.com/entry/2017/12/01/225955
がよくて、最後の天才さんのライブラリを使いました。
理解するためにめちゃめちゃコメントを付けたので貼っておきます。

//出典 http://beet-aizu.hatenablog.com/entry/2017/12/01/225955

template <typename T, typename E>
struct SegmentTree {
    typedef function<T(T, T)> F;
    typedef function<T(T, E)> G;
    typedef function<E(E, E)> H;
    typedef function<E(E, int)> P;
    int n;
    F f;
    G g;
    H h;
    P p;
    T d1;
    E d0;
    vector<T> dat;
    vector<E> laz;
    SegmentTree(int n_, F f, G g, H h, T d1, E d0,
        vector<T> v = vector<T>(), P p = [](E a, int b) {return a; }) :
        f(f), g(g), h(h), d1(d1), d0(d0), p(p) {
        init(n_);
        if (n_ == (int)v.size()) build(n_, v);
    }
    //初期化。要素配列と遅延配列を2*n-1個にする
    void init(int n_) {
        n = 1;
        while (n<n_) n *= 2;
        dat.clear();
        dat.resize(2 * n - 1, d1);
        laz.clear();
        laz.resize(2 * n - 1, d0);
    }
    //既存のvectorからセグ木を構築
    void build(int n_, vector<T> v) {
        for (int i = 0; i<n_; i++) dat[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            dat[i] = f(dat[i * 2 + 1], dat[i * 2 + 2]);
    }
    //ノードを評価する。
    inline void eval(int len, int k) {
        //遅延配列に単位元が入ってたら評価済みなのでおしまい
        if (laz[k] == d0) return;
        //葉ノードでないなら遅延伝播する
        if (k * 2 + 1<n * 2 - 1) {
            //h: 2つの作用素を引数に取り合成した作用素を返す関数
            laz[k * 2 + 1] = h(laz[k * 2 + 1], laz[k]);
            laz[k * 2 + 2] = h(laz[k * 2 + 2], laz[k]);
        }
        //p: このノードに対応する区間長と作用素を引数に取り、区間長に対応する作用素を返す関数
        //dat[k] にlaz に溜めていた作用素を適用(g: 要素型と作用素型を引数に取り、要素に作用素を作用させた結果を返す関数、ここでの作用素とは区間Sum区間Addなら (+ 3) とか)
        dat[k] = g(dat[k], p(laz[k], len));
        //適用し終わったので遅延配列をクリア
        laz[k] = d0;
    }
    //[l,r)の区間を再帰的に見ながら0-indexedの[a, b)を更新する
    T update(int a, int b, E x, int k, int l, int r) {
        //先に評価
        eval(r - l, k);
        //範囲外ならなにもしないでそのノードが持つ値を返す
        if (r <= a || b <= l) return dat[k];
        //完全被覆なら既に遅延配列に入っている作用素と追加したい作用素をマージした後にそれを要素に作用させた結果を返す、pは区間長に対応する作用素を得るための（ｒｙ
        if (a <= l && r <= b) {
            laz[k] = h(laz[k], x);
            return g(dat[k], p(laz[k], r - l));
        }
        //完全被覆でも範囲外でもないなら(中途半端にかぶっているなら)完全被覆と範囲外の境界が見えるまで木を潜って変化後の値を得る
        return dat[k] = f(update(a, b, x, k * 2 + 1, l, (l + r) / 2),
            update(a, b, x, k * 2 + 2, (l + r) / 2, r));
    }
    T update(int a, int b, E x) {
        return update(a, b, x, 0, 0, n);
    }
    T query(int a, int b, int k, int l, int r) {
        eval(r - l, k);
        //範囲外なら単位元を返す
        if (r <= a || b <= l) return d1;
        //完全被覆ならそのまま返す
        if (a <= l && r <= b) return dat[k];
        //一部被覆なら完全被覆と範囲外に分かれるまで木を潜る
        T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
        T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
        return f(vl, vr);
    }
    //0-indexedで[a, b)の区間*を求める
    T query(int a, int b) {
        return query(a, b, 0, 0, n);
    }
};

抽象的な数学が書いてあってウワッとなるけど俺は頭がいいからわかるんだという気持ちで読むとわかる
一番難しいのは作用素のマージとかいう概念ですが、遅延配列lazに入っているのは値ではなく作用素(関数みたいなもの(まさかりを投げるな))が入っていて、新たにそのノードに作用素を作用させたくなったら溜まっている関数と合成するのじゃ、と考えると飲み込みやすい気がします
コンストラクタ引数でセグ木で使う演算を注入できて、それぞれ
int n_ 要素数。
f 2つの要素Tをマージするための関数。
g 1つの要素Tに作用素Eを適用するための関数。
h 2つの作用素Eをマージするための関数。
T d1 演算fの単位元。
E d0, g, hの単位元。
vector v セグ木を構成するときのvector
P p 区間の長さbを引数に取り、区間の長さによって変化する作用素E'を返す関数。
であるので、今回は更新クエリがchmin で区間最小が知りたいので以下になります。
f: min
g: min
h: min
d1: INT_MAX
d0: INT_MAX
p : {return a; }(適用すべき作用素は区間の長さによらない)

これを用意すると区間chminクエリを処理したのち区間最小が求められるので、言い換えた問題が解けます。
ただし、tの範囲が10⁹と広いので、このままセグ木を作るとMLEするので座標圧縮をします。

正しい方針(解説の方針)

問題を言い換えるところまでは同じ、imos法っぽく始点と終点に注目して、始点でsetにxを追加、終点でsetからxを削除、って感じのことをする。
時刻d以下のクエリを消費し終わった時のsetの最小値が答え

得られた知見

・セグ木の一般化(作用素のマージ)
・座標圧縮
・ダイヤグラム->絵を描く

解くのに必要な要素

・セグ木 + 座標圧縮
・もしくはimos法っぽいアレ

周辺調査によって得られた知見

・得られた知見に包含される

2019-06-20

ABC127 Cell Distance

所感

思ったより簡単だったし本番中解けてもよかったね

問題概要

N行M列の盤面にK個のコマを置くことを考える。
配置のコストをすべての盤面上のコマ同士のマンハッタン距離で定義するとき、すべての置き方のコストの総和を求めよ。

取った方針

コマを置く2箇所を定めた時、残りのコマの置き方はBinom(NM-2, K-2) (Binomは二項係数)通り。
よって、そのコストをcと置くと、 c * Binom(NM-2, K-2)のコストがかかる。
よって、すべてのマス(x, y) について、残りのすべてのマスに対するマンハッタン距離の和sumを計算し、sum * Binom(N*M-2, K-2) の和を計算し、最後に2で割ったもの(この数え方では同じ組を二回数えることになるので) が答えになる。

1マスを決めたときの残りのすべてのマスに対するマンハッタン距離の和はx方向とy方向を独立に考えることで等差数列の和からO(1)で求まる。

例えば、以下の盤面で(1, 1)から他のマスへのマンハッタン距離の総和を求めることを考えます。0-indexedです

各行のマンハッタン距離のx成分の和は1+0+1+2 で4です。
これはSum(0, 1) + Sum(0, 2)で表せます。(Sum(First, Last) は初項First, 末項Last, 公差1の等差数列の和です。)
これが4行分あるので、

(Sum(0, 1) + Sum(0, 2)) * 4

です。
同様にy成分も計算できます。結果、H * Wの盤面上で(x, y) から任意の他のマスへのマンハッタン距離の和はイカで表せ、O(1)で計算できます。

Sum(0, y) + sum(0, H - y - 1) * W + (Sum(0, x) * Sum(0, W - x - 1)) * H

マンハッタン距離を考えるときx軸方向とy軸方向を独立に考えることは典型らしいです。。。。

正しい方針

解説の方針はマンハッタン距離のx成分y成分それぞれがdである場合の数を数えているけどまあやってることは同じでしょう

得られた知見

・マンハッタン距離 -> x y 独立に考えるとよい

解くのに必要な要素

・平面を見たらx y 独立に考える奴

周辺調査によって得られた知見

・マンハッタン距離の和を最小にする値は中央値
・http://kagamiz.hatenablog.com/entry/2014/12/21/213931

2019-05-15

ABC113 D Number of Amidakuji

言い訳

codevsたのしかったです

例の表

https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0

所見

一発で思いついたぞヤッホーと思っていたら既に解いた問題だった(は？)

問題概要

https://atcoder.jp/contests/abc113/submissions/5408429
特定条件をみたす「正しいあみだくじ」のうち、左から1番目の線から始めた時左からK番目の線に到達するものの個数を1000000007で割った余りを求めよ。

取った方針

直線がW <= 8本しかないので、1行について全探索ができる。
y行目のx列目(0 origin)にいる場合の数をdp[y][x] とおくと、x-1番目の間(0 origin) に直線があるときdp[y+1][x-1] += dp[y][x]、x番目の間に直線があるときdp[y+1][x+1] += dp[y][x]、両方に直線がない時dp[y+1][x] += dp[y][x] のようなDPができる。
dp[H][K] が答え。

正しい方針

同上

得られた知見

m次元->1次元 x mにしてO(N^m)をO(Nm)にするテク(頻出っぽい)
- 独立に考えてもいいものは独立に考える
場合の数 -> 纏められる状態(今回はy行x列に到達するあみだくじの数)を纏めて考える

解くのに必要な要素

独立に考えてもいいものを独立に考える -> DP

周辺調査によって得られた知見

特になし

2019-04-11

ABC008 コイン

abc008.contest.atcoder.jp

例の表

https://docs.google.com/spreadsheets/d/1nXQpWJ7fddnfDNqcdBumj2WzCbIy_H06upI6R-qkI/edit#gid=0

所感

最初から俺はさんすうだぞみたいな顏をしてくれれば解ける

問題概要

N枚の区別できるコインが与えられる。各コインには整数が書かれている。以下の操作を行ったとき、表向きになっているコインの期待値を求めよ。
1. すべてのコインを表向きにする。
2. 左端のコインから順に、現在見ているコインよりも右側 (それ自身を除く) にあるコインのうち、現在見ているコインに書かれている整数の倍数が書かれているコインすべての裏表をひっくり返す。

取った方針

期待値の線形性より、各場所にある各コインが表になっている確率を求めてそれの総和を取ればよい。
コインCが場所iにあるときそれが表になる確率をP[C][i] とおくと、それは以下のように求められる。
Cの左に置く約数の選び方 * Cの左に約数を置く場所の場合の数 * Cの左に置く約数の並べ方 * jの右に約数を置く場合の数 * jの右に置く約数の並べ方 * Cの約数ではない数の並べ方
これを求めて総和を取ると解になる。

正しい方針

興味があるのはCとCの約数となる数であることを考えると表になっている確率はより簡単に求められる。
Cとその約数である数のみを並べることを考えると、Cの約数がS個あったとして、左から1...S+1番目にCがある場合の数はすべて等しい。
つまり、Cとその約数のみの列を並べ変えたときCの左に偶数個並ぶ確率を求めればよく、Sが奇数なら1/2、Sが偶数なら(S+2)/(2S+2) となるので、その総和を求めればOK

得られた知見

・期待値の線形性
・興味のあるもの以外を省くと見通しがよくなるパターン

解くのに必要な要素

・期待値の線形性

周辺調査によって得られた知見

特になし