2018-10-20

QUPC2018-E:Treeone

最近よく見るやつ。

問題概要

長さ $N$ の数列 $\{A_i\}$ が与えられる。その数列の連続する部分列であって，総和が0であるものの個数を数列のたぴさと呼ぶ。数列のうち1つの値を自由に変えられるとき，あり得るたぴさの最小値を求めよ。
E - Treeone

解法

「数列の連続する部分列であって，総和が0であるものの個数」と聞いたら，累積和 $\{S_i\}$ を考えるのが定石である。その個数は， $S_i=S_j$ となる $(i,j) (i\leqq j)$ の組の個数に等しい。つまりは，ある条件を満たす区間の数である。このうち， $A_k$ の値を一つだけ変えて，どれだけそういう区間を減らせるかということを考えよう。答えは

「元の数列のたぴさ」から「 $A_k$ を変えることで減らせる区間の数の最大値」を引いたもの

である。「元の数列のたぴさ」の効率的な計算については，A - Zero-Sum Rangesがそのものなので参照していただきたい。
$A_k$ の値をうまく変えることによって， $i\leqq k \leqq j$ を満たす区間 $(i,j)$ については，条件を満たさないようにできる。例えば， $A_k$ を5000兆とかにすれば，もともと和が0だった区間の和が5000兆くらいになる。また， $A_k$ を5000兆に変えたことによって，和が0でなかったの区間の和が0になることもない。 $k$ を含む区間については5000兆という数字がでかすぎて和が0になりようがないし， $k$ を含まない区間は $A_k$ が5000兆になったところで何の影響もない。よって，各 $k$ について，「 $i\leqq k \leqq j$ を満たす区間 $(i,j)$ であって， $S_i=S_j$ なるものの個数」が効率的に求まればよい。
これにはimos法と呼ばれるものを使う(imos法を知らない方は調べてください)。各 $i$ について，「 $i$ から始まる条件をみたす区間の数」足し算し，「 $i$ で終わる条件をみたす区間の数」を引き算する。その後，順に累積和を取っていけば，各 $k$ に対して，「 $k$ を含む条件をみたす区間の数」がわかる。また

「 $i$ から始まる条件をみたす区間の数」は「 $i\leqq j$ であって， $S_i=S_j$ をみたすものの個数」に等しい
「 $i$ で終わる条件をみたす区間の数」は「 $j\leqq i$ であって， $S_j=S_i$ をみたすものの個数」に等しい

よって，各 $S_i$ の値が全部でいくつあるかを調べておき， $i$ が小さい順に上の計算をしてけばよい(詳細はコードを見た方がわかると思う)。実装上注意すべきは，単に $S_i=0$ となるような場合(つまり， $A_1+\cdots +A_i=0$ となる場合)を数えるために， $S_0=0$ から計算を行うところである。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3441083

$S_i$ がどんな値かわからないため，mapを用いている
「 $i\leqq j$ であって， $S_i=S_j$ をみたすものの個数」や「 $j\leqq i$ であって， $S_j=S_i$ をみたすものの個数」は適当に引き算すれば求まるので，直接調べる必要はない

方針はすぐだったが，変なところでバグらせて足を引っ張ってしまった。反省。

2018-10-20

QUPC2018-D:Novelist

きれいに解けるので好き。

問題

D - Novelist

考察過程

王都から都市へ移動する依頼をタイプM，都市から王都へ移動する依頼をタイプLとする。
最初は各依頼を頂点として，ある依頼を終えた後，実行可能な依頼について有向辺を張って，最長パスを調べるということを考えていたのだが，これでは辺が $O(ML)$ 本あるためTLEする。考え直し。
よく考える。タイプMの依頼を終えた後，Treeone君はある都市 $n$ にいる。次には(可能なものが存在すれば)タイプLの依頼を選ぶことになるが，都市 $n$ から出発する依頼のうち，現在時刻より後で，最も出発日が早いものを選ぶのが最適になる。できるだけ早く王都に戻った方が，多くの依頼を達成できるかもしれないからである。つまり，あるタイプMの依頼をやると決めた後，タイプLの依頼を終えて王都に戻ってくる日が一意に定まる。
それならば，以下のようにすればよい。

タイプMの各依頼に対して，その依頼の開始日と，王都に帰ってくる日を両端とした区間を作る(ただし，王都に帰ってこれない場合は作らないでおく)。
これらの区間について，区間スケジューリング問題を解く。その解 $\times 2$ を答えに加算する。
区間スケジューリング問題の最適解の終了日を記録しておく。このとき王都にいるので，タイプMの依頼のうち，まだ達成できるものがあれば答えに1を加算する。もう王都には戻ってこれないので，これでTreeone君の仕事は終わりである。

区間スケジューリング問題を知らない方は調べてください(すいません)。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3438077

タイプLの依頼は，出発する都市ごとにvectorで管理した。
あるタイプMの依頼に対する最適なタイプLの依頼を探すのに二部探索をしている。
もうちょっときれいに書けそう。

今思えば，「できるだけ早く王都に戻った方が，多くの依頼を達成できるかもしれない」という考え方はまさに区間スケジューリング問題を示唆するものであった。良問だと思う。

2018-10-20

QUPC2018-C:Ito Campus

慣れているとなんてことない問題だが，ちゃんと書いてみる。

問題:C - Ito Campus

解説

@から距離 $X$ 以内のマスは安全でないなので，そのようなマスを調べて安全でないマークをつけてから，安全なマスだけでSからGへの最短距離を調べればよい。安全でないマスを調べるのも，SからGへの最短距離を調べるのも，幅優先探索(以下bfs)すればよいのだが，前者については注意が必要という問題である。
例えば，「@を見つけたら，そこからbfsで距離X以内のマスに安全でないマークをつける」ということをすると，毎回のbfsに $O(X)$ かかり，@がいっぱいあると計算量が $O(XHW)$ となり，TLEする。
では，「安全でないマークをつけたマスは壁'#'にしてしまう」というアイデアはどうか。これならば，同じマスを2度以上探索しないのでTLEは回避できる。しかし，これではWAを踏んでしまう。例えば， $X=3$ として，以下のような状況を考えてみよう。外側の壁は省略してある。
f:id:sigma1113:20181020185553p:plain
ここで，(1,1)にある@から探索をすると，以下のようになる。
f:id:sigma1113:20181020185655p:plain
これで，(3,1)からあるマスを探索しようとしても，イノシシは壁を通れないので，ここで安全でないマスを調べるパートが終了する。そうすると，SからGまでは距離4で行けることになるのだが，実際はGは安全でないマスであるため，WAである。

そこで，次のようなbfsをする。最初に@であるようなマスと残りの距離 $(x,y,d)$ をqueueに入れてしまう。そこからは素直に安全でないマスを調べていくだけである。異なる点は最初だけだが，これでうまくいく。
うまくいくことを確認しよう。最初に@であるようなマスをqueueに入れておくと，以下のことが成り立つ。

すべての壁以外のマスに $(x,y)$ ついて， $(x,y,d)$ がqueueに入るとき， $d$ は $(x,y)$ について最適な値である。つまり， $d$ は $(x,y)$ から最も近い@から探索したときに得られる残りの距離である。

なぜなら，このbfsは「ある@からの距離が1のマスすべて」→「ある@からの距離が2のマスすべて」→...→「ある@からの距離がXのマスすべて」という順で探索が進むからである。また，どのマスも高々1回しか探索されないので，計算量も $O(HW)$ で済む。

提出

https://beta.atcoder.jp/contests/qupc2018/submissions/3439882
実装上の変なところ(?)は以下。

安全でないマスを調べる際には，queueに入れるときにマス $(x,y)$ を $2000\times x+y$ で管理している。 $y\leq 1000$ なので，2000で割ったときの商とあまりでマス $(x,y)$ を復元できる。こんなことをした理由は，pair< int, pair< int,int> > と書きたくなかったからなのだが，いい方法あったら教えてください。
とか言いつつ，2回目のbfsではマス $(x,y)$ をそのまま管理してる。何も他に情報がいらなければこう書くのが個人的には楽なためそうしている。

こういう探索の始点が複数あるbfsは割とよく見る。

2018-10-14

AGC028-B: Removing Blocks

数え上げ力の不足。

問題概要

1から $N$ までの番号がついたブロックが横にならんでおり，ブロック $i$ には重さ $A_i$ がある。ここから $N$ 回ブロックを取り除くのだが，ブロック $i$ を取り除くコストはブロック $i$ と連結な(自身も含む)ブロックの重みの総和である。取り除く順番は $N!$ 通りあるが，それらのコストの総和を求めよ。

問題リンク:

B - Removing Blocks

解法

この手の問題は，「 $A_i$ が何回加算されるか？」ということを考えるのが定石である(そこまではわかる，という人が多かったと思う)。特にこの場合は，「ブロック $j$ を取り除いたときに $A_i$ が加算されるのは何回か？」ということを考えればよい。各 $j$ についてこれを足し合わせれば「 $A_i$ が何回加算されるか？」という問いの答えがわかる(ここまではよかった)。

では，「ブロック $j$ を取り除いたときに $A_i$ が加算されるのは何回か？」という問いを考えよう。簡単のため， $j\leq i$ とする。公式解説では確率を用いているが(これはこれで賢い)，実は確率を持ち出さなくても十分である。ブロック $j$ を取り除いたときに $A_i$ が加算されるためには，ブロック $j$ を取り除くまでに，ブロック $j$ からブロック $i$ までが取り除かれなければよい。そのような順列はいくつあるかを考える。
$i-j+1=k$ とおこう。これら $j$ から $i$ の $k$ 個の数の並べ方のうち， $j$ が一番最初になるのはもちろん $(k-1)!$ 通りである。これを1から $N$ の順列に埋め込むことを考える。埋め込む位置の選び方は， $N$ 箇所から $k$ 箇所選ぶ場合の数なので， ${}_N \mathrm{C} _k$ 通りである。 $j$ から $i$ 以外の数字の並べ方は任意でよいので， $(N-k)!$ 通りある。以上より，「ブロック $j$ を取り除いたときに $A_i$ が加算されるのは何回か？」という問いの答えは， $(k-1)! \times {}_N \mathrm{C} _k \times (N-k)! = \frac{N!}{k}$ とわかった。
$i \lt j$ のときも同様に考えて同じ表式を得る。あとは， $\frac{1}{k}$ の累積和を事前に計算すれば，「 $A_i$ が何回加算されるか？」という問いに $O(1)$ で答えることができる。よって，全体で $O(N)$ で計算ができる。

提出

Submission #3403177 - AtCoder Grand Contest 028

これが解けなかったのは悲しい。

2018-09-16

AGC027-C ABland-Yard

初AGC2完記念(今更？)＆初900AC記念＆初黄パフォ記念。

問題概要

$N$ 頂点 $M$ 辺のグラフがある(単純とも連結とも限らない)。各頂点にはAまたはBと書かれている。好きな頂点を始点とし，好きな回数隣接する頂点の移動をしたときに，訪れた頂点に書いてある文字を訪問順に並べることでAとBからなる文字列を作る。このとき，AとBからなる任意の文字列を作ることができるか判定せよ。
C - ABland Yard

考察過程

まず，問題の条件を次のように言い換えた。

与えられたグラフの連結な部分グラフ $H$ であって「 $H$ の任意の頂点について，Aと書かれた頂点にもBと書かれた頂点にも移動できる」ようなものが存在する。

もとのグラフは $G$ として， $G$ の頂点のうちAにもBにも移動できるものを良い頂点，できないものを悪い頂点と呼ぶことにしよう。 $G$ のうち連結な良い頂点の集合を探せばいいのだから， $G$ の各頂点が良いか悪いかを判定して，良い頂点の連結成分(大きさ2以上)があるかを判定すればいいと思ったのだが，サンプルさえ通らず考え直す。

よく考えると，目標は上のような部分グラフ $H$ があるか判定することであったから，一番最初の時点で悪い頂点は $H$ を構成する頂点になり得ない。だから，悪い頂点はないものと考えてよい。

さらによく考えると，悪い頂点をないものと考えたことによって，最初は良かったはずの頂点が悪くなっていしまう可能性があることに気付く。悪は伝搬するのである。この伝搬を素直に見ていって，すべての頂点が悪くなったらNo，良い頂点が生き残ればYesっぽいということがわかった。

そうすると，これをシミュレートする方法を考えればよい。頂点 $v$ の，隣接する頂点でAが書かれているものの数を $a_v$ ，Bが書かれているものの数を $b_v$ とする。 $a_v,b_v$ の一方が0であれば $v$ は悪い頂点である。これはBFSでできる。
まとめると

最初に，すべての頂点 $v$ について $a_v,b_v$ を数えて，この時点で悪い時点をqueueに入れる。
queueから頂点 $v$ を取り出し，隣接する頂点に $v$ が悪いことを伝える。つまり $v$ に書かれた文字がAなら， $v$ に隣接する頂点 $u$ について， $a_u$ を1減らす。Bの場合も同様である。
2によって悪くなった頂点があればqueueに入れる。
2~3をqueueが空になるまで繰り返す。
悪くなった頂点の数をカウントし， $N$ 個ならNo，そうでないならYesである。

計算量は $O(N+M)$ であり，間に合う。実はコンテスト中はTLEするかもと思っていた。

提出

コンテスト中に出したものは試行錯誤の残骸が多く汚いので，整理したものを貼る。実装は重くないと思う。
Submission #3206813 - AtCoder Grand Contest 027

雑談

うまく頂点を増やして辺を張って閉路検出という方法もあるらしいが，それよりは比較的自然に出てくる解法だと(個人的には)思う(自分で思いついた方を自然に思うに決まっている)。閉路検出が書けるか怪しいため，後でやってみる。
パフォは2143でレートが100くらい上がった。嬉しい。最近の精進の結果が少し出たかもしれない。今解説を見ても天才だな...と思うってしまう問題でも，そのうち自然だなあと思えるようになってくるのかもしれない。
この回のAGCはBが100人程度しか正解していないという恐ろしい回だった。Bを10分くらい考えて無理そうと思い，(その時点での正解者数を勘案して)Cに振ったのは正解だった。

2018-09-02

ARC102-E Stop. Otherwise...

勉強になったのと，解説があまり丁寧でないのでまとめのため。
問題概要: $1$ から $K$ までの目が出るサイコロを $N$ 個振る。このとき， $2\leq i \leq 2K$ をみたす各 $i$ について，次の問題に答えよ。

・どの異なる2つの出目の和も $i$ にならないような出目の組の場合の数はいくつか？ただし，サイコロ同士は区別しない。

問題リンクE - Stop. Otherwise...

解法が2つあるので，どちらも紹介する。解法2の方が簡潔である。

解法1(解説解)

$i$ を固定したときの問題を考える。 $a+b=i$ を満たす $(a,b)(1\leqq a\leqq b \leqq K)$ のペアの個数を $n$ とする(具体的な $n$ の値はコード参照)。求める出目の総数は， $m$ 個のペアについては $a$ もしくは $b$ の片方のみの数が出現し， $n-m$ 個のペアについてはどちらの数字も現れないような出目の総数を $S(m)$ とすると， $\sum_{m=0}^{m=n}S(m)$ である。
$S(m)$ を求めよう。戦略は以下のようになる。まず，(1) $m$ 個のペアを使うと決めたときに，使用できる数の個数を求める。その次に，(2)それらの数を使った出目が何通りあるかを求める。最後に，(3)使用できる数の選び方が何通りあるか求める。これらをすべてかけ合わせた値が $S(m)$ である。
注意する必要があるのは， $i$ が奇数と偶数のときは少しだけ事情が変わってくるということである。 $i$ が偶数のとき，上のペアのうち， $a=b=\frac{i}{2}$ となるものが混入するためである。まずは， $i$ が奇数のときを考えよう。

(1) $m$ 個のペアの片方の数を必ず使うと決めたので，まず $m$ 個の数が手に入る(このとき， $a,b$ どちらを使うかは問題にならない)。他のペアの数は使わないと決めたので，残りは， $n$ 個のペアに入らない $K-2n$ 個の数たちを使う。よって，使用できる数の個数は $K-2n+m$ 個である。

(2) $K-2n+m$ 個の数のうちから $N$ 個を重複して選ぶ組合せの数なのだが， $m$ 個のペアの片方の数を必ず使うと決めたので， $N$ 個のうち $m$ 個はもう埋まっていると考えよう。すると，残りの $N-m$ 個を $K-2n+m$ 個の数で埋めてやればよい。重複組合せの記号 ${}_n \mathrm{H} _r={}_{n+r-1} \mathrm{C} _r$ を用いれば， ${}_{K-2n+m} \mathrm{H} _{N-m}$ 個である。

(3) まず， $n$ 個のペアから $m$ 個のペアを求める組合せの数は ${}_n \mathrm{C} _m$ である。さらに $m$ 個のペアにそれぞれついて， $a$ と $b$ どちらを選ぶかが2通りあるから， $2^m$ が掛け算される。

以上より， $i$ が奇数のとき， $S(m)$ は
$S(m)={}_{K-2n+m} \mathrm{H} _{N-m}\times {}_n \mathrm{C} _m \times 2^m$
とわかった。これを $0\leqq m \leqq n$ について足し合わせれば，過不足なく数えることができる。

$i$ が偶数のときは， $\frac{i}{2}$ を使うか使わないかで別々に数えるが，別々になるのは(2)の部分のみである。
・まず，奇数のときと同様に考えるため，ペアの数 $n$ は $n-1$ に置き換える。
・次に，(1)での使える数の個数は $K-2(n-1)-1+m$ としておく。 $-1$ というのは $\frac{i}{2}$ を差し引いたものである。((1)で求めたのは，重複を許して使うのことのできる数だったという言い方がわかりやすいだろうか。)
・(2)について， $\frac{i}{2}$ を使うとき，埋めるべき枠は $N-m-1$ 個，使わないときに埋めるべき枠は $N-m$ 個である。
・(3)は $n$ が $n-1$ に変わるだけである。
以上より， $i$ が偶数のときは
$S(m)=\left({}_{K-2(n-1)+m-1} \mathrm{H} _{N-m-1}+{}_{K-2(n-1)+m-1} \mathrm{H} _{N-m}\right)\times {}_{n-1} \mathrm{C} _m \times 2^m$
であり，これを $0\leqq m \leqq n-1$ について足し合わせれば，過不足なく数えることができる。

提出
Submission #3125501 - AtCoder Regular Contest 102

解法2(包除原理)

包除原理がそもそもなにかということについては包除原理 - Wikipediaを参照。
解法1と同様に， $a+b=i$ を満たす $(a,b)(1\leqq a\leqq b \leqq K)$ のペアの個数を $n$ とし，各ペアに1から $n$ までの番号をつけておく。集合 $A_k (1\leqq k \leqq n)$ を「出目の組み合わせのうち， $k$ 番目のペアが少なくとも1つあるようなものの集合」と定義する。すると，求める組合せの総数は，集合
$\bigcap_{k=1}^{n}\overline{A_k}=\overline{\bigcup_{k=1}^{n}A_k}$
の要素の数である(ド・モルガンの法則を用いていることに注意)。よって，包除原理を用いて $\bigcup_{k=1}^{n}A_k$ の要素の個数を求め，全体の出目の組み合わせの数 ${}_K \mathrm{H} _N$ から引けばよい。

$m (1\leqq m \leqq n)$ 個の $A_k$ たちの共通部分の要素の大きさを求めよう。 $m$ 個のペアの数は使うと決めたから， $N$ 個のサイコロのうち $2m$ 個の出目は決まっている。あとは，残りの $N-2m$ 個の枠を， $K$ 個の数で埋めると考えてよい。 $m$ 個の $A_k$ たちの選び方は ${}_n \mathrm{C} _m$ であるから，結局
${}_n \mathrm{C} _m\times {}_K \mathrm{H} _{N-2m}$
を， $m (1\leqq m \leqq n)$ の偶奇に対応して足し引きすればよい。

なんと，この解法は $i$ の偶奇に依存していない。包除原理最高である。

提出
Submission #3126896 - AtCoder Regular Contest 102

こういうのが時間内に解けるようになりたいですね。

参考
包除原理 - Wikipedia
E - Stop. Otherwise...
包除原理の解がもう少し丁寧に書いてあります。本記事と表現がちょっと違いますが、基本的な考え方は同じです。
ARC102 参加記録 - ARMERIA

2018-08-09

codeforces #502 C ~The Phone Number~

codeforces

背景が面白い問題だったのでつい投稿。嘘を書いていたら教えてください。
問題要約
長さ $n$ のpermutationのうち，最長増加部分列(LIS)の長さと最長減少部分列(LDS)の長さの和が最小になるものを1つ出力せよ。
https://codeforces.com/contest/1017/problem/C

本番はエスパーして解いたので，解説を見たところこう書いてあった。

You can use [Dilworth's theorem]https://en.wikipedia.org/wiki/Dilworth So assume we've already known that $LIS=L$ ,then we can achieve $LDS=\lceil \frac{n}{L} \rceil$ .

なんでや。

ということで詳しく調べてみた。
まず，いくつか準備。
定義(最小被覆パス)
$G(V,E)$ を閉路をもたない有向グラフとする。 $G$ の最小被覆パスとは，パスの集合の組 $P_1,\dots P_k$ であって，これらが $V$ の分割になっているようなもの(すべての頂点 $v\in V$ に対して，ある $P_i$ がただ1つあって， $v\in P_i$ )のうち， $k$ が最小のものである。

定義(反鎖)
$G(V,E)$ を閉路をもたない有向グラフとする。 $G$ の反鎖(antichain)とは， $V$ の部分集合 $P$ であって， $P$ の任意の2要素の間にパスがないもののことである。
本来この語は半順序集合に定義されるもののようだが，閉路をもたない有向グラフは半順序集合とみなせる(と思う)ので，ここではグラフで定義をしても差し支えない。

Dilworthの定理とは以下のようなものらしい。
定理(Dilworth)
閉路をもたない有向グラフ $G(V,E)$ における最小被覆パスの大きさ(上の定義でいうところの $k$ )と， $G$ の最大の反鎖の大きさは等しい。
証明は(https://en.wikipedia.org/wiki/Dilworth%27s_theorem)を参照。こちらは半順序集合の言葉で話を進めているので注意。

LISとLDSに話を戻そう。長さ $n$ のpermutationを $p_1,p_2,\dots,p_n$ とする。このとき，頂点集合を $\{p_1,p_2,\dots,p_n\}$ として，グラフを作る。 $p_i,p_j (1\leq i.j\leq n)$ について， $p_i\lt p_j$ かつ $i\lt j$ のときに $p_i$ から $p_j$ に辺を張る。このグラフを $G(V,E)$ とすると，LISの長さ $L$ は $G$ の最長のパスの長さであり，LDSの長さ $K$ は最大の反鎖の大きさになる。これが肝である。
こんな感じ。
f:id:sigma1113:20180809202306j:plain

LISの長さが $L$ のとき， $K=\lceil \frac{n}{L} \rceil$ が最小であることを示そう。Dilworthの定理より， $K$ は $G(V,E)$ の最小被覆パスの大きさに等しい。ここで，LISの長さが $L$ であることから，最小被覆パスを構成するパスたち $P_1,P_2,\dots,P_K$ のそれぞれの大きさは高々 $L$ である。すると， $KL\geq n$ ，つまり $K\geq \lceil \frac{n}{L} \rceil$ が成り立つ。この下界は達成できる。実際， $L(K-1)+1,L(K-1)+2,\dots,n,L(K-2)+1,L(K-2)+2,\dots,L(K-1),\dots\dots,L+1,L+2,\dots,2L,1,2,\dots,L$ がそうなっている。

本番中に証明までして通した人どれくらいいるんだろう。

参考:
codeforces https://codeforces.com/contest/1017/problem/C
https://codeforces.com/blog/entry/61081

Dilworth's theorem https://en.wikipedia.org/wiki/Dilworth%27s_theorem

Erdős–Szekeres theorem https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem

Divisor https://www.slideshare.net/oupc/divisor

順序集合 https://ja.wikipedia.org/wiki/%E9%A0%86%E5%BA%8F%E9%9B%86%E5%90%88