Toy と帽子と ADP BE

主にプログラミングに関わる話をゆるくエモくやっていきます

第三回日本最強プログラマー学生選手権-予選-(ABC262)

3完。19:12。

各問題

A - World Cup

4で割った余りが0のときY+2、1のときY+1、2のときY、3のときY+3です。自分は安全にif-elseで4通り書きました。

B - Triangle (Easier)

どの辺が連結しているかをmap<int, set>で持って全探索しました。

C - Min Max Pair

条件を満たすのはa_i = i and a_j = ja_i = j and a_j = iのときです。

前者は、まずa_i = iとなる場所についてiまでにいくつあるかを累積和で求めておきます。a_i = iとなるiに対してiより大きい場所にa_j = jとなるjがいくつあるかが先ほどの累積和でわかります。

後者はa_i > iのときa_a_i = iかどうかをチェックすればよいです。

D - I Hate Non-integer Number

TLE解しか書けず...。(再帰しました

あー、DPかー。DはDPのD...。なぜか今回はDPが全く考えに浮かばず...。

まとめ

DのDPが思い浮かばないのやばい。