はじめに
ABCの問題の解法を(Twitter以外で)残しておきたいと思って記事にすることにしました。そこまで大層なものでもない上に続くかもわからないです。言いたいこと(アドバイスとか)がある人は気軽にコメントしてください。
成績証：
A.First ABC
A,B,Cそれぞれが登場したかのboolを持っておいた。setの.size()で判定した方が簡単だったが、思いつかず。
B.Vacation Together
vectorに「その日までに連続で何日全員OKな日があるか」を持っておく。具体的には、s[0][i]~s[n-1][i]が全て'o'ならans[i]=ans[i-1]にし、*max_element(ans.begin(),ans.end())を出力。
C.Find it!
まず与えられるグラフが連結ではない場合について、各連結成分の辺数と頂点数が等しくなることから、各連結成分内に閉路を持つことが分かる。ということで頂点0から辿っていき、通った頂点を順に記録していく。すでに訪れている頂点に再び訪れたらそこから辿りながら出力する。
ans[i]が訪れた頂点の配列、閉路を見つけた時点でその番号をメモしていき、配列を最初から見てメモした頂点が出てきたら(この時点で閉路の長さもわかるので出力し、)そこからの頂点番号を出力した。
D.Grid Ice Floor
大まかな方針としてはstackを使ったDFS。ただ今回は進む方向に制限があるため、stackには{次に進むマスのpair,進む方向(0~3)}を入れる。また、それとは別に各マスを踏めるかどうかの配列grid(踏めるなら1,踏めないなら0,岩なら2)や、各マスの各方向について進んだかの配列gone(マス(i,j)から方向kに進んだならgone[i][j][k]=1)を持っておく。特にこのgoneがないとループがあった際に回り続けて終わらなくなるので注意。
最後にgrid[i][j]==1となるマスを数えて出力する。
ちなみにスタートから動けないコーナーケースのケアを忘れて2ペナしている。良くない。
コンテスト中に解けたのはここまで。
E.Defect-Free Squares
コンテスト中に考えたこと：
- サンプルケースから、正方形一つ一つを数えると解法だとTLEする
- 穴のないgridに穴を開けていき、「穴の開いていない正方形」の数が何個減るかを計算する？
- 包除原理っぽい？
- 実装分からん！
ということでコンテスト後に解説AC。公式解説があまりにも分かりやすすぎた。
感想など
- Dの実装が遅すぎた上に2ペナ出してるのは良くない。もっと早く書けていれば今回で入緑できたかもしれないのに……
- EがDPだということに気づけなかったのも良くない。
- でも「そのマスを右下隅とする穴の開いていない正方形の一辺の長さの最大値」を遷移させるのは思いつくわけないだろ
- 来週こそ入緑する！
