naoya_t@hatenablog

いわゆるチラシノウラであります

〈企業コン埋め〉CODE FESTIVAL 2018 Final

CODE THANKS FESTIVAL と CODE FESTIVAL の違いって何だ?

リクルートさん主催のコンテストで

  • 予選(A, B)があって、上位100名(Aから60名+Bから40名)が出れるのがCODE FESTIVAL
  • CODE FESTIVALに出れなかった中から上位100名(Aから60名+Bから40名)が出れるのがCODE THANKS FESTIVAL

かな。
(今年で5年目らしいのだけれど毎年スルーしてる)

というわけで
粛々と埋めていきます
CODE FESTIVAL 2018 Final (Parallel) - AtCoder

A – 2540 (300)

  • 各駅から距離xで繋がる先のリスト、を vector>> で持っておいて、
  • 路線ごとに、Ai側で2540-Liな先、Bi側で2540-Liな先の数を数える
    • 但しLi=2540/Liの時は重複するのでそれぞれ-1
  • 同じのを2回ずつ数えてるはずなので、合計を1/2したのが答え

→AC
https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3690737

解説解では

駅bを固定して解いてた

B – Theme Color (300)

  • 100000までのfactorialのlogを用意しておいて(単なる累積和)、
    • そうすると log(nCk) がO(1)で求まる
    • あとは組み合わせの数をlogで計算しておいてlog10にしてfloorを取ったののabs

→AC
https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3690862

C – Telephone Charge (300)

  • (Ai,Bi)のリストを作ってソートして二分探索
    • 最初のAi以下: 最初のBi
    • 最後のAi以上: 最後のBi + (T[i] - 最後のAi)
    • それ以外: min(前のBi + (T[i] - 前のBi), 後のBi)
  • 一応long longで取ったけど要らないかも

→AC
https://beta.atcoder.jp/contests/code-festival-2018-final-open/submissions/3691032

(続く)

-