2021/1/2に開催されたコンテストの感想
あけおめ
AtCoder Beginner Contest 187
A
3桁の2数の桁和のうち大きいほうを出力せよ 等しければ前者のものを出力せよ
- 出力制約として書いてあったけど後ろ部分は完全に無意味
- ans += X mod 10, X /= 10を繰り返して桁和が出る
- max(digitsum(A), digitsum(B))
B
N点のうち傾きが-1以上1以下のペアはいくつあるか
- 制約的に全部の組み合わせを試していい
- 各座標の差dxとdyの絶対値を比較してdx>=dyならok
C
N個の文字列のうち'!'をつけてもつけなくても自分含むどれかと一致する文字列があれば1つ出力せよ
- !始まりとそうでないのに分ける
- setに入れる
- !グループにもそうでないグループにもあるのがあったら吐く
D
各町の青木派と高橋派の人数が与えられる。演説に行った町の民は全員高橋に、そうでない町の民は青木派のみが青木に投票し、高橋派は何もしない。高橋が過半数の票を得るにはいくつの町に演説に行けばよいか
- 演説に行かない場合から考える
- 行くと高橋-青木は2高橋+青木票増える
- これが大きい順に訪れるのが最適で、この順にsortして試す
E
木がある。辺を指定し、片方の頂点から他方の頂点を経由せずたどり着ける頂点全部にxを足すクエリを処理し、最後に各頂点について足された数の和を答えよ
- 解けなかった。みんな解いてた。
- 根付き木としてみてよくて、最後にbfsかなんかして累積和を取る方針が強そう
- LCAをみて、経由したくない点が深い位置にあるときは根に+xして経由したくない点に-x
- 経由したくない点が浅い位置にあるときがわからなかった。そもそも辺指定を忘れて2頂点だと思ってた（誤読。きつそう）
- 根から-xして経由する点から+xして最後全体に+x…は違う
- +xする頂点をずらしたいので経由したくない点の子を全探索…はTLE（特にウニ）
- 経由したい点に+xするだけでいいですね。
F
完全グラフの森になるようにグラフから辺を削除したときの最小連結成分数
- 解説AC
- 制約小さいので指数っぽいかな
- 部分集合が欲しくなるからbitDPっぽい
- 完全グラフになる頂点集合のみ1で初期化したテーブルを下から埋めていく
- dp[S] = min(dp[S-T]+dp[T])って感じ、雑な記法だけど
- 部分集合を探索するfor文の書き方があり、計算量も4Nでなく3Nに落ちるらしい（なんでか考えてないので考えたい）
Dまでが割といい感じに行ったぶんEのストップが悔しい。てかABが若干むずかったよ今日
