JOIOJI

JOI

Quiz

https://atcoder.jp/contests/joisc2014/tasks/joisc2014_h

公式解説

https://www.ioi-jp.org/camp/2014/2014-sp-tasks/2014-sp-d3-joioji-review.pdf

解説

f:id:peroon:20200226183025p:plain

  • サンプルの文字列に公式解説を適用するとこうなる
  • JO[i]==JO[j] かつ JI[i]==JI[j] の組の中で一番離れているものを見つければいい
  • 解説には「ソートして～」と書いてあるがここを補足しておく
  • 列ごとに構造体にする。例えば
struct Data{
  int jo;
  int ji;
  int index;
}
  • この構造体＋比較関数を定義する
  • 比較関数で jo, ji, index の順に大小比較すれば、上記画像で言う黄色の"0, 1"はindexの順に並び、ソートにO(N logN), 最長距離はO(N)で求められる
  • 参考コード https://atcoder.jp/contests/joisc2014/submissions/8932147

学び

  • 累積和の移項
  • ソートを最適ペア探しに使う

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～

追記：AC