blog.bouzuya.net

2022-06-18 AGC016 の B を解いた

AGC016 : AtCoder Grand Contest 016 の B を解いた。

  • B - Colorful Hats https://atcoder.jp/contests/agc016/tasks/agc016_b
    • 提出: https://atcoder.jp/contests/agc016/tasks/agc016_b
    • 解説 AC
    • 解説動画 https://youtu.be/kdQtQSgIYPI?t=1350 の頭の数列を求めるには……が大切だった
    • 数列は全体の色数からそれを除くことで色数が減るなら色数-1そうでないなら色数として求められる
    • 全体の色数を A とする
    • a_i は A か A-1 しかない → MAX(a) - MIN(a) > 1 なら No
    • MAX(a) - MIN(a) = 0 なら「それを除いても色数の減るものがない」
    • 各色は 2 匹以上に被られている
    • 全体で一色なら a_i = N-1 そうでなければ 2 * a_i <= N
    • MAX(a) - MIN(a) = 1 なら「それを除くと色数の減るものがある」ので
    • a のうち MIN(a) と一致する個数が 1 匹だけに被られている (除くと色数の減るものの個数)
    • a のうち MAX(a) と一致する個数が 2 匹以上に被られている (除いても色数の減らないものの個数)
    • 前者を COUNT_MIN, 後者を COUNT_MAX とする
    • MAX(a) は減らないものの個数なので色数 A = MAX(a) になる
    • 2 匹以上に被られている「色数」は A - COUNT_MIN で求められる
    • COUNT_MIN < A かつ 2 * (A - COUNT_MIN) <= COUNT_MAX
    • usize を使ったので 2 * A <= COUNT_MAX + 2 * COUNT_MIN とした

ABC256 に参加した (https://atcoder.jp/users/bouzuya/history/share/abc256) 。 1174 (-20) で水復帰ならず。 B でハマって慌ててしまった。 D でもったいない WA を出した。 E はもうすこし時間があれば解けたと思う。

近所の風呂屋に行った。想像はしていたけど子どもを連れて……は厳しい。

今日のコミット。