ayu

たまたまProblems開いたら

最早セグ木バッティングセンターと化している

問題文に書かれている操作を愚直に繰り返して、
・同じマスに止まったらそこで打ち切り
・1800msを超えてもまだ打ち切られていなかったら答えをNにする
が通った(犯罪)
atcoder.jp/contests/abc...

Nマスのすごろくがあります。
i番目のマスには数Ai(0≤Ai≤N-i)だけが書かれているサイコロが置かれており、サイコロを振って出た目のマス数だけ進めます。
k=1,…,Nそれぞれについて、以下の問題に答えてください。
・高橋くんはk番目のマスをスタート地点として、このすごろくを始めてしまいました。サイコロを振った回数が10^100回に達したとき、高橋くんがいるマスを答えてください。

みたいな設定だったらすぐ気づけたかも

Bが大嘘すぎる(k=(m-|Si|)/2です)

E 各素因数について指数が1番目に大きいものと2番目に大きいものを保持しておき、基本的には1番目のもの、Aiによっては2番目に大きいものを使えば最小公倍数が求まる
毎回1から線形篩をしていたらMLE+TLEだったので、仕方なく全テストケースのAiの最大を取ってきて線形篩して使い回したら許された

F 各移動回数ごとのコスト総和の最小値を保持したいので、行列の積で、いつも掛け算しているところをコストの総和に、いつも足し算(集計)しているところを最小値採用に置き換えると、行列累乗でK回移動が求まる
↑演算を置き換えるためにめちゃくちゃに破壊された自作行列累乗ライブラリが泣いてますよ

D 各操作で分割したチョコは分割する前のチョコと幅か高さのいずれかが一致する
そこで、HxWのチョコをもう1つ買ってきて、以下の操作をチョコが無くなるまで繰り返す
1. 机の上から、今持ってるチョコと幅または高さのいずれかが一致するチョコを選ぶ
2. 選んだチョコと同じ大きさで、今持ってるチョコからむしりとる
3. 選んだチョコとむしり取ったチョコを食べる
答えの座標は(1,1)で初期化しておいて、操作2のタイミングでxまたはyをずらしていけば良い

ABC445 ooooo(3)o-

A s[0]==s[^1]

B k=m/2

C 問題文を凝視すると「i≤Ai」という条件が隠れているので(隠れてはいない)、移動は必ずi=Aiを満たすどこかのマスで止まることが分かる
よって移動が止まるマスから逆方向にDFS

C#で提出を検索するとよく見かける人がABC Writerになってる

解説チラ見したら2^Nって書いてて終了

AIさん部分集合DP出してくるのか……

コンテスト後に「もしかしてテストケースもAIが準備してるなら強いケースは入ってないのでは」と思ってEに部分和DP投げたけど普通にTLEした
AI舐めてすみません

残りを見た

A 111の倍数ならYes

B 全部試す

C これratedで出てたら間違いなく死んでた
折れずに残っているものがあるとすると、AのmaxがLの候補
全部折れているとすると、Aのmaxとminの和がLの候補
で、実は候補はこれだけっぽい

F 「中央値を固定したときの判定問題 解いて」「わ わかんないっピ…」

ABC444(unrated) ---oo--

D 筆算するイメージで、下の位から繰り上がりを保持しながら計算する

E 条件を「昇順に並べたときに隣り合う2要素の差が全てD以上」と言い換えて、現在見ている区間の要素をmultisetで管理しながら尺取り

今日は妙に心がざわざわして落ち着かないのでいつでも止められるようにunrated予定

いつ見ても「> 2000 ms」の表記が無性に腹立つからスクリプトで書き換えた方がいいな

F 「Nで割った余り」と「最後に決めた下位桁」のペアで遷移元を保持しながらBFSして、なるべく早く余り=0になったペアから遷移元を逆走すればいいと思ったんだけどTLE+WA

ABC443 ooooxx-

A いつもこれくらいのAがいい

B N=1,K=10^8でも愚直シミュレーションが間に合うことを確認

C 青木君が通った時間がblueskyを開く時間を超えていたら答えに加算、を繰り返す

D 「各駒は、現在位置か隣の駒の1行下にあれば良いよね、たぶん」を左から順に決めるのと右から順に決めるのを両方試したらなぜかACする(最悪)

E ずっとF見てて後回しにしたせいで間に合わず
到達可能なマスの壁は無かったことにしていいと思うんだけど、その情報をmultisetで雑に管理したらTLE

Eは64bit整数を分母分子にもつ自作の有理数ライブラリを使いました...

Dの公式解説がセグ木じゃなかったので、AtCoder社の方角に向いて謝罪

ABC442 oooooox

F 「どの行まで塗り分けを決めたか」「現時点で白は左から何列目までか」をキーに持って一旦DPを書くとO(N^3)になってアンハッピー
ここで「現時点で白は左から何列目までか」を配るDPではなく貰うDPで考え直すと、貰う元を降順に累積していけば良さそうなので、書き直すとO(N^2)になってハッピー

G 重さ3のアイテムの個数を決め打ちして三分探索か…？と思ったけどまとめきれず

E めっちゃ大変
点の位置をx軸・y軸・象限に従って8グループに分類し、時計回りにグループを横断しながらカウントしていく
軸上のグループは個数そのままでOK
象限上のグループは有理数x/yを考えると時計回りに昇順で管理できて、個数が二分探索できるようになる
モンスターAjとBjが同じグループなのに時計回りでは反対になるケースとかは、グループの横断開始とかをフラグに持って気合いで頑張る

A タイトルで「Countメソッドを使いましょう」と教えてくれてありがとう

B 音量が2*10^5-1になっているとは知らずにAi=3をする高橋くん

C N-(著者)-(著者と利害関係にある人数) を使って計算すればよく、真の敵はオーバーフロー

D セグ木の浸透化が深刻！

配達員さんクソ寒い中ありがとう

おかえり1600💢

自作の拡張機能で結果ラベルを書き換える際、「MLEとか滅多に出ないでしょ」と決めつけて文字列をめっちゃ長くしていると、コンテスト中に表がぶっ壊れてびっくりするので気をつけましょう

その上で、ある1つの商品iについて以下をそれぞれ考えて、本来の最大価値を実現できるか調べる
選ぶ場合→(①と②を合わせてM-P[i]円以下での最大価値)+V[i]
選ばない場合→(①と②を合わせてM円以下での最大価値)
ただし「①と②を合わせて」は愚直に判定するとO(M^2)で厳しいので、②の方は「◯円になる最大価値」を「◯円以下になる最大価値」としてまとめておく
(N*Mの配列を3つ使ったらMLEだったので、渋々2つにした)

D 22:15頃に順位表を見たら全人類通してたので仕方なく考え直すと、(出次数)^(経路の長さ)=4^10なんだからDFSで良くないか、と我に帰り、AC

F ある1つの商品iについて、それを選ぶ場合or選ばない場合を調べたい
そのためには商品i以外の選び方は最適化しておく必要があるので、商品1,2,...,Nを商品iを境目に分割するイメージを考えると、以下の情報があれば良さそう
①商品1,2,...,Nの順で選び方を決めるDP
②商品N,...,2,1の順で選び方を決めるDP

E (Aの個数)-(Bの個数)を考えたいので、まず(A,B,C)を(1,-1,0)に置き換えて累積和Dを取ると、部分文字列[l,r)における(Aの個数)-(Bの個数)がD[r]-D[l]で計算できる
条件はD[r]-D[l]>0ということなので、rの昇順にD[l]<D[r]となるlの個数を調べればよく、これはセグ木(と座標圧縮らしきもの)で求められる