2020-05-06

AOJ 2443 Reverse Sort

解法

いろいろ嘘枝刈りBFSぽいことを考えましたが、全く解けませんでした…

↑こちらを参考にしました。
前から貪欲に揃えていくと、確実に $N-1$ 回以内で揃える事ができます。操作回数が増えると、たどり着ける状態が指数的に増えていきます。
なので、前(後ろ)からだけ見ていくのでは、最終的な状態が増えすぎてしまいます。
そこで、前から半分だけ、後ろから半分だけを見て、どちらからも行けるような状態が存在するかどうか、を調べます。
ということで、 $N/2$ 手だけ動かしてたどり着ける状態(と手数)を両方調べ、どちらにも存在する状態が無ければ $N-1$ 、そうでなければそれぞれの手数の和の最小値を求めればよいです。

感想

半分全列挙の経験があまりなかったので、面白かったです。勉強になりました。

2020-05-03

ABC166 E - This Message Will Self-Destruct in 5s

数式の変形

問題
 提出コード

解法

もちろん、ペア $(i,j)$ を全探索することは難しいです。
ペアとしてカウントされる条件を詳しく見ていきます。
$i \lt j$ としたとき、カウントされる条件は、

$j - i = A_{i} + A_{j}$

となります。
これを式変形すると...

$j - A_{j} = A_{i} + i$

となります。
$j$ より小さくて、 $j$ とペアになれる $i$ の個数は、上の条件を満たす $i$ の個数になります。
あとは、 $j$ について前から見ていき、 $A_{i} + i$ をそれぞれの値ごとにいくつ存在しているか、を見ればよいです。
やることは下の記事にある問題(と、そのページに貼られている類題)とほとんど同じです。

emtubasa.hateblo.jp

2020-05-01

AOJ 2611 - 順位付け

動的計画法(DP) 二乗の木DP

問題
 提出コード

解法

木の2乗DPとかなんとか言われてるやつです。
問題文をじっくり読むと、入力が木になっていて、そのなかで順位付けをしていくことがわかります。木全体の根は、入力時点で一番高さが高かった頂点です。
木の高さがすべて異なる場合は簡単に求めることができますが、同じ高さの場合があるのでさっと解くことはできません。
以下のようなDPを考えます。

$dp[v][i] = v$ を根とする部分木について、高さの種類数が $i$ となるようにしたときの、高さの決め方

頂点が葉だった場合は、 $dp[v][1] = 1$ となります。
それ以外の場合、子についてそれぞれ探索してから、自分自身にマージしていくことを考えます。
$tmp[i] =$ 子についていくつか見た後の、現時点での値(高さが $i$ 種類となるようなパターン数)
ここに、 $dp[c][j]$ 達をマージしていきます。 $c$ は、今見ている子です。
$tmp[i]$ と $dp[c][j]$ を組み合わせると、
新たな種類数は $[max(i,j) , i + j]$ の区間のいずれかの値になります。
新たな種類数が $k$ になるパターンを考えます。
$i,j$ 種類を組み合わせて $k$ 種類にする際、

$k$ 種類の中から、 $i$ 個を選び、 $tmp$ 側の高さを全て割り振る

という操作をまず行うと、 $k$ 種類の中から、すでに選択された $i$ 個と、まだ選択されていない $k-i$ 個にわかれます。
ここから、 $j$ 個の頂点に高さを割り当てなければなりませんが、この中で、 $k-i$ 個は残りの $j$ 個のいずれかが選ばないといけないので無視します。
ということで、残った $i$ 個の中から、 $j - (k - i)$ 個を選び、 $j$ に割り当てる必要があります。
割り振る場所を決めてしまうと、順番は一意に決まるので、最終的に、 $i,j$ 種類を組み合わせて $k$ 種類を作成する際のパターン数は、
$_{k}C_{i} \times _{i}C_{(i + j - k)}$ 通りです。
ということで、ここに $tmp[i] \times dp[c][j]$ をかけたものを、新たに足しこめばよいです。
f:id:emtubasa:20200501143824j:plain
このようにして、 $tmp$ と $dp[c]$ を組み合わせて新たな $tmp$ を作成、という操作を繰り返します。
その後、最終的な $tmp$ について、 $dp[v][i] = tmp[i - 1]$ とすればよいです。今見ている頂点 $v$ 自身を種類数に加えるためです。
計算量についてですが、一見 $O(N^{4})$ かかるように見えますが、一番内側のループ以外が合わせて $O(N^{2})$ になるみたいです。
詳しい解析はこちらを参照してください。

snuke.hatenablog.com

2020-04-27

ABC164 D - Multiple of 2019

累積和

問題
 提出コード

解法

ここでは、 $S$ について下から $i$ 桁目の数字を $S_{i}$ と表記します。また、 $S$ の文字列の長さ、すなわち $|S|$ を $N$ とします。
加えて、 $X$ を $2019$ で割った余りを $X \ \%\ 2019$ と表記します。
まず、 $S$ について、桁ごとに分解して表現してみると、
$S_{1} \times 1 + S_{2} \times 10 + S_{3} \times 100 + ... S_{N} \times 10^{N-1}$
となります。
$S \% 2019$ は、次のように書くこともできます。
$(S_{1} \times 1 \ \% \ 2019+ S_{2} \times 10 \ \% \ 2019+ ... S_{N} \times 10^{N-1}\ \% \ 2019)\ \% \ 2019$
一般化すると、
$\displaystyle ( \sum_{i = 1}^{N} (S_{i} \times 10^{i-1} \ \% \ 2019) ) \ \% \ 2019$
ここで、 $Sum[k] = \displaystyle ( \sum_{i = 1}^{k} (S_{i} \times 10^{i-1} \ \% \ 2019) ) \ \% \ 2019$
と定義してあげると、
$Sum[0] = 0,Sum[k] = (Sum[k-1] + (S_{k} \times 10^{k-1}) \ \% \ 2019) \ \% \ 2019$
と
$10^{k} \ \% 2019 = (10^{k-1} \ \% \ 2019) \times 10 \ \% \ 2019$
の二つを組み合わせ、累積和のようにして $O(N)$ で計算することができます。
ここで、 $S$ の $i$ 桁目から $j$ 桁目までを取り出した数( $i \leqq j$ )は、これを $P$ として、
$\displaystyle P = \frac{\sum_{k = 1}^{j} (S_{k} \times 10^{k-1}) - \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1})}{10^{i-1}}$
$P$ が2019の倍数となるには、
$P \ \% \ 2019 = 0$
となっていればよいです。
2019と $10^{X}$ は互いに素なので、先ほどの数式のうち分子のみに着目することで、結局
$(\sum_{k = 1}^{j} (S_{k} \times 10^{k-1}) - \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1}) ) \ \% \ 2019 = 0$
であれば、 $P$ は2019の倍数ということがわかります。
これをさらに変形すると、
$(\sum_{k = 1}^{j} (S_{k} \times 10^{k-1} \ \% \ 2019)\ \% \ 2019 - \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1}\ \% \ 2019) \ \% \ 2019) = 0$
となり、結局
$\sum_{k = 1}^{j} (S_{k} \times 10^{k-1} \ \% \ 2019)\ \% \ 2019 = \sum_{k = 1}^{i-1} (S_{k} \times 10^{k-1}\ \% \ 2019) \ \% \ 2019$
という条件であるような $i,j$ のペアを探せばよいということがわかりました。
さて、この式は先ほど作成した $Sum[k]$ そのものの式で、
$Sum[i] = Sum[j]$
であるような $i,j$ のペアを探せばよいことになります。
$Cnt[k] = Sum[x] = k$ となるような $x$ の個数、という配列を用意しておき、

$Sum[i]$ を計算
$Cnt[Sum[i]]$ を答えに加算
$Cnt[Sum[i]]$ に1加算

という操作を、 $i = 0$ から繰り返して行けば、答えが求まります。 $Cnt$ については、取り得る添え字の値が $[0,2019)$ なので、そのサイズだけ確保しておけばよいです。

おまけ

今回のように、 $Sum$ と $Cnt$ を計算しながら答えを求めていく、というものはほかにもいくつかあります。
$Cnt$ は、今回添え字が最大で2019にしかならないのであらかじめ配列を確保しておくことができましたが、そうでない場合でも、列の長さが $N$ 以下のとき、種類も最大で $N$ 通りにしかならないことを利用すると、map等を駆使することで計算ができます。
$Sum$ も、単純な累積和でいいもの等があります。
ほかにも、 $2019$ が $10$ と互いに素でないケースが存在する問題等ありますので、是非見てみると良いと思います。
類題リスト↓

A - Zero-Sum Ranges

AGCの200点でかなりの難関といわれた問題です。しかし、今回の問題を知っていれば、おそらく解けると思います。今回のような操作をする問題の解法ツイート等では、この問題名がよくあがります。

E - Divisible Substring

コーナーケースに注意しましょう。

E - Rem of Sum is Num

少しトリッキーですが、帰着させることができます。

D - Candy Distribution

2020-04-23

MIS.W新歓コンテスト2020

bitDP 最大公約数(GCD) 数え上げ動的計画法(DP) 区間スケジューリング二分探索カタラン数しゃくとり法

自分の大学にあるサークルが主催するコンテストに参加しました。
自分のコードはまとめてここに上げてあります。問題の前から順番にa,b,...と振ってあります。自分のコードを動かすことができるeの入力データも添えました。
長いのでかなり端折る部分があります。
コンテストリンク

Mistale
Join MIS.W!
Okimochi Expression
Random Card Battle
SABAKAN FEVER
Jewelry Construction
MIS.W scheduling?
Taberungo
Contiguous Subsequences
Dentaku
感想

Mistale

$K = N$ か、 $F=N$ か、はたまたそのどちらでもないか、で場合分けをします。
サンプルに"Genocide"となるケースが存在しないので、

10 10 0 0

などと入力してチェックをしてあげたほうがよいでしょう。

Join MIS.W!

$P,C,M$ から、それぞれ $S_{i}$ で入力される人を引いていけば、最終的にすべてが0以下になっているかどうかで場合分けができます。

Okimochi Expression

$R$ の降順でソートし、得点が一番高い人について、"True"であれば(初期値が0の)カウントを+1,そうでなければ-1として、カウントが正か負かはたまた0になるか、で場合分けをします。

Random Card Battle

$O(Nmax(A_{i})$ が間に合うので、全ての $X$ について愚直に試してしまえばよいです。それぞれのカードについて独立なので、 $i$ 番目に勝てる確率の最大値について計算し、その総和を求めると答えになります。
$A_{i},B_{i}$ に対し、 $X_{i}$ を選択した場合、勝てる確率は
$max(A_{i} + X_{i} - max(A_{i} - X_{i} , B_{i} + 1) + 1, 0)$
です。出す可能性のある得点 $A_{i} + j$ を区間として見ると見やすくなるかもしれません。

SABAKAN FEVER

~~面倒な入力の部分必要だったのでしょうか~~問題自体はbitDPを用いて解けます。
$dp[S] = S$ の集合について、問題の条件に違反していないかどうか
とします。
それぞれについて愚直に見ると $O(2^{N}N^{2})$ かかってしまいますが、
とある集合 $S$ について、 $S$ から一つの要素を取り出して $i$ とした場合に、 $S\setminus i$ が問題の条件に違反してたら、その時点で $S$ も問題の条件に違反してしまいます。そうでなければ、 $i$ が、 $S\setminus i$ の要素と隣接していないかを調べることで、
$O(2^{N}N)$ に抑えることができます。
得点計算も愚直計算でそれぞれに対し $O(N)$ でできるので、全体で $O(2^{N}N)$ で解けました。
ちなみに、グーグル翻訳に投げてローマ字に直せばいいや、と思っていたのですが…
Google Translate

問題の指定ではしがsiなのに対し、翻訳ではshiになったり、北区がKitaとNorthに表記ゆれしたり、台東区がTaitoとTaitungで表記ゆれしたり、他にもいろいろあったりで大変でした。

Jewelry Construction

二人の持っている宝石を $p,q$ 個とします。よくよく考えると、 $p = q$ となるのは、 $p = q = k$ の場合のみです。それ以外の場合( $p \lt q$ とします)、最後に $p$ をA面に置いたのは明らかで、その結果 $q = pX + y$ となり、元々 $y$ 個だったのが $pX$ 個増えて $q$ 個になったのだとわかります。
ここで、 $y \geqq p$ の場合、この場合も明らかに最後に宝石が増えたのは $p$ をA面に置いた場合であり、 $y$ をA面に置いたターンは0倍であったことがわかります。
すると、0倍の操作については無視をして、 $q = pX + y (y \lt p)$ となるような $X$ の倍率で1回操作を行った、と考えてよいです。結局、 $y = q \% p$ になります。
これをお互い繰り返して行き、最終的に初期の条件、つまり $p=0,q= K$ になるかを調べればよいです。
この方法だと、初めに後手が $K$ 個、先手が $0$ 個持っているパターンが生じてしまい、 $K = 1,N =13,L=7$ のようなパターンで嘘解法になるように見えますが、この場合は、初手で $X = 1$ としてあげることで、上手く調整ができるようになっています。
これらの操作をうまくまとめると、結局 $GCD(L,N-L) = K$ であればOKです。 $L + K \gt N$ にのみ注意しましょう。

MIS.W scheduling?

実装が破滅しました(その1)。
曜日、時間は全て分になおします。
まずは、サークル活動に重複がないかを調べます。重複があり、この時点で $N$ 個すべてに参加できなければ"No"です。
次に、全体で参加できる数を調べます。 $N + M$ 個の区間について区間スケジューリングで調べればよいです。
最後に、今調べた個数に、サークル全てに参加しながらたどり着けるかを調べます。
サークルとサークルの空き時間それぞれについて、尺取り法のようにしながら、講義を入れられるかどうか区間スケジューリングで試していきます。
サークルについて、0分開始、0分終了および、inf分開始、inf分終了という2つの番兵を入れてあげると楽になります。
f:id:emtubasa:20200423153052p:plain

Taberungo

食べるリンゴ $M$ 個を決めたとき、それらを食べる順番は、明らかに $B$ が大きい順です。
なので、 $B$ でソートをします。
あとは、ナップサックDPのようにして解けばよく、

$dp[i][j] = i$ 番目までみて、 $j$ 個のリンゴを食べた場合に得られる満足度の最大値、とします。

$dp[i][j] = max(dp[i-1][j],dp[i-1][j-1] + A_{i} - B_{i}(j -1))$
で更新すればよいです。

Contiguous Subsequences

実装が破滅しました(その2)。
頑張って二分探索をします。
総和が $X$ 以下となるような連続部分列の個数が $P$ 個以上あるかどうか、については、しゃくとり法を用いることで $O(N)$ で調べることができます。
連続部分列全体の個数が奇数の場合は、 $P = N(N+1)/4 + 1$ として一度二分探索をすればよく、
偶数の場合は、 $P = N(N+1)/4$ と $P=N(N+1)/4 + 1$ の2パターンについて調べ、その平均を取ればよいです。

Dentaku

足し算によって区切られるので、掛け算について考えます。足し算も同様にすればよいです。
+で区切られる部分の連続する文字についての順列をまず考えます。
これはこんな感じで計算ができます。
次に、*を入れる箇所について考えてみると、文字が $n$ 個存在するときに、*は $n-1$ 個あります。
これらを左から並べていくときに、文字の個数 $p$ と*の個数 $q$ には、 $p \geqq q + 1$ という関係がなりたっていなければなりません。
左端は必ず文字なので、これを除くと、 $p \geqq q$ を満たすように文字と*を並べる並べ方を求めることになり、これはカタラン数そのものです。ということで、ここを参考に計算すればよいです。
+パートについてですが、+で区切られる文字列を1つの大きな文字と見てあげて、*と同じことを考えればよいです。
文字列について、辞書順ソート等できちんと並び替えることに注意すれば、この問題に答えることができます。
後は、計算した値の積を求めればよいです。

感想

実装で破滅した問題がいくつかあったので悔しいです。
典型っぽい考え方を使いつつ、面白い部分もたくさんあったので楽しかったです。
自分の中で400点問題と5,600点問題の難易度が逆転していました。

2020-04-22

AOJ 2828 - マトリョーシカ

最小費用流

問題
 提出コード
解説ACです。マッチング、難しいですね…

解法

元の問題について、体積の最小値ではなく、見えているマトリョーシカの個数を求める問題は、
最小パス被覆問題そのものになっています。これは二部グラフの最大マッチングに帰着させることができます。
sourse、sinkと、マトリョーシカそれぞれに対してin,outの2つずつ頂点を用意してあげます。
あとは、sourseから $n$ 個のout、 $n$ 個のinからsinkに加え、マトリョーシカ $i$ が $j$ をしまうことができる場合に、マトリョーシカ $j$ のoutから $i$ のinに向け、それぞれ容量1の辺を張ればよいです。
体積の最小値の場合は、これを応用して重み付き二部マッチングによって解くことができます。
容量は全てそのままで、 $j$ のoutから $i$ のinに向けて張った辺について、コストを $i$ の体積について符号を反転させた値とすることで、辺をカットする行為が $j$ の体積だけ得をすることに結び付けられます。
その他の部分でコストがかかることはないため0にしてしまえばよいです。
辺について一番異なるのは、最小費用流の場合、容量を $n$ 流すと指定しなければならない部分で、最終的に一番外側になるマトリョーシカ分もフローを流さなければなりません。これは、それぞれのマトリョーシカのoutから、直接sinkにコスト0、容量1の辺を張ることで表現できます。
あとは、 $n$ だけ流すのにかかるコストの最小を求め、その-1倍したものを、体積の合計から引くことで、最終的に一番外側になっているマトリョーシカの体積が求まります。
自分は、-1倍して解かずに、これを用いて解きました。2つのマトリョーシカを結ぶ辺については、 $m-(体積)$ 、outからsinkに向けては $m$ のコストに直します。すると、
$mn - (フローを流して求まった値)$ が最終的に得をする分の体積になります。
f:id:emtubasa:20200422233042p:plain

2020-04-19

AOJ 2703 - サイコロスタンプ

動的計画法(DP) bitDP

問題
 提出コード

解法

あらかじめ、 $i$ 番目のサイコロが転がった結果記される数字と座標のペアリストを作成しておきます。

$dp[S] =$ サイコロの集合 $S$ について、これらを最適な順番で転がした際に得ることができる得点の最大値

とすると、答えは $max(dp[S])$ です。
$dp[S]$ の求め方について考えます。
$S$ の中で、 $i$ 番目のサイコロを最後に転がした、ということを考えてみます。
このとき、 $S \setminus\{i\}$ と、 $i$ 番目のサイコロが通る座標で重複する部分があれば、 $dp[S \setminus \{i\}]$ から差し引かなければなりません。
ところが、重複する座標に今どの数字が書かれているか、というのはこれらの情報からは読み取ることができません。
ということで次に逆順、つまり、 $i$ を最初に転がしたとき、について考えてみます。
このとき、 $S \setminus\{i\}$ と、 $i$ 番目のサイコロが通る座標が重複する部分について考えてみると、その座標に何がかかれていようが、 $i$ 番目のサイコロがその座標に書き込む数字は別のサイコロによって上書きされてしまいます。
ということで、 $S$ の中で、最初に $i$ を転がした際に得られる得点の最大値は、
$dp[S \setminus\{i\}] + \sum (i番目のサイコロがS\setminus\{i\}と重複せずに書き込む座標の値)$
となります。
$dp[S]$ は、上記の計算を $i \in S$ について計算したうちの最大値となります。
$O(N max(|rot|)2^{N})$ です。自分は座標管理にmapを用いたので、 $\log$ が付きます。