bobuhiro11's diary

ABC139-141

20 Sep 2019

ABC #139 D - ModSum

$p_1=N, p_2=1, p_3=2, … , p_N=N-1$ とすると、$m_1=0, m_2=1, m_3=2, … , m_N=N-1$ となる。 なので、答えは$1, 2, 3, …, N-1$の総和。

ABC #139 E - League

$i$と$j$の試合を頂点$(i,j)$と表す。ただし、$i$と$j$をひっくり返したものは同一視する。 各頂点は、直前にすべき試合数$prev_{(i,j)}$と、その次に実行可能な試合の一覧$next_{(i,j)}$をもつ。 そして、$prev_{(i,j)} = 0$である試合を見つけるたびに、貪欲にその試合をしていくよう、シミュレーションする。 ここで、ある試合をするたびに、その次の頂点の$prev_{(p,q)}$をデクリメントすることに注意する。

ABC #139 F - Engines

あらかじめ各ベクトルを偏角ソートしておき、 720度分になるようにそのベクトルをつなげておく(後々、楽になる)。 そうすると、この問題の答えは、連続したベクトルの和であることが分かる。 すべてのベクトルについて、以下の操作を行う。

  • あるベクトルを始まりとして、連続したベクトルを足していき、長さが最長となるものを見つける。

ABC #140 D - Fce Produces Unhappiness

まず、幸福でない人に注目して、それをどれだけ減らせるかに注目する。 たとえば、$RLLLLRRRRRLLRRLLRRR$から幸福でない人を抜きだすと、$RL…….RL..RL…R$となる。 連続する人は同時に操作できるので、$RLRLRLR$と考えてよい。 そして、$RLRLRLR$ -> $RLRLR$ -> $RLR$ -> $RR$ -> (空)のように操作を繰り返せば良い。

ABC #140 E - Second Sum

Nから1まで、順番に見ていく。 ある要素$i$について見た時、左右には$i+1, i+2, … , N$の要素が置かれていることになる。 右側に最大値がある場合と、左側に最大値がある場合、それぞれについて、組み合わせを計算して、 合算すればよい。最大値の位置については、setlower_boundで見つけた。

ABC #140 F - Many Slimes

貪欲な感じで、できるだけ体力が大きなスライムから作っていけばよい。 うーん、今回はE・F問題よりもD問題が難しく感じた。。

ABC #141 D - Powerful Discount Tickets

すべてのアイテムを優先度付きキューqに入れておく。 割引券の枚数だけ順番に取り出して、以下の操作を行う。

  • qから最も値段の高いアイテムを取り出す。
  • そのアイテムの値段を半分(切り捨て)にして、再度qに入れる。

ABC #141 E - Who Says a Pun?

長さlenについて、二分探索する。 ある長さについて、ローリングハッシュですべての部分文字列のハッシュ値を入れておき、mapなどで入れておく。 ハッシュ値が一致して、なおかつ重複がなければ、その長さでは条件を満たすことが分かる。

ABC #141 F - Xor Sum 3

各ビットごとに考える。 まず、$A_1 \oplus A_2 \oplus … \oplus A_N$ を計算しておき、 1が立っているビットについて、どのように色分けしても答えに影響しないので、 取り出しておく。取り出した結果、$A_1 \oplus A_2 \oplus … \oplus A_N = 0$の状態になる。 ここで、青色のXORを$X$、赤色のXORを$Y$とする。 $X \oplus Y = 0$なので、XORの性質から、$X = Y$となる。 なので、$A_i$から幾つか選んで、そのXORを最大化するような、選び方を見つけたい。 吐き出し法(連立1次方程式をといていくような感じ)で、上位のビットから見ていき、 1が立っている要素を pivot 行とみなして、他の要素とXORを取っていく。 結果、$X = Y = A_1 \oplus A_2 \oplus … A_N$となる。


ABC136-138

24 Aug 2019

いくつかABCの問題を解いたけど、ブログに記録するのを忘れていた。 まとめて書いておく。

ABC #136 D - Gathering Children

一度RLの組に入ると抜け出せない。 偶数距離を移動させて、RLの組にくっ付ける。

ABC #136 E - Max GCD

ソートしておいて、小さい値は0に、大きい値は答え$d$に近づける。 前と後の両方向から、累積和を求めておく。

ABC #136 F - Enclosed Points

ある点$x$がふくまれるような矩形の数は、その上下左右の4つの領域からそれぞれいくつの点を選ぶかによって計算できる。領域ごとに含まれる点の数を$A, B, C, D$とする。

  • 点$x$を含まない場合は、それぞれの領域から点を取るかどうかで16個に場合分けして考える
  • 点$x$を含む場合は単純に$ABCD$

領域ごとの点数の算出には、平面走査を使う。また、事前に座標は圧縮しておく必要がある。

ABC #137 D - Summer Vacation

アルバイトはどれも一日で終るためコストは変わらず、単純に支払日だけが異なるだけ。 アルバイトを報酬の大きい順に見ていって、できるだけ後ろの日程から埋めていく。

ABC #137 E - Coins Respawn

まず、DFSを使って、始点と終点どちらからも到達可能な頂点の集合$S$を求める。 あとはコストに$-1$を掛けて、ベルマンフォード法を適用して、最長経路を求める。 もし、集合$S$内の頂点が、閉路に含まれていたら、$-1$を返す。 単純に、ベルマンフォード法で閉路を見つけるだけでは不十分なことに注意する。

ABC #137 F - Polynomial Construction

フェルマーの小定理を使う。頻出テクニックだと思うので、復習しておきたい。 $a = {0,0,…,0}$の$i$番目を1にした$a’ = {0,0,..,1,…,0}$を考える。 そうすると、$a$を使った$f$と、$a’$を使った$f’$は以下のような関係になる。 これをすべての1が立っている$i$について、計算すればよい。

$(1-(x-i)^{P-1})$のところは、フェルマーの小定理より、$x=i$のときだけ1となる。 法 P において、以下が成り立つ。

ABC #138 D - Ki

各ノードのカウンタ$x$に足しておき、その後に根から累積和っぽく葉までDFS(BFSでもよい)でカウンタを更新していけばよい。

ABC #138 E - Strings of Impurity

文字列$s$を無限に連携した文字列$s’$を考える。 $t$の各文字を前から見ていき、その文字が$s$のどこに現れていくかをDPの要領で計算していく。

ABC #138 F - Coincidenc

Youtubeの解説動画と同じ解法で解いた。 $L \leq X \leq Y \leq R$ と $Y \% X = Y \oplus X$が条件。 まず場合分けをする。

  • 1) $X = Y$ の場合
    • $Y \% X = Y \oplus X = 0$ なのでOK
  • 2) $X < Y$ の場合
    • 2A) 2進数で$X$と$Y$の桁数が同じ
      • $Y \oplus X = Y+X-2(Y\&X)$
      • $Y\%X = Y-X$ (なぜなら $X<Y<2X$ より $Y/X=1$なので)
      • つまり、$X = X \oplus Y$
      • ある桁において$X=1$で$Y=0$はNG(そのほかの3つの場合でOK)
    • 2B) 2進数で$X$と$Y$の桁数が同じ
      • NG($Y\%X$は1から始まり、MODは0から始まるため)
  • 3) $X > Y$の場合
    • 問題の対象外なので考えなくて良い

その後、桁DP dp[i][j][k][s] を埋めていく。

  • 上からi桁番目まで見た時
  • jはX>=Lが確定しているかどうか
  • kはY<=Rが確定しているかどうか
  • sは先頭ビットが既に現れたかどうか

ABC135

03 Aug 2019

今回はE問題がかなり難しかった。F問題より難しく感じた。 Youtubeの解説放送を聞いて、やっとわかってきた。 自分用のメモなので、日本語が雑になっている。。

ABC #135 D - Digits Parade

dp[i][j]をi桁目まで見た時に、あまりがjとなる場合の数として、求めていく。

ABC #135 E - Golf

事前に、X>=0,Y>=0にしておく

1) X+Yが奇数 かつ Kが偶数

-1を返す。 どうやっても奇数番地にはたどり着けない

2) X+Y>K

n=ceil(X+Y/K)として、X+Y と nK の偶奇が異ればn++とする。余剰 nK-X-Y のために、冗長な経路を作る。 ここで、X=0 だと、序盤の移動において、マンハッタン距離が正しくないので、swap(X,Y)しておく(もちろん出力時には戻す)。

           +(X,Y)
           | Y
(0,0)+     -
   t |     | t = (nK-X-Y)/2
     |-----|
        X

3)X+Y<K

3-1) X+Yが偶数

n=2となる。それ以降の計算は、2) と同じ。

           +(X,Y)
           | Y
(0,0)+     -
   t |     | t = (2K-X-Y)/2
     |-----|
        X

3-2) X+Yが奇数( 1) の条件よりKも奇数)

n=3になる。これは思いつかない。この場合のみ、X, Y両方向に冗長な経路を取る必要がある。

                      p
                    +----+
                  (X,Y)  | Y
         (0,0)+          -
            t |          | t = K-X
              |-----|----|
                X     p = (K+X-Y)/2

4) X+Y==K

一発で行ける。

ABC #135 F - Strings of Eternity

ローリングハッシュで文字列の比較をO(1)で行えるようにしておく。 他のアルゴリズムでも良いと思う。 あらかじめSを充分に大きくしておく。 UnionFindを用意しておき、 Sのi番目とTがマッチして、なおかつ Si+T.size() 番目とTがマッチしているときは、 ii+T.size()に対して、Union処理を行う。 UnionFind全体で、グループの要素数の最大値が答えとなる。


ABC EF問題を埋めた(続き)

15 Jul 2019

前回の続き。Atcoder Beginner Contest #130 ~ #133を解いたので、まとめておく。 まだまだ解説なしでは解けない。。

ABC #130 F - Minimum Bounding Box

dp[i][j]をi,j番目が部分共通文字列となるときの組み合わせ数とする。 更新式もメモ化しておくと高速に計算できる。

ABC #131 F - Must Be Rectangular!

(x,y)座標を2部グラフとみなす。 グラフに置き換えて考えることでスムーズに解ける。

ABC #132 F - Small Products

N/xが同じ値になるxを同じグループとみなして、グループごとに計算を進める。 DPを圧縮していくイメージ。

ABC #133 F - Colorful Tree

木構造の頂点間の距離はLCA(最小共通祖先)を使うことで求めることができる。 実装解説は蟻本にまとまっている。 あらかじめクエリを先読みしておき、必要な頂点と色を抽出しておく。 DFSしつつ必要な値を埋めていく。


ABC EF問題を埋めた

16 Jun 2019

Atcoder Beginner Contest #116 ~ #129のCD問題をすべて解いた。 また、#126 ~ #129についてはEF問題が追加されているので、すべて解いた。 F問題は、解説PDF、解説Youtube、解説ブログを参考にした。

ABC #126 F - XOR Matching

https://atcoder.jp/contests/abc126/submissions/5909511

M=3とすると、長さ2^(M+1)の数列は、{0,0,1,1,2,2,3,3,4,4,5,5,6,6,7,7}のような要素をもつ。 このとき、{<0,1,...,7からKを除いた昇順の数列> K <7,6,...,0>からKを除いた降順の数列 K}とすれば良い。

  • K以外の要素について:間にはKだけが残ることになるので、条件を満す
  • Kについて:間には <7,6,...,0>からKを除いた降順の数列 が残る。XORをとるとKになるので条件を満たす。

ABC #127 F - Absolute Minima

https://atcoder.jp/contests/abc127/submissions/5930963

中央値が最小値となる性質を利用する。中央値が2つあるときには、左側を採用する。 中央値は、小さいほうと大きいほうをそれぞれ優先度付きキューで管理すると便利。 解説動画では、同一のaを二度入れてキュー間で交換するテクニックを使っていたが、 ナイーブに一度だけ入れる方法でも問題ない。 キューが片方に偏らないように、整理する必要がある。 更新クエリのとき、aが最小値を取る区間のなかに含まれていれば、最小値の更新はない。 一方、含まれていなければ、最小値を取る区間のなかで、最も近い点との差分を、最小値に追加する。

ABC #128 F - Frog Jump

https://atcoder.jp/contests/abc128/submissions/5921198

A、Bをそのまま扱うのではなく、C=A-Bk=何度戻りが発生するか という変数に置き換えて考える。 Cを固定すると、kが増えるにつれて、蓮を多く踏めるようになる。 同一の蓮を二度以上通るかどうかは、単純にsetで管理した。

ABC #129 F - Takahashi’s Basics in Education and Learning

https://atcoder.jp/contests/abc129/submissions/5945816

難しかった。まず、等差数列の各要素が何桁なのかによって、分割する。たとえば、A=3、B=4であれば、3,711,15,19に分けて考える。分割後は、sum_i=0^(l-1) (A+Bi)*10^k^(l-i-1)を求めることになる。 A sum_i=0^(l-1) 10^k^iB sum_i=0^(l-1) i*10^k^(l-i-1)にわけて、計算する。 どちらも漸化式に変換して解く(コード中のf,gに対応)。 解説動画を見るのがおすすめ。

Atcoder ProblemsのUser Page