geam1113’s diary

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

AtCoder Biginner Contest 263 参加記録

コンテストページ:LINE Verda Programming Contest(AtCoder Beginner Contest 263) - AtCoder

コンテスト中AC: A〜E

E - Sugoroku 3

期待値DPが使えます。
サイコロを振ることを操作と呼ぶことにします。

マスiからマスNまでにかかる操作回数の期待値をE_iとします。

マスiからは、マスi,\ i+1,\ \cdots ,\ i+A_iに行くことができます。
m = A_i+1とおけば、それぞれのマスには\frac{1}{m}の確率で移動します。

また、マスjに辿りつくと、マスjからは(平均して)E_j回の操作でマスNに行けます。iからjに行くのに操作を1回行うので、マスiからマスjを経由してマスNに辿りつくにはE_j + 1回の操作が必要になります。

以上から、以下の式が成り立ちます。

E_i = \frac{1}{m}(E_i + 1) + \frac{1}{m}(E_{i+1} + 1) \cdots +  \frac{1}{m}(E_{i+A_i} + 1)

さて、この式には右辺・左辺の両方にE_iがあるので、左辺に移行します。

\frac{m-1}{m}E_i = \frac{1}{m} + \frac{1}{m}(E_{i+1} + 1) \cdots +  \frac{1}{m}(E_{i+A_i} + 1)

E_i = \frac{m}{m-1}\{\frac{1}{m} + \frac{1}{m}(E_{i+1} + 1)+ \cdots +  \frac{1}{m}(E_{i+A_i} + 1)\}

この式より、E_{i+1}, \cdots ,\ E_{i+A_i}が求まっているとE_iが求められます。
同じマスに戻るような場合、一見無限回の試行が必要なように思えますが、 このように式変形すると問題なく求められる場合があります。

次に、期待値を求めていきますが、マスの移動先が少なければメモ化再帰等で愚直に求めていくことができます。 しかし、今回は移動先が多いためO(N^2)となってしまうので、もう少し工夫する必要があります。

前述の式を更に整理します。

E_i
= \frac{m}{m-1}\{\frac{1}{m} + \frac{1}{m}(E_{i+1} + 1)+ \cdots +  \frac{1}{m}(E_{i+A_i} + 1)\}

= \frac{1}{m-1}\{1 + (E_{i+1} + 1)+ \cdots +  (E_{i+A_i} + 1)\}

= \frac{1 + E_{i+1} + 1+ \cdots + E_{i+A_i} + 1}{m-1}

= \frac{E_{i+1} + \cdots + E_{i+A_i} + m}{m-1}

したがって、

E_i = \frac{E_{i+1} + \cdots + E_{i+A_i} + m}{m-1}

となります。 E_{i+1} + \cdots + E_{i+A_i}の部分を高速に求められればよく、連続した区間の和なのでFenwick TreeによりO(logN)で求められます。

以上より、E_N = 0を初期値として、i=N-1,\ \cdots ,\ 2,\ 1の順にE_iを求めていくことで、
O(NlogN)でこの問題を解くことができます。

(累積和を用いれば計算量が落ちるかもしれません)

Submission #33834218 - LINE Verda Programming Contest(AtCoder Beginner Contest 263)

AtCoder Biginner Contest 262 参加記録

コンテストへのリンク:
コンテスト中AC:A〜D

D - I Hate Non-integer Number

数列の部分和に関する問題なので、部分和DPを考えます。

  • dp[i][j]:=数列Ai項目までの部分和であって、和がjとなるものの個数

今回は、何個選んだかも必要なので、情報を足します。

  • dp[i][j][k]:=数列Ai項目までの部分和であって、部分和を構成する要素の数がj個、その和がkであるものの個数

今回、数列の要素数N\leq 100と少ないですが、1\leq a_i \leq 10^9であり、和のとりうる範囲が非常に大きく、上記のDPは使えません。

ここで、選ぶ要素数を固定し、X個とします。
X個の要素からなる部分和Sの平均が整数となるためには、SXの倍数である必要があります。すなわち、以下の条件を満たせばよいです。
S\ mod\ X = 0

つまり、部分和のmod\ Xだけわかれば、倍数となるかを判定できます。
そこで、以下のDPが考えられます。

  • dp[i][j][k]:=数列Ai項目までの部分和であって、部分和を構成する要素の数がj個であり、その和をSとした時にS\ mod\ X = kであるものの個数

このようにすれば、kのとりうる範囲も0\leq k \leq N-1となり、N個に限定されます。

計算量は、DPテーブルを埋めるためにO(N^3)かかり、X=1,2,\cdots ,Nのそれぞれについて計算する必要があるので、O(N^4)だと思います。
実装はコンテスト後に見直ししたもの。
Submission #33697694 - AtCoder Beginner Contest 262

AtCoder Beginner Contest 261 参加記録

コンテスト中AC:A〜F

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とする。なお、xC_1,\ \cdots C_Mに含まれていない場合は、D_x=0とする。

  • j\geq 1
    i-1回目終了後にカウンタがj-1の状態であって、i回目にカウンタを+1する操作(コイントスが表)となった場合に遷移します。この時、スコアとしてX_iD_{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進数の桁は01しかありません。
そこで、

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^dB_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...011...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

AtCoder Biginner Contest 260 F - Find 4-cycle

コンテスト後に自力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

AtCoder Biginner Contest 260 参加記録

コンテスト中AC:A〜D

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個持っていたとします。
ここで、次の様に操作します。

  1. レベルiの赤い宝石a個から、レベルi-1の赤い宝石a個と、レベルiの青い宝石をaX個得る。
  2. レベル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)))かなと思います。

AtCodet Beginner Contest 259 参加記録

コンテスト中AC:A〜D

B - Counterclockwise Rotation

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

  
 \begin{pmatrix} \cos \theta & -\sin\theta \\ \sin\theta &\cos\theta \end{pmatrix}

よって、求めたい座標を(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

構造体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

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

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

制約

  • T は、unordered_mapで同一かどうかの判定ができればよい

  • 集合Aのサイズは10^7以下くらい(そうでないと、多くの問題でTLEになる可能性が高い)

build

void lp.build(T t)

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

初期値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すると、pV_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} \rfloorr = 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 問題 実装