AtCoder Beginner Contest 225 (ABC225) に参加して， ABCD 4完の 1004 位でした．冷えました．

問題へのリンク

A - Distinct Strings

全部違えば6，2つ同じでもう一つが違えば3，全部同じなら1です．

B - Star or Not

最初の2行で共通している頂点を見つけて (無ければ No)， 他の全部の行にその頂点が入っているかどうかチェックします．

C - Calendar Validator

以下の条件をチェックします．

  • 行の先頭の値が 7 つずつ増える
  • 行内では値が 1 つずつ増える
  • 7 の倍数は，行末以外には現れない．

D - Play Train

各電車について，後と前の電車の番号を覚えておきます(無ければ-1)． クエリ1, 2 では O(1) で更新できます． クエリ3では，前の電車をたどって， 先頭に到達したら，そこから後の電車を順に出力していきます． 出力する電車の合計数が $10^6$ 以下なので，これで間に合います．

「これで間に合う」ことに気づかず，他の方法を探し続けて 時間を浪費しました．

E - フ

一応コードは時間内に書けたのですが，デバッグが間に合いませんでした．

直観的には次のようにすればできます．

  • i 番目の「フ」の下端と原点を結ぶ直線と，x軸とのなす角を b[i] とする．
  • i 番目の「フ」の左端と原点を結ぶ直線と，x軸とのなす角を e[i] とする．

すると，開区間 (b[i], e[i]) たちが交わらないようにたくさん取れ，という問題に なります．e[i] の昇順に並べ替えておいて，次のDPをします．

dp[i] = i 番目の区間まで見たときに，重ならないようにとれる区間の数の最大値

dp[i-1] まで決定したとすると， e[j] <= b[i] なる最大の j を二分探索で取って， dp[i] := max(dp[j] + 1, dp[i-1]) で dp[i] が決定できます． dp[N] が求める答です．計算量は O(N log N)．

実際には誤差が怖いので整数で計算します． 2つの半直線 (0,0) - (x1,y1) と (0,0) - (x2,y2) が x 軸となす角度の 大小だけ決定できれば良く，それは，x1 * y2 と y1 * x2 の大小を比較すれば わかります．