naoya_t@hatenablog

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

AtCoder Grand Contest 027

9/15(土) 21:00-23:20
1完(200)
レートちょい下げ (1739→1718)

A - Candy Distribution Again (200)

小さい順に貪欲に
最後余りが出るとぴったりじゃなくなるのでN-1という以外は
→AC
https://beta.atcoder.jp/contests/agc027/submissions/3199592

B - Garbage Collector (700/400)

20分ちょい考えたけど
パス

C - ABland Yard (900)

  • ○A-B○
  • ○A-B-B'-A○
  • ○A-B-B'-A'○
  • A-B-B’-A’-A

みたいなのさえあればカバー出来る?と思って

  • 自分自身にループしているノード (A○, B○)
  • A-A'で隣接しているペア、B-B'で隣接しているペア

を中心に探していく実装が最後の12ケースぐらいがWA
AとBが逆になってるやつでカバーできていないとか?考えたけどそうでもなくて
残り16分ぐらいで、あ、○A-A-B-B-A-A-B-B-... で蛇のように蛇行して繋いでも行ける、と気づいて
これループ始まりでなくても閉路でも良いよねとか、閉路も四辺形だけじゃなくて(AABB-)の連続なら任意のサイズで良いよねとか
ようやく解くべき問題にたどり着いたのが残り十数分
(試合終了)

解説解は AABB の無限の繰り返し解法で、何だそりゃ?AABAA とかカバーできないじゃん、とか一瞬思ったけど
自分がやってたのと同じことだった(好きなように引き返せばいいわけだし)

  • Aに繋がる辺とBに繋がる辺を両方持つノード(A-[AB]-B)だけ残るように削っていったときに、全部消えるのであればNo、生き残りがあるならYes

は?
あああ
なるほど
グラフがどういう形をしているかなんかどうでもよくて

  • AAB(ないしABB)が存在する→単独では存在できないのでAもBもグラフに存在する(し、それぞれAAB, ABBである)
  • Aで始まる文字列:AABから始める。辺が示唆するとおり次にAが来てもBが来ても大丈夫。
  • Bで始まる文字列:ABBから始める。(略)

トポロジカルソートの要領で O(N+M) で行けるっていうんだけどちゃんと書けてなくてTLE連発(で寝落ち)

翌日、整理して書き直す。

  • N個のノードについて、Aに何本、Bに何本の辺をもっているかを保持する。
  • M個の辺について、辺の両端のノードについてそれぞれ(A,B別の辺の数を)インクリメントする。
  • A接続ゼロもしくはB接続ゼロなノードをキューに入れる。(このキューには消されるノードが入る)
  • キューからノードを取り出して、(未訪問であれば)そのノードから繋がる辺の向こうのノードについてデクリメントする
  • キューが空になったら終わり。全てのノードが消されてしまったならNo、残っているノード(それは必ず2つ以上だが)があるならYes

ようやく…TLEは取れたけどWA連発… s[i]=='A' と s[i] - 'A' が混在してた…orz
そこを直して
→AC
https://beta.atcoder.jp/contests/agc027/submissions/3210010


D - Modulo Matrix (1100)

見てない

E - ABBreviate (1300)

見てない

F - Grafting (1900)

見てない