パナソニックプログラミングコンテスト2021 (AtCoder Beginner Contest 231 - ABC231) に参加して，ABCDEF 6完347位でした．

問題へのリンク

A Water Pressure

D/100 を出力します．

B Election

map を使って 各名前の投票数を数え，その最大値を求めます． 書くのも愚かな間違いをして 1WA．

C Counting 2

ソートしておいて，lower_bound を使って 求めます．

D Neighbors

迷走したあげくにしょうもないコーディングミスで 1WA． サンプルが弱すぎる! と責任転嫁してしまいます．

Nノードで，$A_i$ と $B_i$ に無向辺を設定したグラフにおいて， 各連結成分が直線上になっていれば良い． 各ノードについて，辺でつながっているノードを vector で持っておいて， サイズが3以上のものがあったらNo．

ノードを端からなめて，vector サイズが1 のものがあったら， そこから直線状にたどれる辺を全部消す．

最後に全部の辺が消されていたら Yes．残っていたら No．

E Minimal payments

おつり，というのが問題文に出てくるだけで， ちゃんと解けないような気がしてしまいます．

$dp[x, k] = x$ を，$A_1$ から $A_k$ までの硬貨で表せる枚数，として， $A_k$ 円の硬貨を，$x$ 円以下のできるだけ多くの枚数を払う場合と， 1枚多く使っておつりをもらう場合の枚数の少ない方を取る， と考えて，dp の遷移が書けます． 実装は，$k$ ごとに map を使ってメモ化再帰をすれば良いです．

F Jealous Two

E よりは簡単な印象がありました．

$(A_i, B_i)$ を，まずAの降順，等しかったら Bの昇順 でソートしておきます． この順で見ていくと， 今までみたものと，今見ているもので喧嘩をしない組合せというのは， Bの方が，今見ているもので値が増えているもの，とすれば良いことが わかります．これはセグメント木で実装できます．反転数の数え方と似ています．

ただし，同じ値があるので注意が必要です．AとBの両方の値が等しいものは， ひとまとめにして考える必要があります．