naoya_t@hatenablog

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

AtCoder Grand Contest 028

10/13(土) 21:00-23:30
https://beta.atcoder.jp/contests/agc028/

1完(300)279位
1714→1749 (+35)
1完でレート上がるとか納得行かない...

A - Two Abbreviations (300)

2つの文字列S,Tがあって、それぞれの長さが|S|=N,|T|=M
ここから条件を満たす文字列Xが作れるか

  • |X|=L=k\cdot LCM(N,M)
  • 先頭から\frac{L}{N}文字おきに取るとS
  • 先頭から\frac{L}{M}文字おきに取るとT

割と愚直にシミュレート
ただし具体的に構築するだけのメモリはないのでmap<long long, char>に乗せる
O((N+M)\log N)とかそのくらい

→AC 8'17''
https://beta.atcoder.jp/contests/agc028/submissions/3392873

B - Removing Blocks (600)

N=7か8ぐらいまでシミュレートしてみて
スターリング数っぽいのが出てくる
ああこういうの無理
と思ってskip

C - Min Cost Cycle (700)

出口側と入口側に数字を持ってて、繋ぐ時に相手側との小さい方を接続コストとする感じで1つの輪を作る
コストのしきい値を決めて、それ以下のものとそれ以上のものを繋ぐ、みたいなのの二分探索的なのを考えたりしてたけど
終了

D - Chords

見てない

E - High Elements

見てない

F/F2 - Reachable Cells

見てない