olpheの競プロ帖

競プロ問やアルゴリズム等の考察します

Codeforces Round #581 (Div. 2)D-Kirk and a Binary String

Codeforces

問題概要

長さNの01からなる文字列がs与えられる。次の条件を満たすの文字列tを見つけたい。

  • 長さがN
  • 任意の l , r (0 \le l \le r \lt N)について、[s_l:s_r] のLISと[t_l:t_r ]のLISの長さが同じ
  • tに含まれる0の数が上二つの条件を満たす中で最大

メモ1

まず、先頭と末尾以外の文字について、文字を変更できるパターンを考える。

  • 000->010:後ろ2文字を取ってきたときに不適
  • 001->011:少なくともこの3文字からはどのように部分文字列を取ってきても条件に違反しない
  • 010->000:後ろ2文字を取ってきたときに不適
  • 011->001:少なくともこの3文字からはどのように部分文字列を取ってきても条件に違反しない
  • 100->110:後ろ2文字を取ってきたときに不適
  • 101->111:3文字を取ってきたときに不適
  • 110->100:先頭2文字を取ってきたときに不適
  • 111->101:先頭2文字を取ってきたときに不適

また、一気に複数文字変更することを考えたときに、0.....0、1.....1以外の塊を変更させるのは、01若しくは10の部分を取ってきたときに不適であることがわかるため、複数文字変更のパターンは0.....0->1.....1か1.....1->0.....0だが、それらは1文字変更を何回か繰り返したものとみなせるので1文字変更のみを考える。また、001->011と011->001は逆操作であり、0の数を最大化したいことを考えるとあり得る操作は011->001のみになる。

メモ2

文字列sの先頭に0を、末尾に1を付けて考えてよい。これは、新たな先頭を含んだ文字列は常にLISの長さが1長くなり、新たな末尾を含んだ文字列は常にLISの長さが1長くなるからである。これによって、もとのsのすべての要素が、前の要素も後ろの要素も持つようになり、メモ1の内容を適用できる。

メモ3

s全体で考えたときにi文字目を1->0と変更できない場合は、あるl,rを選んだ時に、

  • [s_l:s_{i-1}]か[s_{i+1}:s_r]のどちらかは空ではない
  • [s_l:s_{i-1}]の末尾が0という条件のLISの長さ+1+[s_{i+1}:s_r]のLISの長さ
    \ne[s_l:s_{i-1}]のLISの長さ+1+[s_{i+1}:s_r]の先頭が1という条件のLISの長さ

となるようなl,rが存在する場合である。

二つ目の条件はよく見ると左右に分割することができることが分かる。両辺が等しくないときは左側、右側のどちらかが等しくないことが必要だからである。

また、これと、1を0に変えることより左側の条件は

  •  [s_l:s_{i-1}]のLISの長さ\gt[s_l:s_{i-1}]の末尾が0という条件のLISの長さ

右側の条件は

  • [s_{i+1}:s_r]のLISの長さ\gt[s_{i+1}:s_r]の先頭が1という条件のLISの長さ

と表せる。

メモ4

左から貪欲に変更していくことができると非常にうれしいので、貪欲で良いことを証明したい。

まず左側の条件を考える。既に左側の1を0に変更していた場合、[s_l:s_{i-1}]の末尾が0という条件のLISの長さは常に長くなるが、[s_l:s_{i-1}]のLISの長さは長くなる、変わらない、短くなるのどれもあり得るため、変更できない条件を見ると左側の変更によって、右側の変更を妨げない、もしくは促進する。

右側の条件を考えると、影響がないため、左側の変更によって、右側の変更を妨げない。

よって、左から貪欲に変更していくことが可能である。

なお、右側から変更していくと妨げる場合があるので注意である。

 

解法

今見ている文字の左側の0で終わる部分文字列のLISと1で終わる部分文字列のLISの長さの差、右側の0で始まる部分文字列のLISと1で始まる部分文字列のLISの長さの差が求められれば良い。文字が2種類なのですべて持っておきながらLISの長さを求めることが可能である。

 

実際にACした提出

https://codeforces.com/contest/1204/submission/59269885

Codeforces Round #576 (Div. 1)C-Matching vs Independent Set

Codeforces

問題概要

3Ｎ頂点Ｍ辺の単純無向グラフがある。このグラフから次のどちらかを取り出したい。

・互いに辺で結ばれていないサイズＮの頂点集合

・互いに頂点を共有していないサイズＮの辺集合

 

解法

全ての辺を好きな順番で見ていき、これまでに辺集合に追加した辺と頂点を共有しないならその辺を辺集合に追加する。

 

全ての辺を見終わったときに辺集合のサイズがＮ以上ならばそれが答えで、Ｎ未満ならば、辺集合の辺の端点となっていない頂点Ｎ個が答えである。(どちらもサイズＮまで小さくする必要がある場合がある)

 

これは余った頂点間に辺が存在するならば、辺集合に新たに辺を追加できることから、どちらもサイズ以外の条件は満たしているし、頂点の数が3Nなので少なくともどちらかはサイズの条件も満たしているのでうまくいく。

 

実際にACした提出

https://codeforces.com/contest/1198/submission/58131409

全国統一プログラミング王決定戦本戦-F Flights

AtCoder

問題概要

N個の頂点があり、各頂点はx,y座標とコストを持っている。これらをx,y,costで表す。頂点i,jを考えたときに、x_i \leqq x_j , y_i \leqq y_jを満たすときにij間に距離cost_jの辺が貼られる。

スタートからゴールまでの距離の最小値を求めたい。距離はdistで表す。

 

メモ

まずスタートとゴールを(x,y)で比較したときに、常にスタートが小さくなるようスタートをゴールを入れ替えても一般性を失わない。

(x,y)の昇順に頂点を見ていくことで、移動を「左下からの移動」「左下への移動」の2種類のみとして考えることができる。

 

左下からの移動

頂点iに左下にある頂点kから移動する場合

dist_i=min(dist_k)+cost_iである。

 

これは各頂点に対してO(N)であるため後に高速化することを考える。

 

左下への移動

頂点iから左下にある頂点kへ移動する場合、全てのkに対して 

 dist_k=min(dist_k,dist_i+cost_i)である。

 

これも各頂点に対してO(N)であるため後に高速化することを考える。

 

またこの時ゴールの右上にあるすべての頂点kも考えて、

ans=min(dist_i,min(dist_k+cost_k))である。

 

mapを用いた高速化

(y,x)をキーにしてdistを持つmapを用いることで、2種類の移動の際に見るべき頂点の数を1つにすることができる。これを実現するためにはmapの値が常に単調減少であるようにすれば良い。

頂点iを見ているときのことを考える。

左下からの移動

mapの値が単調減少であれば、(y_i,x_i)よりも小さい要素をキーに持つ要素の中でキーが一番大きな要素のみを見たら良い。これはlower_boundとprevを用いることなどで値の更新ができる。もしそのような要素が無ければその頂点にたどり着くことは不可能である。

但し追加の過程で単調減少でなくなる場合があるので、その場合mapから頂点iを削除するか、頂点iよりも後の要素の値が頂点iでの値よりも小さくなるまで頂点iの直後の要素を削除し続けることで単調減少を維持することができる。

左下への移動

 mapの先頭から見ていって値がdist_i+cost_iよりも大きい要素をdist_i+cost_iに変更することで値の更新ができる。ここでも単調減少でなる場合があるので、mapの先頭の値よりも2番目の値が小さくなるまで2番目の要素を削除し続けることで単調減少を維持することができる。

 

 

実際にACした提出

atcoder.jp

遅延セグ木を用いた高速化

座標圧縮後の各y座標以上に到達するための最小距離の最小値を持ったセグ木を用いる。セグ木はsegで表す。

RMQ(a,b)は[a,b]の最小値を求める関数である。

chmin(a,b,c)は[a,b]に対してseg_m=min(seg_m,c)を行う関数である。

頂点iを見るときのことを考える。

 左下からの移動は、dist_i=seg.RMQ(0,y_i)+cost_iである。

左下への移動は、これまで見た頂点のy座標の最小値をmin_yとするとseg.chmin(min_y,y_i,dist_i+cost_i)である。

 

 実際にACした提出

atcoder.jp

 

全国統一プログラミング王決定戦本戦-E Erasure

AtCoder

問題概要

N個のブロックが並んでおり、幅K+1以上の全ての区間がある。区間の数をM個とすると区間の選び方は2^M通りある。全てのブロックを選択できる区間の使い方は何通りか。

 

メモ

素直なDPをする方法と包除原理を用いる方法がある。

 

素直なDP

seicaさんから掲載許可を頂いた画像が非常にわかりやすい。

f:id:olphe:20190220184537j:plain

これを参考にしたAC提出

atcoder.jp

 

包除原理

ixmelさんに教えていただいた。

dp[i][j]を、i番目のブロックまで見て、i番目のブロックを(未来永劫)使わず、[0,i]でj個以上のブロックを使っていない場合の数と定義する。

分かりやすさのために、0番目のブロックとN+１番目のブロックを用意すると良い。

そうすると、dp[k][j]からdp[i][j+1]に遷移したいときに区間の幅とKから(k,i)での区間の選び方が求められる。

 

このままだと状態数がO(N^2)、遷移の種類がO(N)でO(N^3)だが、二次目を偶奇のみ持つことで状態数をO(N)まで減らすことができ全体でO(N^2)となるので間に合う。

 

この解法でのAC提出

atcoder.jp

AGC008-E Next or Nextnext

AtCoder

問題概要

サイズNの数列Aが与えられる。サイズNの1~Nの順列であるPの中で、

p[i]=a[i],p[p[i]=a[i]の少なくとも一方を満たすPの数を数える。

 

メモ

途中まではAtCoderの公式解説と同じ考察をする、「ただの閉路」の数え上げがDPで行える理由が分からなかったので(分かる人いたら誰か教えてください)、組み合わせで殴りたくなる。

 

サイズが3以上の奇数である閉路の数え上げ

閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は

\frac{K! \times S^M \times 2^{K-2M}}{M! \times 2^M \times (K-2M)!}

となる。(2つの閉路を選んだ時のペアの作り方はS通りあるし、ある1つの閉路の使い方は2通りある。)

Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。

 

それ以外の閉路の数え上げ

閉路のサイズをS、そのような閉路の数がK個、その中からM個のペアを作る場合の数は

\frac{K! \times S^M}{M! \times 2^M \times (K-2M)!}

となる。(2つの閉路を選んだ時のペアの作り方はS通りある。)

Mが1変わったときの差分は高速に求められるので、十分高速に全ての場合を計算できる。

 

閉路のサイズごとにこれらを求め、掛け合わせると答えが出てうれしいです。

ACの提出を載せます。

atcoder.jp

AtCoderで橙になるまでにやったこと

ポエム

橙になった記事が少ないので橙記事を書きます。

 

前回のみんなのプロコンで橙になりました。

 

 

簡単な自己紹介

olphe

競プロ始めて5年弱

今年度n=1で農工大入学

データ構造で殴るのが苦手で、構築やインタラクティブが得意

 

無->水-青ボーダー(ぐらい？)(高1春~高3夏)

 

AtCoderに参加する前で、JOIやPCKの本戦参加を目指していた頃です。

JOI非公式難易度表　AOJ/AtCoder-JOI

の難易度6までを埋めようとしていたり、

PCK予選の過去問の問6ぐらいまでを埋めようとしていました。

 

水-青ボーダー(ぐらい？)->黄到達(高3夏~浪人期夏)

 

CfやTcでは緑->青になっていました。

このころにtwitterで競プロerと絡むようになり、介護されていました。

ABC-ABを埋めたり、ABC-CD、ARC-ABの多くを埋めたりしていました。

また、JOIの難易度7~8ぐらいの問題を時間をかけて解いていて、考察をまとめて記事を書いていた時期です。(めんどくさくなって途中でやめています。)

 

黄到達->橙到達(浪人期夏~Now!!)

 

CfやTcでは青->黄になっていました。

序盤は難しくて解けていなかったABC-CDやARC-ABを解いたりしていました。DPばかり残っていて、苦手だと思いTDPCの簡単な問題を解いたり、600点までを埋めていました。

中盤は700点～900点ぐらいの面白そうな問題をつまみ食いしていました。

終盤はAGC-BCD埋めをしていたのですが、これがかなり大きいと思っていて、曖昧な感覚ですが考察の仕方が分かってきたような気がしています。

特にAGC-Dで感じたのが、個々のステップ自体はそんなに重くなくて、うまく組み合わせるのが求められている気がします。

今はAGC-Eもゆっくり埋めています。

また最近はICPCのことも考えてCfの2300点(？)前後も少しずつ解いています。

 

AGC埋めからは同時に実力の近い人と問題を解いており、解説の抜けを補い合ったり感想戦ができて楽しく問題を解けています。

 

橙到達->赤到達(Now!!~????)

2021年の夏ぐらいまでには赤くなりたい！

AGC-Eを埋めます。

ARC-CDを埋めます。

 

ICPC国内予選2018

参加記

メンバー紹介

ferin:基本的にはBとDを担当する。

div9851:基本的にはAとCを担当する。(←予選通過の立役者！！)

olphe:基本的にはEとFを担当する。幾何が出たらferinさんと1問交換、構文解析が出たらdivさんと1問交換

 

模擬国内前

僕が入学してすぐにチームが決まった気がする。(競プロerが少ないので)

5月ごろから週に1度500点*3ぐらいのセットを2時間で解く練習をしていた。(1時間でDまで解いて残り頑張ろうなみたいな感じ)

多くの練習でdivさんが構文解析引いてたの面白かった。

 

模擬国内

事前の打ち合わせ(？)通りとりあえずdivさんにFまで印刷してもらって問題を割り振る。

二人がAとBを一瞬で通したので次に軽そうなEの実装に入る。

楽勝じゃ～んとか言ってたら細かい部分で手間取ってちょっと時間がかかるも通る(FA！！！)

Fを考えている間にCが通る(すごい)

CHTかな～とか考えていたけど3回微分するといい感じになることに気づく(天才か？)

めちゃくちゃ時間かかったけど通る。

残りferinさんがDを、divさんがGを考えたり実装したりしていたけどどっちも辛そうだった。

5完で11位だったのでめっちゃ強いじゃんとか言ってた。

 

当日

先輩たちから大量のエナドリの差し入れをもらいつつ準備

 

模擬国と同じくFまで印刷してもらい問題に目を通す。Fが幾何っぽかったのでferinさんのDと交換する。

 

 開始後一瞬でAとCが通る。すごい。Dは枝刈り全探索をしたくなったので書くと最悪ケースでかなり重い。微妙だったのでBの実装に入ってもらうもBも辛そう。

その後しばらく高速化をしていたが、最悪ケースを埋め込むと爆速になったので通す。

その後Bも通る。

この時点で1時間以上経っていて焦って順位表を見るもその時点では5完は結構少なく、また順位が29位でそこそこ余裕があったので一息つく。

 

Eはくり返し二乗法で解けなかったら解けないでしょ！と強硬に主張して実装に入る(←戦犯)

二人が残りの問題の考察を進めるも辛そう。

そのままEが通らず終了(それはそう)

33位

 

順位は厳しかったけど通過したので挽回のチャンスがありますね！