ABC256(東京海上日動コン) 参加記

82:24 7完でひさびさに成功!

パフォはカンスト相当です、やったね

テストで忙しくてあんまり精進できてなかったのにどうして??

 

 

A 2^N

マイルドなAですね、(1<<N)でOK

(AC 1:13)

 

B Batters

最初、料理で使うバターだと思って???になってました

n塁(0 ≦ n ≦ 3)にいるか?を管理してもいいです

が、ちょっとめんどくさいので100塁とか1000塁まであることにしてもよいです

こうすると4塁以上にいる人たちの数を数える問題になり場合分けがいりません

1000塁もある野球、マジで終わらなそう

(AC 4:17)

 

C Filling 3x3 array

こういうの地力勝負になりそうですき

制約が小さいのでいいかんじに全探索すればいいかな~と思います

左上の4マスを決めてあげると、あとは自動的に決まるので条件を満たすか判定すればよいです

解説読むとDFSでもできるよ!って書いてあって賢いなって思いました

(AC 10:45)

 

D Union of Interval

マジで今までに何回も何回も出会ってきたので秒ですね

左端でソートして貪欲にくっつけていけばいいです

制約が実は小さい(みてなかった)ので、imos法で解くこともできるらしいですね

(AC 15:29)

 

E Takahashi's Anguish

初手で「Anguish」の意味を検索します(は?)

苦悩っていう意味らしいので、高橋くんが悩んでるんだな~と思いながら問題を読みます。たしかに困ってそう

こういう問題は有向グラフに落とし込むのが典型的で、閉路になっているところをうまくすればいいとわかります

で、1頂点から1本しかでないいわゆる"functional graph"なので、「サイクルは1つだけになってくれ、頼む、Eだし」と信じます

実際そうなんですが、確信するほどの証明を考えるのが大変そうだったのでとりあえず書いて投げることにします

サイクルが1つなら、その中で最も不満にならない人を選べばいいので、SCCをして強連結成分ごとの最小値を加算すればよいです

投げると無事通りました、よかったね

この問題見ると、不満を感じにくい優しい人が損する世の中なんですね悲しい

(AC 22:44)

 

F Cumulative Cumulative Cumulative Sum

いかにもセグ木で解いてくださいという見た目なんですが、更新がけっこういろいろ影響するので困ります

書き換えた箇所がK個あるとすると、Dxの計算時にK個見るとなんとかなりますが、これを愚直にすると間に合いません

これは... 平方分割か!?と思ってTLを見ますが普通に2sです(平方分割想定なら4sくらいありそう)

ただ、考えても何も思い浮かばないので定数倍に気を付けながら平方分割をすることにします

 

平方分割の手順は以下です(これを√Qごとに繰り返します)

1. 普通にDを計算する

2. クエリを処理する

  a. t = 1なら、今のaiとの差を記録して、aiを更新する

  b. t = 2なら、そこまでのt=1クエリを全部チェックして差分を更新する

 

こうすると、bでのチェック回数が高々√Qになるので、O(N√Q + Q√Q)で解けます

入出力高速化も不安なので入れておくと、880msで通りました

atcoder.jp

 

解説見たら難しそうな数学をしてました、まあ言われるとそうなんだけどね

(AC 49:47)

 

G Black and White Stones

ここまでいいペースなのでせっかくなら解きたいなと思って考えます

それぞれの辺の端が結構影響するので、

「両方白」「片方白で片方黒」「両方黒」で場合分けしたりしようとしますが、Nが大きすぎるのでうまくいきません

Dが小さいので、1辺に使う白い石の数を固定するという方針はそれなりによさそうです

よく考えると、これは円環の構造になっているので、最近何回か出ている「はじめの状態を持つ」DPが使えそうだとわかります

 

ここまで気づくと、あとはこの手のDPをNが大きいときに解くのは行列累乗が向いているので、それを採用します

dpi,j,k = 今i番目の辺をみていて、その左端がj色、最初の頂点がk色(j, k = 0,1)

というDPをたてて、あとは丁寧に遷移を合わせると解けます

(AC 82:24)

 

総括

Fで犯罪ACしたおかげで、Gがうまくいった!

賞金当たってくれ~~~