2022-07-28

AtCoder Beginner Contest 261 参加記録

コンテスト中AC:A〜F

D - Flipping and Bonus
E - Many Operations
F - Sorting Color Balls

D - Flipping and Bonus

説明のため、お金をスコア、コイントスによって表か裏かを選んでスコアを得ることを操作と呼びます。

その時々の操作後のスコアを最大化するような貪欲法は使えません。
そこで、操作回数とカウンタの最大値が $N\leq 3000$ であり、小さいことから、DPできないか考えます。

$dp[i][j]:=$ $i$ 回目の操作終了後にカウンタが $j$ の時のスコアの最大値

このDPテーブルの大きさ(状態数)は $N^2 \leq 9\times 10^6$ となり十分小さいです。

次に $dp[i][j]$ への遷移を考えますが、その前にカウンタで得られるスコアについて、次のようにしておきます。

カウンタが $x$ の時のスコアを $D_x$ とする。なお、 $x$ が $C_1,\ \cdots C_M$ に含まれていない場合は、 $D_x=0$ とする。

$j\geq 1$
$i-1$ 回目終了後にカウンタが $j-1$ の状態であって、 $i$ 回目にカウンタを $+1$ する操作(コイントスが表)となった場合に遷移します。この時、スコアとして $X_i$ と $D_{j}$ が加算されます。
$dp[i][j] \leftarrow dp[i-1][j-1]+X_i + D_j$
$j=0$
カウンタが0の場合は、 $i$ 回目でカウンタを $0$ にする操作をした時です。 $i-1$ 回目のカウンタの状態に関わらず遷移するので、 $i-1$ 回目のスコアの最大値となります。
$dp[i][j] \leftarrow max(dp[i-1][0],\ dp[i-1][1],\ \cdots ,\ dp[i-1][N])$

$j=0$ の時に $N$ 回、 $1\leq j \leq N$ の時に各 $1$ 回ずつの計算が必要となるため、 $i=1,2,\cdots ,N$ と更新していった時、各 $i$ について、 $2N-1$ 回の計算が必要となります。従って、遷移にかかる計算量は $O(N^2)$ です。
( $1\leq j \leq N$ の計算の際にmax値を同時に計算していけば、定数倍軽くなると予想されます。)

よって、計算量も問題なく、DPで解けることがわかりました。
Submission #33455701 - AtCoder Beginner Contest 261

E - Many Operations

ビット演算の問題は、2進数の各桁毎に考えるのが典型です。

非負整数 $S$ の2進数表記の $d$ 桁目を $S^d$ と表すことにします。

非負整数 $X$ に対して操作 $1$ から操作 $3$ までを実行した場合を例に考えます。
操作1,2,3はそれぞれ $and,\ or,\ xor$ であったします。また、求めたい値を $Y_3$ とします。
つまり、

$Y_3 = ((X\ and\ A_1)\ or\ A_2)\ xor\ A_3$

です。
ここで、 $d$ 桁目のみに着目しても以下が成り立ちます。

$Y_3^d = ((X^d\ and\ A_1^d)\ or\ A_2^d)\ xor\ A_3^d$

2進数の桁は $0$ か $1$ しかありません。
そこで、

$B_3^d = ((0\ and\ A_1^d)\ or\ A_2^d)\ xor\ A_3^d$
$C_3^d = ((1\ and\ A_1^d)\ or\ A_2^d)\ xor\ A_3^d$

という風に予め計算しておくと、 $X^d$ が0か1かを判定することで、 $O(1)$ で $Y_3^d$ が求められます。
各桁について同様に求めることで、 $Y_3$ を構築できます。 $0\leq d \lt 30$ という制約があるため、高々30回の計算で済みます。

また、 $B_3^d,\ C_3^d$ は $B_2^d,\ C_2^d$ から以下の様に求められます。

$B_3^d = B_2^d\ xor\ A_3^d$
$C_3^d = C_2^d\ xor\ A_3^d$

これは操作3に限らず、一般の $i$ について、 $i-1$ の値から $i$ の値を求めることができます。

実装では、2進数表記で、00...0、11...1から始めて、順に $A_i$ とビット演算していきました。
このようにすれば、実装は少しシンプルになるのかなと思います。
詳細は実装を参照ください。
Submission #33463754 - AtCoder Beginner Contest 261

F - Sorting Color Balls

隣合う要素を入れ替えてソートするのはバブルソートです。バブルソートの最小交換回数は反転数に等しいです。そこで、反転数を軸にこの問題を考えます。

まず、色がない場合を考えます。
$i$ より前にあって、 $X_i$ より大きいものは自分より後ろに来なければいけないので、必ず $X_i$ と入れ替えなければいけません。
よって、その数を $c_i$ とすると、少なくとも $c_1+c_2+\cdots +c_N$ のコストがかかります。
これがコストの下界となります。コンテスト中は具体的な証明が思い浮かばなかったのですが、バブルソートの最小交換回数と反転数が等しいことから、実際にこれを達成できるはずと考えました。

次に、この考え方に従って、色がある場合を考えます。
$i$ より前にあって、 $X_i$ より大きいものでも、色が等しいものは交換にかかるコストが $0$ なので、無視できそうです。
そこで、 $i$ より前にあって、 $X_i$ より大きいものであり、かつ、色が異なるものの個数を $d_i$ とすると、少なくとも $d_1+d_2+\cdots +d_N$ のコストがかかると予想できます。

これが色を考慮した場合のコストの下界となります。具体的な証明はコンテスト中は浮かばなかったのですが、色が異なる場合と同様の操作をして、同色の分のコストを無視すれば良いだけなので、同様にこれが達成できるだろうと考えました。

結果として、この考え方は正しかったです。
おそらくこの証明は、Web解説やyoutube解説で示されているのかなと思います。

後は反転数の計算ですが、各色に対し、自分と異なる色のみの反転数を求めるのは難しいと考えました。
そこで、全体の反転数を求めた後、各色の反転数を引くことで求めました。
全体の反転数はFenwick Treeで求めました。
各色の反転数については、全色分のFenwick Treeの領域を確保するのが難しそうだったので、色ごとに $X_i$ を分類した後、分割統治法で求めました。

実装はコンテスト後に修正したものです。
Submission #33567025 - AtCoder Beginner Contest 261

2022-07-23

AtCoder Biginner Contest 260 F - Find 4-cycle

グラフ ABC コンテスト後鳩の巣原理

コンテスト後に自力ACしましたが、記事を書いていて計算量の見積もりが誤っていたので、公式解説を読みました。

頂点集合 $U,V$ を以下の通りとします。

$U = \{1,\ 2,\ \cdots ,\ S\}$
$V = \{S+1,\ S+2,\ \cdots ,\ S+T\}$

$U,V$ は独立集合であるという条件から、4-cycleをもつ条件は以下に限定されます。

$U$ に属するある頂点 $u_i,u_j$ と、 $V$ に属するある頂点 $v_k,v_l$ であって、 $u_i,u_j$ のいずれも $v_k,v_l$ の両方に辺がある

そこで、

$U$ に属する頂点 $u_i$ が、頂点 $V$ に属する2つの頂点 $v_j, v_k$ の両方と辺を持つ

という場合に、それを

$u_i$ が頂点対 $(v_i, v_j)$ を持つ

という風に表現したとき、4-cycleを探すという問題は、

$U$ から共通の頂点対を持つ2つを見つける

という問題に言い換えられます。

そこで、以下のような解法が考えられます。

$i=1,\ 2,\ \cdots ,\ S$ について、以下を行う。

$u_i$ と繋がる頂点を $v_1,\ v_2,\ \cdots ,\ v_{m_i}$ とする。
ここから得られる全ての頂点対 $(v_j,v_k)$ について、 $u_i$ が持っているということを記録していく。ここで、既に別の $u_x$ が、頂点対 $(v_j,v_k)$ を持っていた場合、 $(u_x,u_i,v_j,v_k)$ を答えとして出力する。

これでACしましたが、問題を解いた後に上記の部分の計算量の見積もりが誤りだったと気づきました。公式解説を見たところ、鳩の巣原理により $O(T^2)$ となることがわかりました。

これは、 $(v_i,v_j)$ という組は高々 $T^2$ 個しかないので、頂点対を調べていくと、高々 $T^2 + 1$ 回で既に一度調べた頂点対が現れる、ということです。

細かい実装の話に移りますが、C++で頂点対をpairとして、mapに記録する方法だとTLEしました。
二次元配列に記録していく方法だと、ACできました。配列として持てる場合は、mapは使用しない方が良さそうです。

Submission #33385373 - AtCoder Beginner Contest 260

2022-07-20

AtCoder Biginner Contest 260 参加記録

ABC Union-Find

コンテスト中AC:A〜D

B - Better Students Are Needed!
C - Changing Jewels
D - Draw Your Cards

B - Better Students Are Needed!

配列 $P,Q,R$ を用意し、各要素は以下のようにします。
$P_i = (A_i ,\ -i)$
$Q_i = (B_i ,\ -i)$
$R_i = (A_i+B_i ,\ -i)$

この配列は例えば、C++ならvector<pair< long long, long long >>を使用します。

$P,Q,R$ について、各要素の1つ目を第一キーに、2つ目を第二キーとして降順ソートすると、
得点の大きいものが前に来て、同じ得点なら $i$ の小さいものが前に来ます。

このように、第一キーと第二キーで昇順・降順が異なるようにソートしたい場合、一方を負にしておけば、ソート1回でこの並び方を実現できます。

後は、同じ値を2回取らないように配列に記録するなどしながら、問題文の通り、

$P$ の前から $X$ 個
$Q$ の前から $Y$ 個
$R$ の前から $Z$ 個

を合格にしていけば良いです。

計算量はソートがボトルネックとなって、 $O(NlogN)$ だと思います。

Submission #33302936 - AtCoder Beginner Contest 260

C - Changing Jewels

レベル $i$ の赤い宝石を $a$ 個、青い宝石を $b$ 個持っていたとします。
ここで、次の様に操作します。

レベル $i$ の赤い宝石 $a$ 個から、レベル $i-1$ の赤い宝石 $a$ 個と、レベル $i$ の青い宝石を $aX$ 個得る。
レベル $i$ の青い宝石 $b+aX$ 個から、レベル $i-1$ の赤い宝石 $b+aX$ 個と、レベル $i-1$ の青い宝石を $(b+aX)Y$ 個得る。

この一連の操作を1回の操作と考えると、操作1回でレベル $i$ の宝石からレベル $i-1$ の宝石を得ます。この操作を $N-1$ 回すれば、レベル $N$ の宝石は全てレベル $1$ になります。

実装では、前述した2つの変数 $a,b$ のみを持っていればよいです。操作一回での具体的な更新方法を示します。

$b\leftarrow b+aX$
$a\leftarrow a+b$
$b\leftarrow b+bY$

コンテスト中は再帰で実装しましたが、普通のループで問題ありません。
テキストの公式解説のDPに近い感じですが、ボトムアップかトップダウンかという点が違うかなと思います。

再帰
 Submission #33311975 - AtCoder Beginner Contest 260

ループ
Submission #33347207 - AtCoder Beginner Contest 260

D - Draw Your Cards

まず、以下が高速に実現可能なデータ構造が必要です。

$X$ 以上で最小の整数 $Y$ を得る
$Y$ を削除する
$X$ を挿入する

これは順序付き集合で実現できます。(C++なら順序付き集合set)

次に、以下を実現する必要があります。ここで、表向きで重ねられたカードを山と呼ぶことにします。

$X$ とそれ以上で最小の整数 $Y$ を同じ山にする
$X$ が属する山にあるカードの枚数を取得する
$i$ ターン目に $X$ が属する山のカード枚数が $K$ となった時に、山に属するカード全てに $i$ を記録する
$X$ が属する山が何ターン目に $K$ 枚となったかを取得する

これはUnion-Findにより実現できます。
AtCoder Libraryのdsu< long long > d(N)の使用例を示しておきます。なお、カードに書かれた整数は全て-1して、 $0,\ 1,\ ,\ \cdots N-1$ にしておくことにします。また、連想配列 $m$ を用意し、 $X$ が属する山が何ターン目で $K$ 枚となったかを $m[X]$ に記録することとします(普通の配列でも可)。

d.merge(X,Y)
d.size(X)
if (d.size(X)==K) m[d.leader(X)] = i
m[d.leader(X)]

ポイントとしては、同じ山の全てにターン数を記録するのではなく、Union-Findにおける同一グループの根にだけターン数を記録します。
各整数から根を辿ることで、自分が属する山が何ターン目に $K$ 枚となったかわかります。

計算量はsetの各種操作が $O(logN)$ で、Union-Findの各種操作が $\alpha (N)$ なので、 $O(N(logN + \alpha (N)))$ かなと思います。

2022-07-16

AtCodet Beginner Contest 259 参加記録

ベクトルの回転 ABC Union-Find

コンテスト中AC:A〜D

B - Counterclockwise Rotation

ベクトルの反時計回りの回転行列は以下の通りです。

よって、求めたい座標を $(p,q)$ とすれば、
$p=a\cos d - b\sin d$
$q=a\sin d + b\cos d$

となります。
但し、C++では角度はラジアンにしないといけないので、 $r\leftarrow \frac{d\pi}{180}$ として、 $d$ の代わりに $r$ を渡します。

実装は、ようやくベクトルの回転をライブラリ化したので、それを載せておきます。
Submission #33246511 - AtCoder Beginner Contest 259

D - Circumferences

円 $i,j$ 及び $j,k$ が交点を持つなら、点は $i,k$ 間を移動できます。
このように点が行き来できるような円の関係はUnion-Findで管理できます。

Union-Findにおいて、円 $i,j$ が同グループとなる条件は、円 $i,j$ が交点を持つことです。
この条件ですが、Web検索して以下を見つけました。

www.mathlion.jp

というわけで、円の全組を全探索し、以下の条件を満たし、交点を持たない場合以外にはグループ化します。

$a\leftarrow (r_i + r_j)^2$
$b\leftarrow (x_i - x_j)^2 + (y_i - y_j)^2$
$c\leftarrow (r_i - r_j)^2$
とした時、
$b\gt a\ \lor\ b\lt c$

誤差が怖いので、全て2乗で考えました。
半径の大小関係が規定されていたので、念のため $r_i \gt r_j$ の場合に判定することにしました（おそらく2乗するので必要ないです）。

グループ化した後は、点 $(s_x , s_y)$ を通る円 $i$ と、点 $(t_x , t_y)$ を通る円 $j$ がグループであるかを全探索し、1つでも同グループがあればYes、1つもなければNoとなります。

この全探索の前準備として、点 $(s_x , s_y)$ を通る円を配列 $S$ に記録します。
点 $(t_x , t_y)$ を通る円も同様に配列 $T$ に記録します。

点 $(a,b)$ が円 $i$ 上にあるかは、 $x_i^2 + y_i^2 = r_i^2$ に代入して、 $a^2 + b^2 = r_i^2$ を満たせば良いです。

計算量は、グループ化させていくところがボトルネックとなり、 $O(N^2 \alpha (N))$ だと思います。
$\alpha (N)$ はアッカーマン関数の逆関数です。

Submission #33105175 - AtCoder Beginner Contest 259

2022-07-14

構造体Loop

Loop アルゴリズム

初めに
概要
コンストラクタ
build
get
count
実装
アルゴリズム
AtCoderでの過去問でLoopを使える問題

初めに

独自で実装している構造体Loopについて書いておきます(C++です)。
AtCoderでこの構造体を使用して解ける問題が何度か出題されています。
一応、いくつかの問題でACは取れていますが、素人の実装なので、誤りがある場合があります。ご了承ください。

概要

$N$ 個の元を持つ集合 $A$ とその写像 $f$ が以下の条件を満たすとします。

$f:A\longrightarrow A$

$t\in A$ である初期値 $t$ が与えられ、ここから写像を求めることを繰り返すような処理についての以下のクエリを、 $O(N)$ の前処理をしておくことで、それぞれ $O(1),\ O(N)$ で答えられます。

$K$ 回写像を求めた時の元 $x$
$K$ 回写像を求める過程で $A$ の各元 $a$ からそれぞれ何回写像を求めたか

基本的には $f:\{0,\ 1,\ \cdots ,\ N-1\} \longrightarrow \{0,\ 1,\ \cdots ,\ N-1\}$ を想定しています。

集合 $A$ は構造体内では定義されていません。写像を構造体内に記述し、写像を求める中で得られた値のみを配列Vに記録していきます。

コンストラクタ

Loop<T, mapping> lp

写像mapping

を定義する必要があります。

T mapping(T x) {
    /* xが与えられた時のf(x)の内容を書く */
}

制約

型T は、unordered_mapで同一かどうかの判定ができればよい
集合 $A$ のサイズは $10^7$ 以下くらい(そうでないと、多くの問題でTLEになる可能性が高い)

build

void lp.build(T t)

クエリに答えるための前計算です。
後述するgetやcountの呼び出し前に実行する必要があります。

初期値tから写像を求めることを繰り返し、写像として得られた値が順番に配列Vに記録されます。同じ値に2回なった時点で処理が終了します。

計算量

$O(N)$

get

T lp.get(long long k)

初期値tからk回写像を求めた後の値を返します。

計算量

$O(1)$

count

vector<long long> lp.count(long long k)

初期値tからk回写像を求める時、Vの各要素から何回写像を求めたかをカウントします。

計算量

$O(N)$

実装

表示

template<class T, T (*mapping)(T)>
struct Loop {
    long long s, // ループのスタート
              e, // ループの最後+1 (初めて重複した値が出現した場所)
              l; // ループの長さ

    vector<T> V; //非ループ部とループ部を記録
    unordered_map<T,long long> mp; //値が2回現れたかを調べる

    void build(T t) {
        while (1) {
            if (mp.count(t)) {
                s = mp[t];
                e = (long long) V.size();
                l = e - s;
                break;
            }
            mp[t] = (long long) V.size();
            V.emplace_back(t);
            t = mapping(t);
        }
    }
    
    /*
    build呼び出し後に使用する
    写像をk回求めた時のt'を返す
    */
    T get(long long k) {
        if (k < s) return V[k];
        k = (k - s) % l;
        return V[s + k];
    }

    /*
    build呼び出し後に使用する
    k回まで写像を求めた時に各値に何回なったかをカウントする
    */
    vector<long long> count(long long k) {
        int size = (int) V.size();
        vector<long long> res(size, 0);
        for (int i = 0; i < min(s,k); i++) res[i] = 1; //非ループ部
        k -= s;
        if (k <= 0) return res;
        long long q = k / l, r = k % l;
        for (int i = s; i < e; i++) res[i] = q;
        for (int i = s; i < s + r; i++) res[i]++;
        return res;
    }
 
};

アルゴリズム

前処理について

$f:A\longrightarrow A$ という条件を満たす場合、写像を求めることを繰り返すと、同じ値が2回出た時点で以後ループします。
同じ値となったものを $x$ とおきます。

$x$ について、

1回目に出現した位置を $s$
2回目に出現した位置を $e$
右半開区間 $[s,e)$ に含まれる元の数を $l$

とします。
また、 $x$ が2回出現する直前までに出現した値を出現順で並べたものを、

$V=\{V_0,\ V_1,\ \cdots ,\ V_s,\ \cdots ,\ V_{e-1}\}$

とします。

写像を求めることを繰り返しても、 $V_0,\ V_1,\ \cdots ,\ V_{s-1}$ となるのは高々1回です。この部分を非ループ部と呼ぶことにします。
非ループ部のサイズは、 $s$ です。

$V_s,\ V_{s+1},\ \cdots ,\ V_{e-1}$ の部分は、この後写像を求め続けると $V_s = V_e$ となるためループします。これをループ部と呼ぶことにします。
ループ部のサイズは、 $l$ です。

前処理にかかる計算量ですが、鳩の巣原理から高々 $N$ 回写像を求めると同じ値になります。このため、 $O(N)$ です。

getについて

$K$ 回写像を求めた後の値が、非ループ部かループ部によって場合分けします。

非ループの場合
$K\lt s$ が成り立つ場合、最終的に非ループ部の値となり、それは $V_K$ です。
ループ部の場合
$s$ 回移動すると、 $V_s$ となります。残り、 $K-s$ 回の移動後にループ部のどの値になるかが分かればよいです。

これは以下の問題と同じです。

数列 $V'=\{V'_0,\ V'_1,\ \cdots ,\ V'_{l-1}\}$ を時計回りに並べ、時計回りに1つずつ進むことを考える。 $V'_0$ から $K'$ 回進むとどの元に到達するか。

この問題のように $l-1$ まで進むと $0$ に戻る場合、 $K'\ mod\ l$ をとればどこに行くかわかります。

$p = (K-s)\ mod\ l$ すると、 $p$ は $V_s$ からのオフセットとなるので、 $V_{s+p}$ となります。

計算量は $O(1)$ です。

countについて

非ループ部からは、1回しか写像を求めることはありません。そのため、 $K\leq s$ の場合、 $i\lt K$ を満たす $i$ 番目が+1ずつされます。

$K\gt s$ の場合を考えます。
非ループ部は全て1となります。

ループ部について、写像を求める残り回数 $K'$ は、 $K' \leftarrow K - s$ となります。
$K'=ql+r$ となる $q,r$ を求めます。 $q = \lfloor \frac{K'}{l} \rfloor$ 、 $r = K' \ mod\ l$ です。

これは、ループ部を $q$ 周して、残り $r$ 回写像を求めることに対応します。

よって、ループ部については、全て $q$ 加算され、更に $s\leq i \lt s+r$ を満たす $i$ 番目に+1されます。

以上から、 $V$ の各元について、一回の計算で何回写像が求められたかがわかるので、 $O(N)$ です。

AtCoderでの過去問でLoopを使える問題

ネタバレ注意

表示

ABC258E Packing Potatoes 問題実装

ABC241E Putting Candies 問題実装

ABC167D Teleporter 問題実装

2022-07-06

AtCoder Biginner Contest 258 参加記録

Loop ABC

コンテスト中AC:A〜D
コンテスト後にEを自力AC。コンテスト中に漠然とした解法まで思い浮かんでましたが、実装間に合わず。
A〜Dは特に書くことがないので、Eについて書きます。

2022/07/08追記
Eの実装中の同値類などは誤りなので、無視してください。

E - Packing Potatoes

説明のため、じゃがいもは円環に並んでおり、 $N-1$ 番目のじゃがいもまで行ったら $0$ 番目に戻るものとします。

$1\leq i\leq N$ の各 $i$ について、空の状態の箱に $i$ 番目のじゃがいもから箱詰めを開始したとします。この箱の箱詰めを終了し、次の箱の箱詰めを $A_i$ 番目から開始するとします。
$i\rightarrow A_i$ という関係性を有向辺とみなしてグラフ化します(この関係性は一定です)。

頂点 $0$ から出発して有向辺を辿ることを繰り返すと、鳩の巣原理により高々 $N$ 回で1回訪問済みの頂点に辿りつき、以後ループします。

有向辺を1回辿るということと、箱詰めが1回終了したことが対応します。従って、 $K$ 回目の箱詰めを始めたじゃがいもの番号は、有向辺を $K-1$ 回辿って、辿り着いた頂点番号に対応します。

$K-1$ 回でどこの頂点番号に辿り着くかというのは、まず、ループ前の非ループ部とループ部に分けて配列に記録しておきます。非ループ部ならそのままその頂点番号を返し、ループ部に辿り着くなら、ループに属する頂点数をループのサイズとして、ループサイズでmodを取ることで $O(1)$ で求められます。

以上から、 $i$ 番目のじゃがいもから始めた時に箱に詰めることになるじゃがいもの個数 $B_i$ を予め計算しておけば、各クエリに $O(1)$ で答えられます。

過去にもこのような構造をもつ問題は何度か出題されており、構造体Loopとして計算できるようにしてあります。
結構出題されるので、計算方法の詳細は別記事にまとめてみたいと思います。

次に、 $A_i,\ B_i$ の求め方です。愚直に $X$ 以上となるまで足し続けることは計算量的にできません。まずは円環で並ぶ $W$ を何周するか求めます。これは、 $W$ の和を $S$ とすると、 $\lfloor \frac{X}{S} \rfloor$ 周する必要があります。これを $Q$ としておきます。

残りは $X\ mod\ S$ 必要です。これを $R$ とします。残りは一周未満であることが確定します。

合計が $R$ 以上となるのに残り何個のじゃがいもが必要かを求める方法としては、 $W$ を2つ繋げた $W'$ を用意し、累積和 $S$ を求めます。
$i$ 番目のじゃがいもについて、 $R+S_{i-1}$ をキーとして $S$ を二分探索することで求めることができます。 (但し、 $i=0$ の時 $S_{i-1}=0$ )

二分探索した結果、 $W_i + W_{i+1} + \cdots + W_j\geq R$ となる、 $j$ が求まったとします。
すると、
$A_i \leftarrow (j+1)\ mod\ N$
$B_i \leftarrow N\times Q + j-i+1$
となります(実装では累積和を取る時にインデックスがずれて計算がおかしくなったので、注意)。
Submission #32991116 - AtCoder Beginner Contest 258

2022-06-30

AtCoder Biginner Contest 257 参加記録

ABC 二分探索 BFS 貪欲法ダイクストラ

コンテスト中AC:A〜D
コンテスト後にEを自力ACできたので、こちらに書いておきます。

2022/07/01 追記 Fも自力で解けたため追記

C - Robot Takahashi
D - Jumping Takahashi 2
E - Addition and Multiplication 2
F - Teleporter Setting

C - Robot Takahashi

誤った解法でかなり時間をロスしてました。
また、コンテスト後にこの記事を書いていて、嘘解法であることがわかりました。コンテスト中の嘘解法とコンテスト後の正しいと思われる解法書いておきます。

$W_i$ を大人と子供に分けます。
大人を
$A=\{A_1,\ \cdots ,\ A_M\}$
子供を
$C=\{C_1,\ \cdots ,\ C_K\}$

とします。
$A,C$ のいずれかが空の場合は、 $N$ 人達成可能です。以下、そうでない場合を考えます。

大人の判定が正しくなる個数を全探索します。この場合、実数 $x$ の候補として、 $A$ の要素のみを考えればよいです。

例えば、 $C_j \lt A_i \leq C_{j+1}$ という位置に $A_i$ が居るとします。 $C_j \lt x \leq C_{j+1}$ の範囲で $x$ を動かしても、子供の判定結果に影響を与えません。また、 $C_j \lt x \leq A_{i}$ の範囲にすると、 $A_i$ の判定を正しいものにできます。
よって、 $x=A_i$ として、損をすることがないです( $A_i = C_{j+1}$ のケースで少し悩みましたが、これも問題ありませんでした)。
なお、 $C_j$ や $C_{j+1}$ が存在しない場合でも、同様となります。

以上から、 $x=A_1,\ \cdots ,\ A_M$ とした時に正しく判定できる人数をカウントします。 $A$ の人数は明らかです。 $C$ の人数は、 $C$ を予めソートしておくことで、二分探索可能です。

コンテスト中の実装は以下のような感じです。
Submission #32731821 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

コンテスト後に、この実装の反例が存在することがわかりました。

5
00100
10 20 30 40 50

このケースでは、実装 $x$ を $x\gt 50$ として、子供の判定を全て正しくすることで、正しい判定を4人にできます。
しかし、最初の実装だと、3人になってしまいます。
なぜこのようなことになるかというと、大人の正しい判定が0人となる場合を考慮できていないためです。

これを正しく判定するためには、 $A$ に $\infty$ を入れておけばよいです( $\infty$ を正しい判定となる人数に含めてはだめです)。

Submission #32806566 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

D - Jumping Takahashi 2

$S$ は、ある値以上ならOKで、それ未満はNGという境界があります。そこで、二分探索できないか検討します。

二分探索の判定処理にかかる見積もります。
まず、以下が言えます。

ジャンプ力 $x$ で全てのジャンプ台に到達できるかは、始点となるジャンプ台を $1,\ \cdots ,\ N$ まで全探索し、どれか1つでも達成できればよい。

次に、

ジャンプ力 $x$ 、始点 $s$ ですべてのジャンプ台に到達できるかは、幅優先探索により $O(N+M)$ で判定できる。

ここで、 $M$ は辺数であり、今回の場合全2点間に辺がある完全グラフとみなせるため、 $M=\frac{N(N-1)}{2}$ です。よって、今回は $O(N^2)$ です。

以上から、ジャンプ力 $x$ で全てのジャンプ台に到達できるかという判定にかかる計算量は $O(N^3)$ です。

ジャンプ力として考えられる最大を $S_{max}$ とすれば、全体の時間計算量は $O(N^3 log{S_{max})}$ です。
$S_{max}=10^{18}$ とかでも、間に合うと想定でき、二分探索で問題ないことがわかります。

ここからが割と重要で、コンテスト中4回WAを出しました。 $S_{max}$ をいい加減に大きくするとオーバーフローします。

というのも、幅優先探索で、ジャンプ台間で移動可能かの判定には問題文中の以下の式を使います。

$P_i S \geq |x_i - x_j|+|y_i - y_j|$

$P_i$ は最大で $10^9$ になるため、ジャンプ力 $S$ が $10^{10}$ くらいになると $P_i S$ がオーバーフローしてしまいます。

そこで、 $S_{max}$ をしっかり目に見積もります。
$(-10^9,\ -10^9)$ と $(10^9,\ 10^9)$ 間を移動する時、

$|x_i - x_j|+|y_i - y_j| = 4\times 10^9$ となり、右辺が最大です。また、 $P_i = 1$ の場合、

$S \geq 4\times 10^9$ かどうかを判定することになるので、 $S_{max}$ は $4\times 10^9$ を見積もれば良いことになります。実際にこれでACできました。

その他の方法としては、__builtin_smull_overflowでオーバーフロー判定し、オーバーフローする場合は常に移動出来ることにしておいても良いかもしれません。
Submission #32746202 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

E - Addition and Multiplication 2

10進数 $X,Y$ について、考えます。 $X$ の上から $i$ 桁目(の整数)を $X_i$ という様に表現します。

$X\gt Y$ の時、以下が言えます。

$X$ の桁数が $Y$ の桁数より真に大きい
$X$ と $Y$ の桁数が等しいとき、上から $i-1$ 桁目までが等しいなら、 $X_i \gt Y_i$ (但し、便宜上 $X_0 = Y_0$ )

1番目の条件より、出来るだけ $x$ の桁数を大きくすればよいです。そこで、支払う金額が最小の整数 $d$ を選び、可能な限り置き換えを行います。なお、支払う金額が最小のものが複数ある場合、そのうち最大の整数を選びます。

次に2番目の条件より、 $x$ の最上位桁から優先的に $d$ より大きい整数に変更できないか検討します。変更後の整数についても大きい方から優先的に選びます。なお、 $x$ の桁の2つ分を1つの別の整数に変更すると、桁数が減るので、変更は1対1で行います。

残金がなくなり、変更操作ができなくなった時の $x$ が答えです。

$i$ 桁目についての具体的な変更方法は、残金を $N'$ とすると、 $C_d$ を払い戻したと考え、 $N'+C_d \geq C_j$ なら、 $i$ 桁目を $j$ とし、残金を $N' \leftarrow N' + C_d - C_j$ と更新します。
Submission #32759248 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

F - Teleporter Setting

町を頂点、テレポーターを辺とした無向グラフとみなします。移動時間は辺の距離とみなします。
一旦簡単のため、全て連結であるとしておきます。

$i$ に全ての未接続だった辺が繋がった場合を考えます。
最短距離は以下のパターンに限定されます。

(1) 未接続だった辺を経由しない
最短距離は、未接続だった辺を無視した $1\rightarrow N$ の最短距離となります。

(2) 未接続だった辺を経由する
$1\rightarrow i$ と $i\rightarrow N$ の経路に分けて考えます。最短距離は2つの最短距離の合計です。

$1\rightarrow i$
- $1$ から直接 $i$ に行く
  最短距離は未接続の辺を無視した $1\rightarrow i$ への最短距離となります。
- 未接続だった辺を持つ頂点 $s$ を経由して $i$ に行く
  $s$ は $1$ から最も近い頂点を選びます。この時、 $1\rightarrow s\rightarrow i$ という移動となります。最短距離は未接続だった辺を無視した $1\rightarrow s$ への最短距離+1です。
$i\rightarrow N$
- $i$ から直接 $N$ に行く
  最短距離は未接続だった辺を無視した $i\rightarrow N$ への最短距離となります。
- 未接続だった辺を持つ頂点 $t$ を経由して $N$ に行く
  $t$ は $N$ から最も近い頂点を選びます。この時、 $i\rightarrow t\rightarrow N$ という移動となります。最短距離は未接続だった辺を無視した $t\rightarrow N$ への最短距離+1です。

以上より、各 $i$ に接続した時の $1$ から $N$ への最短距離は、(1)又は(2)のパターンのいずれか小さい方となります。

$s,t$ 及び未接続の辺を無視した場合の最短距離は、未接続の辺を無視したダイクストラ法を $1$ 及び $N$ のそれぞれを始点として1回ずつ行えば求めることが可能です。

$1$ から $N$ に行けない時は、最短距離が $\infty$ になるようにすれば求めることができます。詳細は実装参照。
なお、 $s,t$ が存在しない場合もあるので、注意が必要です(WAしました)。
Submission #32861308 - NS Solutions Corporation Programming Contest 2022（AtCoder Beginner Contest 257）

geam1113’s diary

主にAtcoderのコンテストの備忘録を書きます。AtCoder緑と水色を行ったり来たりしています。