ABC-D 87-104

色々あって更新していなかった。

そもそも旅行先でまでやるほどプログラミングが好きではない…

昨日は結局ABCが行われたようだが不参加。コンテスト後にD問題だけ見てみたが、後ろから処理 & union-findにちゃんとスムーズにたどり着けたのでok.

基本的には参加回数を稼いだ方が良いのだが、上限パフォ出せそうならむしろ出ない方が良い。ratingの仕組み的に、低パフォーマンスで回数重ねてしまうとその後上がりづらくなる。来週のAGCは出るか未定。そもそも時間的に出れるかも未定。

考察はしたが実装してないD問題が溜まっていく。
以下も、89以降は実装はしてない。
ストリーク切れたけどまあどうでもいい。

87
情報の先読みをして、誰か1人を基準にした上でbfs的に位置を決めていく。
矛盾が発生すればそこで打ち切り。

->位置の間の関係性が閉じてしまっているとbfsで辿りきれない。
setで無理やりどうにかする感じのを書いたが テストケース2だけTLE。
bfsでミスってるっぽいが解決法がよく分からんので黒魔術的なことをしてAC

88
最短ルートを求めて、それに使われていない全てを塗ればいい。
最短経路長と初期配置の黒の数が分かっていればHW-pathlen-initialblack

89
先に全てのマスについて処理し、mapを作る。
値から位置へのmapが最初に作るべきもの。

クエリは10^5なので、毎回処理でも間に合いそう。

90
Kがゼロでなければa!=bなので、b>aと仮定して最後に2倍でok
K以上b未満の数の総和をb=1...Nについて計算。

91
わからん
N^2個の数字の各桁について、現れる1の個数が奇数か偶数かで決まるが、繰り上がりをどうするか。
01
01
10
10
0-2-2

11
11
00
00
1-3-2

わからん。

想定解は、上位桁の情報をmodで潰した上で、各aiについて調べている。
30*N log Nが通るという発想がなぜか出てこなかった。
1の個数の偶奇というところまでは分かっていたのに。

92
100*100以外を考える必要はなさそう。

w w w w
w b w w
w w b w
w b w w
のように塗ると、4列でBを99稼ぎつつWを1にできる。
途中で好きな数Bを抜くこともできるので、4列あればWを1, Bを0-99にできる。
また、チェッカーボードで塗ると、2列でW,Bをそれぞれ100作れる。

よって、まずWBの少ない方が100以下になるまでチェッカーボードで塗る。
これは高々10列で終わる。

多い方を上のWにして、少ない方を0まで減らす。4列+1列
b w b
w b b

最後に多い方を塗る。高々4*6列。
実装ダルそう。

93

AB未満に出来るだけ詰め込むには？
1回目で1位だった人は、2回目にAB-1位であってほしい。逆もまたしかり。
素朴にはこれを繰り返すだけ。n位に対してnmがAB未満で最大になるようなmを探して組ませる。

A,Bの制約が大きく、単純にnについてループが回せない。
sqrt(AB-1)以下のnは必ず相手がいるはず。

場合分けよく分からん。
https://img.atcoder.jp/arc094/editorial.pdf
場合分けよく分からん。

94
全部見る必要はない。
最大になるのはn/2に最も近いkのみ。
昇順と降順でソートしておいて、lower_boundで見れば2N log N

95

もっとも左ともっとも右について調べればわかるがN^2で部分点。

左にだけ行く場合、右にだけ行く場合を調べると、後戻りしないならどこまで進めばいいかは一意に決まる。これはO(N)

後戻りのある場合、先に右に行くならどこまで進めばいいかはO(N)。これと左にだけ行く場合を合わせればいい。右に行くときに左を侵食している場合も考えられるので、それを処理する。左に進む個数に対して、そこまでで達成可能なカロリーの最大値を配列で持っておけばいい。O(N)

先に右に行く場合も同じ。あとは全体の最大値を出せばいい。

96
奇数は2n+1なので、任意の奇数5つの和は2(n1+...n5)+5
合成数をどう考えるか。n1+...n5がmod5で等しければ確実に5の倍数で合成数。
2が含まれる場合、残り4つの和は必ず偶数なので合成数。

したがって、上限までの全ての素数を求めてmod5で分類してカウント。
2を除いて54以上あれば勝ち。なかったらどうしよう。

97
Swap操作で繋がることを、その数字の間にパスがあると見る。
Nが小さくないのでワーシャルフロイドができない。どうするか。

Union findを考えると、同じunionに入っていれば好きなように動かせるはず。
piとiが同じunionかを数えればいい。

98
桁問題は苦手なんだよなあ。

最上位桁を考えると、l...rの中に1は一つ以下でなければならない。
また、下からの繰り上がりも考える必要がある。

xorは繰り上がりを無視した和なのでA+b>= A xor Bが成立。
等号は繰り上がりのないとき。

つまり、全ての桁で繰り上がりが無いような組を求めればいい。

lを固定して数える。
Aiの累積和から繰り上がりの発生を求められるか？

値の累積和ではなく、桁に登場する1の回数での累積和。
p[10^5][30]
あるlから出発して繰り上がりが発生する場所は、各桁について1の個数のlower boundを考えれば分かる。O(30 N log N)なのでTLEが際どいライン。

しゃくとりで良いのでは？
l2>l については、対応するr2がr2>=rを満たす。繰り上がりの判定があるのでO(30N)。

99
最終的には3色で塗られる。
Binom(30,3)*3！ なので全パターン調べればいい?
初期状態で各色ブロックに何色がいくつあるか数えておく。
塗る色を決めたら、もともとその色の場所以外全て塗ればよく、したがって色を決めたらO(1)でいける。

100
それぞれの項目について合計が正or負場合を考えると8パターン。
例えば全て正であれば、x+y+zが大きいものからM個取る。
項目2が負の場合を考えるなら、x-y+zが大きいものからM個取る。

これでいけるか？嘘貪欲だとツライ。

解説によるとOkだったらしい。

101

桁わからん。
119の場合119/11
199の場合199/19

9が多い方が良さそうではあるが、あまり上位の桁を9にしてしまうと問題。
最上位桁を1から2にすると、分子は1000...増えるが分母は1しか増えない。

ある桁の数字を増やしたとき、(n+10^k)/n * sum(n)/sum(n+1)が1と比べてどうか。
繰り上がりの発生はとりあえず無視。
10 ^k/nと1/sum(n)の大小で決まる。>=ならnはすぬけ数の候補。
nがすぬけ数ということは、任意のkについて>=が成立する。
この時条件として最も厳しいのは明らかにk=0。つまりsum(n)>=n

これだと19が入らない。二桁以上では満たせない。

下一桁が9の時、繰り上がりが発生する。この時、sumが8減少しnが10^k増えるので必ず増大。

下一桁以外で繰り上がりが発生する時も同様なはず。
繰り上がりのない場合は?

nがすぬけ数であるには、各桁kにおいて、1増やして繰り上がりが発生する or 10^k/n >=1/sum(n)が少なくとも必要。nを固定した時左辺はkについて単調なので、あるk以上では任意になってくる。

結局候補は、ある桁まで全て9で、それ以上は任意。
m桁のすぬけ数は、*****9..9。
各桁についてどこまで9にするのか調べる。

https://img.atcoder.jp/arc099/editorial.pdf
解説が分からん。19はどうやって出てくるんだ？

上の考察はこの人の解法と同じなので通りはしたっぽい。
http://drken1215.hatenablog.com/entry/2018/06/24/010600

102
CDの間をどこにするか決めると、BC, DE間のカットはそれぞれの区間の和をできるだけ等分に近づけるようなもの。
累積和が求めてあればこの切断箇所は二分探索で求められる。

CD間で同じことをやろうとすると入力例2で失敗する。

正解。ただししゃくとりなら全体でO(N)にできる。
本番で書くなら実装早い二分探索かな。

https://img.atcoder.jp/arc100/editorial.pdf

103
要望を区間と見て、重複度の大きいところから切っていけばいい。
具体的な実装どうするか。

切断した時の処理の仕方が分からん。O(M^2)になってしまう。

右の端点で考えてみると、各要望の右端より左に必ず切断点。

右端点最小の区間の右端で切る。
左端点がこの時の切断点より右にあるものだけが残る。

左端でソートしておく。
右端最小を求め(M)
二分探索で残す部分を決める(log M)
とりあえずこれでO(M^2 log M)になる。

左でソートしたあとで、i番目以降での右端の最小値を求めておく。
これは、右端から見ていって決めればいいのでO(M)で最小値を入れた配列を作れる。

この配列を参照すれば、上で最小値を求める部分がO(1)になるので通る。

想定解はもっと単純に左から決めていけばよいというものだった。
たしかにその通りで、直前にどこで切断したか記録しておけば、ある要望について無視して良いかがすぐにわかる。

400点問題はだいぶ安定して考察ができるようになってきた。
実装してないので落とし穴はあるかもしれないが。

104
Qのことを考えなければどうなるか。
dpで、i番目までにA,B,Cのどれまで決まっている時の数を求める。
このあいだのyahooコンと同じようなイメージ。

i番目がAのとき、
dp[i][A]= dp[i-1][0]+dp[i-1][A]

bのとき
dp[i][B]=dp[i-1][A]+dp[i-1][B]

C
dp[i][C]=dp[i-1][C]+dp[i-1][B]

dp[i][0]はiまでにどれも決めていない状態で、dp[i][0]=dp[i][0]でいい。

最終的にdp[N][C]が答え。

Qを考慮する。?はワイルドカードなので、上の全てのパターンの更新が発生する。
変わるのはi番目をスルーする時のカウントが3倍になること。

dp[i][0]=3dp[i]-1[0]やdp[i][B]=dp[i-1][A]+3dp[i-1][B]など。

答えはやはりdp[N][C]でいい。

dpはなんだかとても久しぶりなきがする。