解いた問題へのコメント
ABC 062 D問題
コメント
よりシンプルな問題に分解してからそれらを組み合わせるといういつもの方針、というか思考の癖がうまくハマった問題だった。その分実装で苦しんだのは残念（一つ前の記事を参照）。
概要
長さ3Nの配列a[3*N]からN個の要素を取り除き、残った長さ2Nの配列を前半と後半に分ける。前半の総和 - 後半の総和が最大になるように取り除く時、この値はいくらか？
考えたこと
前半の配列と後半の配列が独立に決定できれば、「前半の総和 - 後半の総和」は前半の最大化と後半の最大化を行えばよいことになる。 前半を最大化することを考えた時、a[0] .. a[2*N-1] の要素をソートして最初のN個を取ってもいいが、ここは貪欲的に考えて以下のように求める。
- a[0] .. a[N-1] のうち最小の値a1_min と、a[N] の値の大きさを比べる。
- a1_min < a[N] ならa1_min を除く。するとa[N] は前半のN個の要素の中に入る。前半の総和はa[N] - a1_min の分だけ増加する。この総和をa1_sum[N] と書こう。
- a_min >= a[N] ならa[N] を除く。前半の総和は変わらない。
- 同様のことをa[N+1], a[N+2], .. a[2*N-1] まで繰り返す。最終的に得られた前半の総和は、要素の取り除き方に対して最大のものになっている。
- ちなみに、a1_sum[i] はa[0] .. a[i] の中からN この要素を選んだ時の総和の最大値になっている。
同様のことを後半の配列に対しても行い、結果をa2_sum に格納する。しかし、前半の配列と後半の配列は独立でなく、前半でa[i] を使ってしまった場合、後半ではj > i なるa[j] しか使えない。
前半でa[i] を使ってしまった場合の前半の総和の最大値はa1_sum[i], j > i だけを使った場合の後半の総和の最小値はa2_sum[i+1] であるから、i = N-1 .. 2*N に対してa1_sum[i] - a2_sum[i+1] を計算すると、これの最大値が答えとなる。
Submission #1746297 - AtCoder Beginner Contest 062 | AtCoder
ABC 075 D問題
コメント
これも問題を分解し、他のパーツとの結合を最小限にすることで計算量を抑えるという観点から考えて上手くハマった。とくにダイクストラとの類似が思いついた時は心の中でガッツポーズ。ただしO(N) でやるもっとうまい方法があったみたですね。ちなみに本番では優先度つき待ち行列を実装し終わったくらいでタイムアップです。
概要
1次元上を移動する点の問題。区間に対して制限速度と時間の長さが、全体を通して加速度の制限が与えられており、進んだ距離を最大化する。
考えたこと
区間内の制限速度は分かっているので、区間の境界の制限速度を求めることができれば、区間内の速度は簡単にもとまる。 境界の制限速度が何によって決まっているかを見極めなければいけない。一見すると隣接する区間の制限だけ分かっていればいいように思える。例えば、制限速度が100 の区間と80 の区間が隣り合っていたら、区間の境界では80 以下になっている必要がある。しかしこれで決まりではない。100, 80, 10 と並んでいて、80の区間がとても短かったら、100 と80 の境界では速度は80よりも大幅に遅くなくてはダメだ。80 と10 の境界でスピードを落としきれず脱線するだろう。
このことをナイーブに考えると、ある区間境界の制限速度を求めるには他の全区間からの影響を調べなければならない。また、ある区間境界の制限速度が更新されることで他の区間境界の制限速度にも影響するため、いたちごっこになってしまう。
ここで、ある区間境界が影響を受けるのはより制限速度が遅い区間境界であることに注目する。最も遅い区間境界から制限速度を確定させていくことで、このいたちごっこを避けることができる。つまりダイクストラの要領である。 ダイクストラのように優先度つき待ち行列を使って区間境界の最低値を管理してもよいが、区間を全て走査してO(N2) で解いても間に合う。
Submission #1723275 - AtCoder Beginner Contest 076 | AtCoder
