ARC088D

D - Wide Flip

問題概要:

{0,1}からなる文字列Sが与えられる.連続した部分文字列の0/1を入れ替える作業をし,文字列Sを0のみになるようにしたい.この入れ替える区間の長さの最小値をKとするとき,Kの最大値を求めよ.

制約:

1 ≤ |S| ≤  

解法:

まず連続する{0,1}の数を数える(連続した塊が左から数えてi番目であるとき,この数をとする).この数列の任意の区間を選んでマージして(下図)数列のサイズを1にするのが目的.

マージするときに選ぶ区間はできるだけ大きい方がいいので(Kを大きくするため),(全区間でない)最大の区間を選んでマージする,を繰り返すと最大のKが得られる.

最大の区間は{A}が負数を含まないため両端のうち小さい方を除く区間である.よってdequeを使って両端を比較することによって最大の区間を求めることはO(1)でできる.

赤枠の和の最小値(=4)が答え

ソースコード:

リハビリ（ARC064E)

半年近く虚無をしていました

E - Cosmic Rays

問題概要：(xs,ys)から(xg,yg)への最短経路長問題

ただしN個の点(xi,yi)の半径ri内は距離をカウントしない

制約：

• $-{10}^9\le x_s,y_s,x_t,y_t\le {10}^9$
• $(x_s,y_s)$ ≠ $(x_t,y_t)$
• $1\le N\le 1,000$
• $-{10}^9\le x_i,y_i\le {10}^9$
• $1\le r_i\le {10}^9$

任意のバリア2点間を移動することを考える。(xi,yi)から(xj,yj)へ移動するときの経路長が最も短くなるのは直線で移動するときなので、スタートとゴールをr=0のバリアと考え、各バリア間に重さmax(0,)の辺を張ってdijkstraをするとスタートからゴールまでの最短経路長が得られる。

隣接行列を使ってdijkstraで解くと計算量はO(N^2)

天下一プロコン2017 D

天下一プロコンは調子乗ってBeginnerじゃないほう参加したら見事に爆死しました

Cはともかく、Dは自力で解けなかったので解法をメモ

tenka1-2017.contest.atcoder.jp

問題概要：N個の非負整数がある　それぞれの値と価値はAi,Biである

Aiの任意の組み合わせの論理和がK以下となるようにしたとき、最大の価値の総和を求めよ

制約：

1 ≤ N ≤ 10^5

0 ≤ K ≤ 2^30

0 ≤ Ai ≤ 2^30(1≤i≤N)

1 ≤ Bi ≤ 10^9(1≤i≤N)

まず制約からして全探索、BitDPは不可能

bitwise orの特徴は A∨B = A ⇔ AはBの立っているビット全て立っている

なのでK以下の値に対してAiが含まれるかどうかを判定して、含まれている場合価値の和を取ればよさそう

次にK以下の値の取り方を考える　

論理和は0→1はあっても1→0という値の変化はしないため、Kに立っていないビットを取るようなK'(<K)を取れば全ての値をカバーできるはず

K'の取り方はKの立っているビットを下から探して、そのビットを0にした後に以下の桁を全て1で埋めれば良い

この方法だと計算量はO(NlogK)　ただしK=0の場合があるので注意

競プロで頻出の初歩的な（？）テクニック

使い所は多いけれど説明・紹介されることはあまりないようなテクニックのメモ

ほぼ全ての言語で使えるもの

整数での切り捨て切り上げ

自然数A,Bで除算をするとき、大半の言語では切り捨てられることを利用するテク

ex) 切り捨て A/B

切り上げ (A+B-1) / B

bit演算とか

1 << n は1をn回左シフトした数を表す、つまり2^nと等しい

また、x & (1 << n)とすることによってxの（下から数えて)nビット目が立っているかどうかを調べることもできる

x & -xはxの一番下に立っているビットを表す（なぜそうなるのかは2の補数でｇｇってください）

よって x / (x & -x)とするとxを2で割れるだけ割った数が得られる

最後に続いている0の数。NLZ(x) = count_bits( (x & (-x) )-1)

最初に続いている0の数。NTZ(x) = 32 - NLZ( (~x) & (x-1) )

動作が処理系によるもの（ここではC++で考える）

 文字で演算

C,C++では文字コードはASCIIを使っているので1byte変数として扱うこともできる

この文字コードでなくても(文字が連続しているならば)基本的に演算はできる

例えば

int cnt[26];

cnt[c - 'a']++;//cは小文字のアルファベット

のようにすればa,b,c...に0,1,2...を対応させてそれぞれの文字に対して数え上げなどができる

にぶたん

何故かめぐる式二分探索をバグらせてしまったのでメモ

めぐる式二分探索とは（自分がそう呼んでるだけだが）↓を参照

【めぐるのアルゴリズム講座】
二分探索（整数）の書き方
難しさ：４ pic.twitter.com/LGLbkS0D7l

— 因幡めぐる@競技プログラミング (@meguru_comp) 2016年2月9日

 結論から言うとsolve()が

mid >= ans のときtrueの場合 okが最小値

mid >  ans のときtrueの場合 ok-1が最小値

mid <= ans のときtrueの場合 okが最大値

mid <  ans のときtrueの場合 ok+1が最大値

半開区間がよくわかっていなかった模様　南無

ARC069Dを解いた

解くのに無駄に時間がかかったので自分への戒めに解説を載せておく

arc069.contest.atcoder.jp

問題概要は省略　

以下、狼と羊をそれぞれWとSと表記する

siがoのとき動物列をaiとすると

 {ai-1,ai,ai+1} = {SSS},{WSW},{SWW},{WWS}

xのとき

 {ai-1,ai,ai+1} = {SSW},{WSS},{SWS},{WWW}となる

このときai-1,ai,siがわかっていればai+1が一意に決まるため４通り試せば全ての列を調べることができる　計算量はO(N)

作られた列が内容を満たしてるかどうかは先頭と末尾に反対側の要素を付け足して、一致するかを確かめれば良い(ソースコードの10,21行目部分)

実装方法についてはSを1、Wを0（逆でも良い）としてbit演算をすると良い

図よりxのときa[i+1] = a[i-1] xor a[i]っぽいことがわかるのであとは漸化式的に更新するときれいに書ける

～余談～

考察に１時間強、実装に３０分弱かかった

最初の４０分くらいはO(2^N)アルゴリズムから法則性を探してて本当に何がしたかったのかわからない

ABC073

A問題

今回はWAしなかった（ドヤ顔

文字列でs[0],s[1]調べるだけ

ソースコードは省略

B問題

最初bool配列用意して席を埋めていくトンチンカンなコードを書いた

席は連続、同じ席に二人以上座らないという制約があるので

r-l+1の総和を取れば良い

C問題

概要：以下の施行をN回繰り返す　

　ある整数Nを入力、すでにNが場にある場合はNを消す、ない場合はNを場に追加する

1≦N≦10^5　1≦Ai≦10^9より場にある数を検索する方法とbool配列である数が場にあるかどうかを判定する方法は使えない

setを使えば検索、追加がO(logN)で済むので間に合う

計算量はO(NlogN)

D問題

概要：r1...rRに対しての巡回セールスマン問題

今回は多重辺（AとBの街に対して２つ以上の道）があるので二点間の最短距離を入れる必要がある

次にワーシャルフロイドで任意の２点に対して最短距離を記録・更新する

最後にNext_permutationを使って全通り（たかだか8頂点なので十分間に合う）

計算量はO(N^3+R*R!)（多分

追記

 今回でレート1200突破

晴れて水色コーダーになれました　ﾔｯﾀﾈ

今日から水色コーダー！！！！！！！！！！！！！！！！！！！ pic.twitter.com/0iZS0aKYbT

— l3 4 Λ/ † 4 l＜ 0 (@__Bactpus__) 2017年9月9日