naoya_t@hatenablog

いわゆるチラシノウラであります

AtCoder Grand Contest 026

7/14 21:00-23:30

oxo---
2完パフォ1885
レーティング1743→1759(+16)
Bも通したかった
f:id:n4_t:20180715001942p:plain:w500

A - Colorful Slimes 2 (200)

RLEして(RLEのスニペット今日使ったばかりだった)、塊ごとに長さの半分(切り下げ)個変色すればいい
→AC
https://beta.atcoder.jp/contests/agc026/submissions/2841603

解説解も同様

B - rng_10s (600)

場合分けして行って
→WA(1)
https://beta.atcoder.jp/contests/agc026/submissions/2843485

(先にC問題を通して)

C<Bのときに[C+1,B-1]のエリアに陥ると死ぬ、って所の計算がちゃんと出来てなくて
→ WA(2)
https://beta.atcoder.jp/contests/agc026/submissions/2845626
https://beta.atcoder.jp/contests/agc026/submissions/2846547
愚直なシミュレータを書いてランダムなデータを投げてみて、自分のコードが間違ってるのは分かるんだけど
gcd持ち出して使ってみるけど計算あわない…(頭が回ってない)

解説読む

以上より、この問題は次のように言い換えられます。
・A からスタートして、D を足していく。個数 mod B が C を超えることはあるか?

そこまでは分かっているのです...

A からスタートして、D を足していくとき、個数 mod B の最大は,g = gcd(B, D) として B−g+(A mod g)
となり,これを C と比較すればよいです。個数 mod g が常に一定であることを考えるとこれが上界であるこ
とは言え、また,(B/g − 1) × inv(D/g, B/g) 回 D を足したときにこの上界が達成できます (inv(X, Y ) は,
X × inv = 1 mod Y なる値とします)。

なんでこれが言えるんだろう…(頭回らないから寝て起きてから考えよう)

起きてから

コード見返す
あれ
なんか要らんことしてる行がある
g=gcd(h=d%b,b)をhに代入しちゃってるからこれだとh/g==1になるじゃんダメじゃん
そこ消したら通った

https://beta.atcoder.jp/contests/agc026/submissions/2850749

解説を改めて読む

大体同じなんだけど、視点がちょっと違う
・自分の解:A mod Bから gcd(D%B,B)=gcd(D,B) をk回足して [C+1, B-1] の区間内のどこかにたどり着けるか調べている。gcd(D,B)を使うのは、剰余環の取りうる場所がgcd(D,B)間隔(互いに素ならすべての場所に行ける)だから
・解説解:(A mod B + k・gcd(D,B)) mod B の最大値がC+1以上かどうかを調べる
解説解の式からだと自分は分かりづらかったんだけど、上から見るか下から見るかの違い。

教訓

焦るな

C - String Coloring (600)

先にこちらを
真ん中で左右に分けて考えられるか?
左の色分け全パターンをなめても18×2^18で、それをmapに入れてもO(N 2^N logN)
mapを使うのは、各パターンがいくつずつあるかを数えておくため
右も同様に(左右逆順で)同じことをやって
左の全パターン(2^N)について、(左赤 左青)のreverseパターンが右にもあるかを同様のmapから引いて個数の積を取って合計していく(ここもO(N 2^N logN))
→AC
https://beta.atcoder.jp/contests/agc026/submissions/2844755

解説解も同様

D - Histogram Coloring (1100)

開いた
左から考える

  • 任意の縦の並びは隣りにその色反転パターンを置ける
  • 縦に交互にoxoxox..と伸びるやつは隣りに同じパターンも置ける
  • どの2x2にもかからない箇所は任意(なので答えがx2)
  • これで左から遷移していったら計算できる?

って辺りまで考えてBに戻った

解説ちら見した

下から考えるべき

E - Synchronized Subsequence (1600)

開いた
考えてない

F - Manju Game (2000)

開いてない