AtCoder Beginners Contest231感想

ABC231に出たので各問題で考えたことをメモってみます。

A問題

答えに小数点が出てくるので、変数はintじゃなくてdoubleで用意。

B問題

map型を使った。候補者の名前をkeyにして、それぞれカウントしていき、最後に全部の候補者の名前を調べて最も票の多い人を出力。

C問題

まず生徒を身長順にソート。各クエリについて二分探索を行い、答えを求める。

D問題

とりあえず図を描いてみる。すると、1人につき隣り合わなければならない人が３人いると並ぶことは不可能だとわかる。(例えば④の人が①②③の人と隣り合って一列に並ぶ方法はない。)
これで提出、、、と行きたいところだが、D問題でこんなに簡単な条件なわけがない。もう少しプログラムの粗探しをしてみた。
すると、ミスが見つかった。①と②、②と③、③と ①がそれぞれ隣り合って一列に並ぶ方法はない。これは先ほどの条件は破っていないが、並ぶことはできないのである。よってこの条件もプログラムに追加。
これでAC。

実際には、これらはグラフを使って考える。１つ目の条件は、「１つのノードに別のノードが３つ以上隣接していたらアウト」というもの。２つ目の条件は、「グラフにループが１つでもあればアウト」というもの。
２つ目の条件については、UnionFindという便利な構造を使うと一瞬で判定できる。

E問題以降

う～ん。。。難しい。わかりそうでわからない。。。
来週中に解き直して精進します。