2022-01-16

ABC235 参加記録

コンテスト中AC:A〜E

C - The Kth Time Query
D - Multiply and Rotate
E - MST + 1

C - The Kth Time Query

二次元配列 $B$ を用意し、 $B[ A_i ]$ には、 $A_i$ が出現したインデックスを順に記録します。

クエリが与えられた時、まず、 $B[ x ]$ のサイズが $k$ より小さい場合(出現数が $k個より少ない場合$ )は、-1を出力します。
そうでなければ、 $B[x][k]$ を答えとすれば良いです(0-indexedであれば、 $k-1$ となることに気をつける)。

しかし、今回 $a_i$ が大きく、配列に収まりません。そこで、 $A$ を座標圧縮します。
同様に $x$ も圧縮後の値を得ますが、 $x$ がそもそも $A$ に一回も出現していないパターンがあります。
この場合は、座標圧縮後の値が見つからず、正しく動作しません。このパターンで必ず-1を出力するために、 $A$ に出現した整数かどうかを記録する連想配列を用意して対処しました。
提出コード

D - Multiply and Rotate

可能な操作を整理します。整数 $x$ からは以下の条件を満たす整数 $y,z$ が作れます。

$y=ax$
$x$ の10進表記を $d_k d_{k-1}\cdots d_1 d_0$ とすると、 $d_0 d_k d_{k-1} \cdots d_1$ (但し、 $x\geq 10\ \wedge \ x\ mod\ 10\neq 0$ の場合)

ある整数にしたいような問題では、 $N$ から出発して値を小さくしていく、メモ化再帰が使われる場合があります。
しかし、今回の場合、操作によって必ず小さい数になるとは限らないので、この方法は使えません。

そこで、メモ化再帰、つまりDFS木の発想から、操作を重み1の有向辺とみなしてみます。

すると、整数 $1$ を始点とし、始点から最短経路問題と同様に最小の操作回数を確定できます。
すなわち、現在作ることが可能な整数の中で操作回数が最小な整数は、その後どのように整数を作っていってもその操作回数未満にすることはできません。
以上より、ダイクストラ法でこの問題を解くことができます。

なお、2個目操作で自分より小さい整数にできるため、 $N$ を超えた整数も考慮する必要があります。
桁数の増減は無いので、 $N$ が $m$ 桁なら $m$ 桁までの全ての整数を考慮しておけば良いです。
提出コード

E - MST + 1

クラスカル法で最小全域木をつくる時のアルゴリズムは、

辺のコストを昇順に並べて、辺のコストが小さい順から調べていき、辺[e=(u,v)]について、 $u,v$ が非連結ならその辺を採用する

というものです。よって、クエリの辺 $e_i$ が採用されるか否かは $G$ の辺のうち、コストが $w_i$ より小さい辺のみによって決定します。そこで、

$G$ の最小全域木を求める過程で、 $w_i$ よりコストが小さい辺を追加した後に、辺 $e_i$ が採用されるかを判定する

という方法ではどうでしょうか。
今回の制約上、

[texG]の辺のコストは相異なり、かつ $G$ の辺のコストと、クエリの辺のコストは全て異なる

となっています。従って、

$G$ の辺をコストの昇順に並べたとき、並び方は一意(クラスカル法による全域木及び辺の走査順が一意)
$G$ の辺をコストの昇順に並べたとき、クエリの辺の挿入位置は一意

が成立します。これによって、前述した判定方法で達成可能ということが言えます(多分)。
逆に、コストが同じ辺が存在する場合、同一コストの辺の走査順を変えることによって、異なる全域木(又はその部分集合)が構成されてしまい、構成されたものよって辺の採用の要否が異なる可能性が出てきます。

実際の判定方法のアルゴリズムですが、 $G$ の辺とクエリの辺をごちゃ混ぜにして昇順ソートし、クラスカル法で最小全域木を構成していきます。その過程で、クエリの辺が出てきた場合は、辺の採用の要否のみを判定し、全域木には追加しないようにします。

提出コード

2022-01-15

ABC216G 01Sequence

ABC 牛ゲー

問題へのリンク

解説AC

牛ゲーとのことで、解法は公式解説を見るのが良いかと思います。
ここでは、自分なりの理解をつけ足したいと思います。

牛ゲーについては、別記事にまとめました。

geam1113.hatenablog.com

また、ネットで調べると色々出てきます。

牛ゲーを適用するには、以下を満たす必要があります。

2値の差分の制約しかない
値を最大化する

そこで今回、

1の数を最小化する

ことを、

0の数を最大化する

と言い換えをすることが１つポイントだと思います。

次に、以下の3つが今回の制約です。

$B_i \leq B_{i+1}$
$B_{i+1} - B_i \leq 0\ \vee \ B_{i+1} -B_i \leq 1$
$B_{R_i} - B_{L_i -1} \leq R_i - L_i +1 -X_i$

制約1は自明かなと思います。

制約3は、0の数を最大化する問題とみなし、1の個数の制約を0の個数の制約に変換することで導き出されます。

制約2ですが、 $A_{i+1}$ を1にすれば $B_{i+1} - B_i \leq 0$ となり、 $A_{i+1}$ を0にすれば $B_{i+1} - B_i \leq 1$ となります。そこで、多重辺をもつような場合はどうなるのかという疑問が出ました。

おそらくですが、「0以下または1以下」なので大きい方の1以下のみが採用されます。これが、「0以下かつ1以下」であれば、0以下が採用されると思います。

牛ゲーでは、
$a - b \leq c$ という制約を「 $b$ から $a$ への重み $c$ の有向辺」
とみなします。これに従って、3つの制約式から有効辺を追加し、 $B_0$ を始点とした最短経路問題を解きます。重みが非負なので、ダイクストラ法が適用できます。

あとは、 $1 \leq i \leq N$ について、

$B_{i-1} \lt B_i$ なら $A_i \leftarrow 0$ 、そうでなければ、 $A_i \leftarrow 1$

として $A$ を構築できます。

提出コード

2022-01-11

牛ゲー

牛ゲーアルゴリズム

2022/01/15 修正・有向グラフの図追加

初めに
牛ゲーとは
最大値と最短経路
具体例

初めに

AtCoderの問題で牛ゲーが出たので、まとめておきます。数学的に厳密でない部分や、誤りを含む場合もありますのでご了承ください。

牛ゲーとは

以下の2つの問題があります。


という「2つの値の差分についての制約」のみからなる制約の元で、と各の差を最大化する線形計画問題

重みつき有向グラフについて、頂点から頂点にコストの有向辺があることをと表現する。


という辺がある重みつき有向グラフについて、始点から各頂点への最小コストを求める最短経路問題

この2つから得られる $d_{v_i}-d_s$ の最大値と、始点 $d_s$ から頂点 $v_i$ への最小コスト $d_{v_i}$ が同じになります。

従って、

2つの値の差分についての制約のみからなる
値を最大化する

という条件を満たす問題は、最短経路問題に帰着して解くことができます。

計算量は、 $w_i\lt 0$ を含むならBellman-Ford法によって、 $O(|V||E|)$ 、非負整数のみならDijkstra法によって、 $O(|E|log|V|)$ です。

最大値と最短経路

最短経路問題の最小コストが、線形計画問題の最大値を与えるというのがよくわかりませんでした。
この点について考察してみます。

例として、以下の有向辺を持つ有向グラフを考えます。

f:id:geam1113:20220115060606p:plain — 有向グラフ

$d_1 = 0$ とし、 $d_2 = 1$ までが求まっているとして、 $d_3$ を求めます。

有向辺を差分の制約とみなします。具体的には、
2から3への重み1の有向辺は、 $d_3 - d_2 \leq 1$
1から3への重み3の有向辺は、 $d_3 - d_1 \leq 3$
となります。
よって、条件は $d_3 \leq 2$ かつ $d_3 \leq 3$ となり、最終的に右辺が小さい方の
$d_3 \leq 2$ という条件のみとなります。
この時の右辺は、最短経路問題における最小コストであると言えます。

$d_3 \leq 2$ という制約において、非負整数であれば、
$0,1,2$ のいずれでも良いわけです。しかし、有向グラフとして考えていることから、 $d_3 = 2$ が採用されます。
これは、 $d_3 \leq 2$ という制約のなかでの最大値であると言えます。

もう少し一般化してみます。
頂点 $v_i$ が終点となる有向辺について、その有向辺の始点となる頂点を $u_1,u_2, \cdots , u_m$ とし、その有向辺のコストをそれぞれ $w_1,w_2, \cdots ,w_m$ とします。

これを線形計画の制約とみなしたとき、 $d_{v_i} \leq min(d_{u_1}+w_1,\ d_{u_2}+w_2,\ \cdots ,\ d_{u_m}+w_m)$ となります。右辺は最短経路問題における最小コストの計算と同じです。

また、最短経路問題と見做しているため、
$d_{v_i} = min(d_{u_1}+w_1,\ d_{u_2}+w_2,\ \cdots ,\ d_{u_m}+w_m)$ となります。これは、制約式の最大値となります。

以上が、最短経路が最大値となる理由だろうと思います。

具体例

AtCoder Beginner Contest過去問 : 解説記事へのリンク

2022-01-10

ABC234 参加記録

ABC ウェーブレット行列 N進数変換

C - Happy New Year!
D - Prefix K-th Max
E - Arithmetic Number

C - Happy New Year!

非負整数 $x$ の2進数表記の1を2に変換する操作を考えます。操作後の値を $f(x)$ とします。すると、以下が言えます。

$x$ と $f(x)$ は一対一対応する。
非負整数の変換によって、0,2のみからなる整数の全てを得られる。
$x \lt y$ なら $f(x) \lt f(y)$ である。

以上から、 $K$ の2進数表記の1を2にすると答えを得られます。
提出コード

D - Prefix K-th Max

ウェーブレット行列が使えます。
ウェーブレット行列では、以下の関数が $O(logP_{max})$ で使えます。( $P_{max}$ は $P$ の要素の最大値で、今回は $N$ )

$quantile(s,e,r)$ :半開区間 $[s,e)$ の $r+1$ 番目に小さい値を返す。

$P$ を0-indexedとすれば、 $K \leq i \leq N$ について、 $quantile(0,i,K-i)$ で答えが計算できます。

計算量は、 $P$ のウェーブレット行列の構築がボトルネックとなり、 $O(NlogP_{max})$ です。
提出コード

E - Arithmetic Number

整数 $X$ の桁数を $d$ とします。
候補となる等差数 $Y$ の制約を考えてみます。

桁数 $i$ は $d\leq i \leq d+1$
公差 $j$ は $-9 \leq j \leq 9$
最上位桁 $k$ は、 $1 \leq k \leq 9$

更に、実際に $Y$ を構築する時に、 $i$ 回の計算が必要になります。
ワーストケースのおおよその計算量は、
$2 \times 19 \times 9 \times 18 = 6156$ となり、十分に小さいので、全探索可能です。

$Y$ の各桁の計算の過程で、桁の数 $t$ が $t \geq 10$ または $t \lt 0$ とならないものだけを答えの候補とします。その中で、 $Y \geq X$ を満たすもののうち、最小の $Y$ が答えです。

なお、条件1は $d+1$ 桁の整数について、必ずゾロ目が含まれ、これは公差0の等差数になることより導けます。
提出コード

2022-01-03

ABC233F Swap and Sort

葉から探索 ABC DFS Kruskal

解説AC。大体の解法は自分が想定したものと合っていました。

ここでは、 $P_i$ を、頂点iに書かれた整数と表現します。

「i番目とj番目が交換可能」という条件を「頂点iと頂点jに無向辺がある」と言い換えます。

昇順に並び替えるとは、

すべての頂点 $i$ について、 $i$ と $P_i$ が等しい

と同値です。上記を達成するためには、

すべての連結成分について、同一な連結成分に属する頂点番号の集合 $V_i=\{v_j,v_{j+1},...\}$ とその頂点に番号に書かれた $P$ の集合 $Q_i=\{P_{v_j},P_{v_{j+1}},... \}$ が一致する。

となります。
一見ややこしいですが、すべての $P_i$ について辺を辿って $i=P_i$ となる位置に移動できるということを示しています。

次に、操作回数Kの制約があるため、操作回数のワーストを考えます。
頂点が5個の時を例にすれば、

V -> 1-2-3-4-5
P -> 5-4-3-2-1

上記のように頂点が昇順に連結し、Pが降順となっていた時が、バブルソートの交換回数と同様にワーストになると予想できます。
この時、交換回数は
$4+3+2+1=\frac{5(5-1)}{2}$
です。よって、N=1000の時、 $\frac{1000(1000-1)}{2}=499,500\lt 500,000$
となり、Kの制約に適合します。従って、 $V_i=Q_i$ さえ保たれていれば、グラフはどのような形をしていても達成可能だということがわかります。

ここで、各頂点からDFSし、頂点iに本来納まるべき整数を順次持ってくる解法が思いつきます。しかし、各頂点からDFSした場合の計算量は $O(N(N+M))$ となり間に合いません。

前述したように、グラフの構造は何でも良いので、全域森にしてしまえばよいです。全域森はKruskul法で構築できます。よって、辺の数は最大でも $N-1$ 個となり、計算量が間に合います。

今回、頂点と整数は葉である頂点から順に一致させていく必要があります。この実装でかなりつまづきました。
最終的な実装としては、

次数1以下の点をキューに追加する
キューが空になるまで以下を繰り返す
1. キューから頂点を1つ取り出しuとする。
2. uからDFSして整数を一致させる。この時辿った辺を操作列に追加する。もし一致できなかったら-1を出力して終了。
3. uを決定済みとする。
4. u及びuと隣接するすべての頂点 $v_i$ の次数を1減らす。 $v_i$ の次数が1以下でかつ未決定ならキューに追加する。

という風にしました。最初に葉をキューに追加する時は、次数0も追加しないといけません。なぜなら、

V -> 1-2 3 4
Q -> 2-1 4 3

というケースなどでWAとなります。
別に実装してみましたが、次数を減らした後に頂点 $v_i$ を追加する時の条件は、「 $v_i$ の次数が1である」のみにしてもよく、整数が決定済みかどうかという条件は省けました。

DFSでは、始点sと頂点uに書かれた整数が等しい場合に、始点sまで順次交換操作を行い、辺番号を操作列に追加します。

bool dfs(int s, int u, int p=-1) { //sは始点である頂点番号、uは現在訪問している頂点番号、pは親の頂点番号
    if (P[u]==s) return true; // 始点である頂点sと現在訪問している頂点uに書かれたP[u]が一致したら、trueを返す。
    for (auto&& e : g[u]) { //辺を示す構造体{始点from,終点to,番号id,コストcost}
        int v = e.to; //頂点uの辺eに接続する頂点v
        int id = e.id; //辺の番号。今回は操作番号に一致。
        if (v==p) continue; //親なら無視。木を前提としているため。
        if (dfs(s,v,u)) {  //始点sと一致する整数が見つかったら、
            swap(P[u],P[v]); //書かれた整数を交換する
            ans.pb(id); //操作列に辺番号を追加
            return true;
        }
    }
    return false;
}

提出コード

2021-12-31

ABC231 Minimal payments

ABC お釣り問題

解説AC

お釣りの問題は過去出題例があります。

過去問では、

maspypy.com

を参考にしました。

この解説と公式解説を踏まえ、まずは解法を書きます。

例として、

X = 35

A = {1,4,12}

を考えます。

$f(x)$ を $x$ 円払うために必要な最小の硬貨の枚数

と定義します。

$35\ mod\ 4=3$ は、1円玉でしかやり取りできません。

・1円硬貨で3円払って32円払う問題とする

・1円硬貨を使わず、おつりとして1円を受け取ることを確定させ、36円を払う問題とする

ことができます。

よって、35円を払うのに必要な最小枚数 $f(35)$ は、

$f(35)=min(f(32)+\frac{35-32}{1},\ f(36)+\frac{36-35}{1})$

となります。

同様に、 $f(32),f(36)$ は以下のように計算できます。

$f(32)=min(f(0)+\frac{32-0}{4},\ f(36)+\frac{36-32}{4})$

$f(36)=min(f(0)+\frac{36-0}{4},\ f(36)+\frac{36-36}{4})$

そして、 $f(0)=\frac{0}{12},f(36)=\frac{36}{12}$ というように計算できます。

各硬貨を考慮したときには、

・X以下の最小の $A_i$ の倍数。(ここでは $S_i$ とします。)

・X以上の最大の $A_i$ の倍数。(ここでは $T_i$ とします。)

の2パターンしか現れません。

そこで、以下のDPを考えます。

$dp[i][j]:=$

j=0のとき、 $S_i$ 円払うのに必要な硬貨の最小枚数
j=1のとき、 $T_i$ 円払うのに必要な硬貨の最小枚数

初期値は、

$dp[N][0] = 0,\ dp[N][1]=\frac{T_i}{A_i}$
です。

漸化式は、

$dp[i][0]\leftarrow min(dp[i+1][0]+\frac{S_i - S_{i+1}}{A_i},\ dp[i+1][1]+\frac{T_{i+1}-S_i}{A_i})$

$dp[i][1]\leftarrow min(dp[i+1][0]+\frac{T_i - S_{i+1}}{A_i},\ dp[i+1][1]+\frac{T_{i+1}-T_i}{A_i})$

これを金額が大きい順に計算しておくと、答えは $dp[1][1]$ (または $dp[1][0]$ 。等しくなるはず)です。

「 $A_{i+1}$ は $A_i$ の倍数である」がよくわからなかったこともあり、数直線で考えてみました。

下記の表は $A_i$ の倍数でいける座標( $A_i$ 円硬貨で払える金額)を示したものです。

f:id:geam1113:20211230065338j:plain

表を見ると分かるように、 $A_{i+1}はA_i$ の倍数であるという制約により、4円硬貨で支払えない金額は、12円硬貨でも払えません。

したがって、

・ $X\ mod\ A_i$ で得られる端数は、 $A_{i-1}$ 円以下の硬貨で支払うしかない

ことが言えます。

また、

・DPの過程で、 $A_i$ 円硬貨で支払う金額、 $S_i - S_{i+1}$ 、 $T_{i+1}-S_i$ 、 $T_i - S_{i+1}$ 、 $T_{i+1}-T_i$ が、 $A_i$ の倍数である

ことが保証されます。

この問題は、以下のように数直線上を移動する問題に言い換えができそうです。

0から始まり正の方向に無限に伸びる数直線があり、その数直線上を点0から点Xまで移動することを考える。

$A_1,\cdots ,\ A_N$ だけ、進むか戻ることができるとき、操作回数は最小で何回か。

数直線上を移動する問題においても、

・値の大きい方から移動した方が効率が良い

・Xに最も近い $A_i$ の倍数、すなわち $S_i$ または $T_i$ のみに移動すればよく、他は無駄である

・考慮する移動方法は、

　　・ $S_{i+1}$ から $S_i$ または $T_i$ に行く

　　・ $T_{i+1}$ から $S_i$ または $T_i$ に行く

ことから、元の問題と同様に解けるかなと思います。

提出コード

2021-12-29

ARC132 参加記録

ARC

コンテスト中AC:A,B

A - Permutation Grid
B - Shift and Reverse

A - Permutation Grid

nの制約上、実際に構築することはできません。
このことから、 $(r_i,c_i)$ の組みによって一意に定まるような法則性がありそうだと予測します。

白黒がどのように決定するか試して見ると、例えばn = 5では、

$R_5,C_5$ の行と列を全て黒で塗る
$R_1,C_1$ の行と列のまだ塗られていないマスを白で塗る
$R_4,C_4$ の行と列のまだ塗られていないマスを黒で塗る
$R_2,C_2$ の行と列のまだ塗られていないマスを白で塗る
$R_3,C_3$ の行と列のまだ塗られていないマスを黒で塗る

となります。
よく考えてみると、この決定順序は $R_i,C_i$ の順列の並び方によらず同じです。加えて、ある１つの順列で決定した塗り方について、行や列を交換して別の順列にしても条件を満たします。

よって、ある一例で色の塗り方を確認すれば十分です。

ここでは、 $R_i,C_i$ がそれぞれ昇順に並んでいるとして、n = 2〜6まで列挙してみます。
0が白、1が黒です。

01  001  0001  00001  000001
11  011  0011  00011  000011
    111  0111  00111  000111
         1111  01111  001111
               11111  011111
                      111111

こうすると、階段状に塗られることがわかります。
ここで、以下のような法則があると予想できます。

マス $(r_i,c_i)$ について、 $c_i \leq N-r_i$ ならそのマスは白、そうでなければ、黒

これがいずれのnについても成り立つことを数学的に証明はできませんでしたが、おそらく成り立つだろうという予測しました。実際、これでACしました。
提出コード

B - Shift and Reverse

2つの操作を突き詰めると、右または左への巡回シフトのみが可能です。
操作によって、昇順に並び替えることが可能という条件から、数列 $P=\lbrace p_1,p_2,\cdots ,p_n\rbrace$ は、

$\{ 1,2,\cdots ,n\}$
$\lbrace n,n-1,\cdots ,1\rbrace$

のいずれかをいくらか巡回シフトした数列だとわかります。
よって、最小な操作回数としてあり得るもの以下に限定されます。

Pが昇順の巡回シフトである場合
- 1が先頭に来るまで、先頭を末尾に移動する
- ひっくり返して、1が末尾にくるまで先頭を末尾に移動させる。そして、再度ひっくり返す
Pが降順の巡回シフトである場合
- ひっくり返して、1が先頭に来るまで先頭を末尾に移動させる
- 1が末尾に来るまで先頭を末尾に移動させてから、ひっくり返す

よって、Pが元々昇順であったか、降順であったかに応じて、上記の小さい方を出力すれば良いです。

昇順の判定は、最初に1があるインデックスをposとして、
$i = 0,1,\cdots N-1$ であるすべての $i$ ついて、
$p_{(pos+i)\ mod\ N} \lt p_{(pos+i+1)\ mod\ N}$ が成り立つかどうかで判定できます。

提出コード

geam1113’s diary

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

ABC235 参加記録

C - The Kth Time Query

D - Multiply and Rotate

E - MST + 1

ABC216G 01Sequence

牛ゲー

初めに

牛ゲーとは

最大値と最短経路

具体例

ABC234 参加記録

C - Happy New Year!

D - Prefix K-th Max

E - Arithmetic Number

ABC233F Swap and Sort

ABC231 Minimal payments

ARC132 参加記録

A - Permutation Grid

B - Shift and Reverse