ABCDFの5完、1WA1RE。
各問題
A - Water Pressure
Dを100で割ればよいです。ちゃんと小数で計算することだけ注意。
B - Election
map<string, int>
を使って集計すればよいです。
C - Counting 2
Aはソートしておきます。xも先に全部受け取ってソートします。ここで、元の位置がわからなくならないようにpairとかを使って番号を一緒に管理することに注意です。
で、Aとxの列をしゃくとり法の要領で小さい方から大きい方に超える超えないを判定していけば、線形時間で解けます。
D - Neighbors
条件は大きく二つあります
- 1人に隣接できるのは2人まで
- 輪になってはいけない
前者は配列か何かでA, Bにおける出現数をカウントすればよいです。後者はUnion-findで判定できます。すでにマージ済みの2点をくっつけると輪になってしまいます。
後者の条件を抜かしてしまい、1WA。
E - Minimal payments
なにもわからない・・・。
F - Jealous Two
AとBをペアにして、Aの昇順でソートします。
高橋くんが青木くんにプレゼントするものを一つ選んだとき、そのプレゼントより右側のものが(そのプレゼントと同じAを持つ左側も含まれますが、そこは実装でうまくやる)、高橋くんがもらって嬉しいものになります。
この範囲の中で青木くんから見て嬉しいものを選べばよいのですが、これは最初に選んだ一つのB以下のBを持つものとなります。これはBITで個数を管理することができるので、容易に取ることができます。
実装としては、最初にBの個数をBITに全て入れて、プレゼントの配列を左からチェックしていって、すでに高橋くんが嬉しくなくなった(今のプレゼントより左側でAが小さい)もののBをBITからのぞいていく、という作業になります。
ただし、Bの範囲が広いので、座圧をする必要はあります。(座圧せずに投げて1RE)
まとめ
EでねばらずすぐにFをちゃんと読むべきだった・・・。Highestまであったかもしれずもったいなかったです。