https://betrue12.hateblo.jp/entry/2018/08/26/122740
“前項で書いたとおり、「中央値はX以下である」ことと、「X以上の要素が半数以上存在する」ことは同値です。そして、「整数Xが与えられたとき、集合の要素の中にX以上の要素は半数以上存在するか？」というYes/No問題は、直接中央値を求める問題よりもずっと考えやすくなります。というのも、各要素の具体的な値は全部無視して、X以上かどうか、だけで2値化して考えれば良いからです。”

108
Nが20以下でMが60以下なので、xからx+1に3本ずつ引ける。
全ての数字を重複なく、ということなので、hoge進数でやれそう。

辺の重みはゼロでも構わないので、
頂点xからx+1への辺の重みを、0, 3^(x-1), 2*3^(x-1)として3進数でやればいい。

面倒なのは、ちょうどL個という部分の処理。

30を考えると、3*3は必要だが2*3^3を入れるとオーバー
3^3も、それ以下をいれすぎるとオーバー

3^11>10^6なので、頂点数にはある程度余裕がある。
3^n-1までは安全に作れるので、3^nからL-1は別ルートで作るi。
頂点1から重み3^nの辺を伸ばし、すでに使った頂点以外を使って作る。

これを繰り返す。

解説は2進数ベースでやってる感じで、実装はあちらの方が楽そう。
2^n-1を超えた部分の処理が上手い。改めて制約を考えると二進数の方が自然だった。

109
うねうね動きながら処理していけば、全て偶数 or ひとつだけ奇数まで持っていけるはず。
どちらになるかはともかくとして、操作としては変わらない。

i, j を見て偶数ならそのまま、奇数ならi+1, jへ一つ移動させ、次はi+1, jを見るというのを繰り返す。

110
Mを素因数分解してから、1でない要素がいくつあるかで分けて数えていく。
k個の場合、nCk * (Mの1以外の約数のk個の箱への振り分け方)

素因数の重複がややこしい。
各素因数について、区別のできないボールとして分けていく。
kを処理する時にどれかの箱がカラにならないように注意する必要がある。
単純に分配した後でk*(k-1の場合)+kC2*(k-2の場合)... を除けばいい。

というかもっと単純に、各素数について独立に、N個に分配する場合の数を求めればいい。
カラになった箱には1が入っていると考えればいい。
Π binom(n+素数の登場回数-1, 素数の登場回数)

111
まず、十分にアーム全体が長ければ近づけるだけ近づけた後で帳尻を合わせればいい。
腕が重なることは許されているので、この場合0, 0からの距離の偶奇が全ての点で等しければ到達可能。部分点はこれで良さそう。

m<=40という制約をここに取り入れていく。
直感的に、マンハッタン距離の最大公約数とかが関係しそうではある。

最大公約数を作ることができるなら、それを何回か繰り返せば到達できる。
ただし、3, 12のような組み合わせでは3が作れなくなる。
最大公約数で割ったときの偶奇が等しければ、いって戻ってを適正回数やれば帳尻が合う。

マンハッタン距離で考えていたが、x, yそれぞれでやらないとダメか。
中途半端なところで曲げられないので。

結局、x, yそれぞれの方向の各店の距離の最大公約数を求め、それで割った偶奇をチェックする。全ての点で等しく、また、割った値のx, y方向での合計が40以下であれば作れる。

解説ぜんぜん違うやんけ。
https://img.atcoder.jp/arc103/editorial.pdf
マンハッタン距離は回転させるとx, y独立にあつかえるので2進数で作る。
負まで許せば、全ての腕を使いつつ任意の値を作れるということに頭が及んでなかった。
マンハッタン距離のこの性質は頻出っぽい。

冷静に見ると、上でやった考察だと最大公約数が小さい時に腕が足りない。

112
median of mediansのように、値について二分探索っぽい。
ある値xを最大公約数とするような分割が存在するか判定。
MがN*x以上でM%x=0ならok

用は、Mの約数でM/N 以下で最大のもの。

113
最低限必要な本数はK-1本。
『i th rowで j th colに居る為の、i-1 th rowまでのアミダパターンの数』でdp。

114
約数が75個ということは、その数は約数が75, 3*25, 5*15, 3*5*5個。
1,2,...,Nをそれぞれ素因数分解して約数の個数を数える。

115
レベルNバーガーの厚みは、x_{i+1} = 2x_i +3の解。
レベルiのパティの枚数も簡単に求まる。

与えられたxがレベルNのどこまでか。
半分超えてればレベルN-1のパティ+残り、という感じ。

レベルN-1の途中で止まっていることになるが、それがレベルN-2の言葉でどこか。

このように再帰的に潜っていって、レベル何の途中で止まっているかを突き止める。
確定で含まれるとわかったバーガーのパティから勘定に入れていく。

実装ミスりそう。

116
何種類食べるかを決めれば、それに応じて美味しさの高いものから取っていけばいい。
種類についてループを回すなら、log Nで作れないといけない。厳しい。

とりあえず、種類のことを気にせずK個取ったとするこれは解の下限。
構成から、どれを入れ替えたら大きくなりうるかといえば、種類数が増えるもののみ。

使用していない種類の品物を集めて価値でソート。
使用しているもののうちで使用回数が1のものは確定なので、2個以上の物を集めてまとめてソート。小さいものから順に入れ替えていく。ただし、すでに入れ替えたものと同じ種類はスキップ。各ステップでのスコアを記録しておいて、最終的に最大を出す。

種類毎の最大を出す、という一番最初にの方針を、逐次的な入れ替えで行なっていく。

これで新基準以降のABC-Dについて考察だけは終了。
500点以下は結構安定して解法にたどり着けるようになってきた。
実装してないけど。

2019-03-04

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列。
実装ダルそう。

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

もっとも左ともっとも右について調べればわかるが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はなんだかとても久しぶりなきがする。

2019-03-01

ABC-D 79-86

実装する段階になって読み間違いに気づくことがしばしば。

それでも一応86以外は自力で解けたので良い傾向。

79
各数字について、最小コストの遷移を決めてやればいい。
ワーシャルフロイドでok.

80
si-0.5 -tiが最も多く重複する区間の重複度。
imos[10^5][30]

81
値が正なら、左の数字を右に足していけばいい。
負の時は？
左をより小さくすればいいので、右を左に足す。
後者によって前者で作った関係が壊れうる。
うるのでもう一周で2N回

最初のN回で符号を揃えてしまえばいい。
負に揃ったら右から、正に揃ったら左から処理でok

82
TとTの間のFを数える。
0回目と1回目の間、2回目と3回目の間、、、、を数えると、x方向に進めるパターンはそれらの和or差の組み合わせで全て生成される。setで管理。

最後の移動を処理するために、末尾に'T'を追加しておく。

83
n-1回でできるのは、一番左、一番右を好きな数にすること。
Kの場合、左右からn-K番目までは自由にできる。
よって問題は、それらの中間がどうなっているか。

数列の中心から見ていって、異なる数字が出るまでどれだけ広げられるか。
.....011111.....の場合、 ...0 1111 1...と分割。n-K=(n-4)/2
...0111111...で...0 11111 1....の場合も、n-K=(n-5)/2

84
10^5以下の奇数全てについてあらかじめ調べておいて、条件を満たすものをソートして格納した配列を作る。あとは各クエリに対して二分探索していくつ含まれるか計算。

85
振るのは最大のaiのもののみでいい。
そのaiをどのタイミングで投げるか。
bj>aiは投げて良い。ただし、biを投げることで回数が減るなら処理が必要。

bj全て投げで終わるなら、大きいものから。
終わらないなら、aiで適正回数殴ってから投げる。
ai殴りでHがbjの総和以下になったら投げに移行する。投げる順番はbjの大きい方から。

N 3^2だから全部試せばいいと思って書いている途中にN K^2と気づく。

O(N K^2)から落とす方法がいまいちわからず断念。

二次元累積和 https://img.atcoder.jp/arc089/editorial.pdf

2019-02-28

AGC-A 19-30

これでAGC-A終了。

f:id:cmat-comp:20190228002420p:plain

緑化進行中。

来週再来週末と連続してAGCがあるらしい。日程的にどちらもちょっと参加できないかも。

今週はどうなるんだろうか。また直前にABCがアナウンスされるのだろうか。

旅行中なので、移動時間にipadで考察だけメモ→落ち着いてから実装という流れを取ったが、問題文を勘違いしていたケースがちらほら。あと、まだint溢れとかよくやらかす。

019

2l引けるまで、最小金額で作って引き、、、という貪欲法

020

最初に後退する必要が生じた方が追い詰められて負ける
A-Bの偶奇

021

最初に9でない値になる桁と出会った時に、上位を一つ減らして残り全て9
最上位が9の場合、下位が全て9ならNそのもの、それ以外なら最上位減らして残り9

stringでchar to intミスってWA出した

022
sが26文字でない限り、使われていない文字のうちで辞書順最小を付け足せばいい。
26文字なら、next_permutationすればいい。
falseが返ってきたら-1を出力

入力例4のパターンがある。どうするか。
next_permuationしたものが元とずれるまで出力すればいい。

023
累積和を計算した時、和が0の部分列が存在すると、累積和の配列に同じ値が現れる。
それらを拾ってくれば答えは出るが、O(N^2)

mapを使って累積和の値を記録しておき、各値について登場回数をnとしてnC2を出して和を取ればいい。

200点にしては難しい。

累積和のint溢れでWA出した。

024
差は、A-B,B-A,A-Bを繰り返す.
あるkでの値は二つ前＊2+一つ前で求まるので、これでok

025
A, Bの値について全探索

026
左から逐次的に。
使用する色の種類は関係ないので、左隣と同じなら変えるでok
変更先は確実に重複のない値ならなんでも

027
ソートして小さい方から。
ちょうど配らないといけないあたりで微調整

028
最小公倍数っぽい
N、Mが互いに素なら自明
互いに素でないなら、最小公倍数で条件を満たせるか否か

具体的にstringを作ろうとすると長すぎてMLEspするのでmapで。

->WA, またint溢れミス。

029
要するに、隣接するW,BをswapしてWを左に寄せていく操作。
最終状態は必ず、WWW...BBBなので、Wを寄せるのにかかるステップ数。
左からi番目のWを配列の左からi番目の位置に移すのにかかるステップ数の和。

030
CBCB..と食べて、Bが無くなったらACAC..でAがなくなったら終了
min(C, B)=CならB+C
min(C, B)=Bなら2B+min(A,C-B)

一枚だけなら食べても大丈夫なので微修正。

cmat日記(競技プログラミングその他)

AtCoderはじめました (id: cmat)

400点問題埋め

ABC-Dの実装

AtCoder 300点問題

ABC-D 105-116

ABC-D 87-104

ABC-D 79-86

AGC-A 19-30