naoya_t@hatenablog

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

〈企業コン埋め〉600点問題篇2019

企業コン500点が煮詰まってきた(まだ全部埋まってない)ので600埋めます

1/4(金)

SoundHound Inc. Programming Contest 2018 (春)

D - 建物

これは出場したコンテストで問題には見覚えがある
やるべきことは分かるのだけれど計算量をどう減らすか…

各フロアでの動作を分解してDPすることで計算量を減らせる。

  • ある地点から左に0個以上行って帰って得られる利得の最大値
  • ある地点から右に0個以上行って帰って得られる利得の最大値

これらは p_{i-1}-2f_i ずつ増やしていくステップで、1つ手前の結果からDP的に求められる。

  • ある地点から出る最後が右往復の場合の最大値:(その位置より左から入る、左往復)+おまけの右往復
  • ある地点から出る最後が左往復の場合の最大値:(その位置より右から入る、右往復)+おまけの左往復

これもDP
で、左と右の大きい方をその地点から出る場合の最大利得として次のフロアに持ち越す。

(サンプルケースで答えが合うまでが大変だった)
→AC
https://atcoder.jp/contests/soundhound2018/submissions/3926159
自力AC出来たけど80分以上かかってる…

解説読んだ

同様


天下一プログラマーコンテスト2016予選A

C - 山田山本問題 (600)

社員に山田さんと山本さんがいる場合にチャットで @yama まで打つと @yamada と補完されてしまうのをアルファベット順に細工して山本さんに有利にする問題。

  • 有向グラフ
  • トポロジカルソートする?
    • アルファベット順に互い違いに入れていくのなんかうまくいかなかった
  • priority_queueに放り込んでアルファベットの若い順に貪欲に取っていくか
    • 依存関係を解消しながら、依存ゼロになったやつをまた放り込んで*1

サンプルケースは通るようになったし投げてみるか
→WA(1)

2つの文字列を比較する時に、左が右のprefixになっている場合(同じ長さの場合を含む)は無条件に成立するから無視していいっていう条件がちゃんと入ってなかった
直して
→AC
https://atcoder.jp/contests/tenka1-2016-quala/submissions/3928406

解説読んだ

トポロジカルソートで解いてるわ

DFS を用いたアルゴリズムも広く知られていますが、この問題の場合は辞書順最小を選
択する必要があるため、入次数 0 の頂点から探索する類のアルゴリズム(Kahn's algorithm)
を用いると簡単に解けるでしょう。

はい
というかよく見たら自分のトポロジカルソートの実装が良くなかったので直して
再AC
https://atcoder.jp/contests/tenka1-2016-quala/submissions/3928466

*1:いやそれこそがトポロジカルソートのKahn's algorithmな気が