【競プロ精進日記】AtCoder ABC157

2020.03.13
競プロ

1. はじめに
2. A
3. B
4. C
5. D
6. E
7. F

はじめに

当ブログは問題の解説がメインではなく、筆者の解法やアイデアの保存がメインです。
したがって、読者の期待に沿えないことがあると思いますがご了承ください。

A

A – Duplex Printing
\(\lceil N /\ 2 \rceil \)
https://atcoder.jp/contests/abc157/submissions/10426737

B

B – Count Balls
実装だるい（実装するだけ）
うまい方法あるかな？
https://atcoder.jp/contests/abc157/submissions/10431935

C

C – Guess The Number
無限にWAなので嫌い
制約が小さいので全探索
無駄に条件を先に整理するとバグらせやすいので、条件を保持してひとつひとつ条件に合うかを調べる方が安全
https://atcoder.jp/contests/abc157/submissions/10449876

D

D – Friend Suggestions
個人的にD>E、誤読したのもありますが。
各人について、連結している人数（友達の友達の友達の…）－連結している直接の友達もしくはブロックの人数－1（自身）が答え
連結している人数はdfsで色分けしてカウント
連結している直接の友達もしくはブロックの人数は同じ人を2重にカウントしないように注意（友達かつブロック）
そのため、連結している直接の友達もしくはブロックの人数＝連結している直接の友達の人数＋連結していて直接の友達でなくブロックである人数としてカウントした。
https://atcoder.jp/contests/abc157/submissions/10766660

E

E – Simple String Queries
文字種ごとの個数かと誤読しそうになったが、文字種の個数なので簡単。
セグ木を生やしましょう。
文字列の長さNのセグ木を生やして各要素は文字をビットに直したintを保持（a=00000000 00000000 00000000 00000001、z=00000010 00000000 00000000 00000000など)。
セグ木の演算は論理和をとることで、区間の文字種の個数が簡単にわかる（1の個数を数えるだけ）。
解説ではset使っててなるほどなとなった。
文字種ごとの個数なら26本のセグ木を植えるのかな～？
https://atcoder.jp/contests/abc157/submissions/10786203