AtCoder Beginner Contest 185 B,C,E,F 問題メモ

AtCoder Beginner Contest 185

B - Smartphone Addiction

• 高橋君のスマートフォンのバッテリー容量は $N$ [mAh]
• スマートフォンを満充電した状態で時刻0に外出し、途中で $M$ 回カフェを訪れ、時刻 $T$ に帰宅する
• $i$ 回目に訪れるカフェには時刻 $A_i$ から時刻 $B_i$ まで滞在する
• カフェ以外にいるとき以外は時刻 $0.5,1.5,2.5,...$ を迎える度にバッテリー残量が1[mAh] ずつ減少する
• カフェに滞在している間は時刻 $0.5,1.5,2.5,...$ を迎える度に1[mAh] ずつ増加する。ただし $N$ [mAh] 以上にはならない
• 途中でスマートフォンのバッテリー残量が0になることなく帰宅することができるかを判定せよ
• $1 \le N,T \le 10^9$
• $1 \le M \le 1000$

リチウムイオン電池は表記上の残量が0になっても体温で暖めたらほんの少し回復する。冬の寒い時期は特に有効。

それはともかく、時刻ちょうどにカフェに出入りしたときや、ちょうど0でカフェに着いたときの成功失敗の混乱を無くすためか、電池の増減時刻が0.5となっている。

プログラムの実装上は、これを0.5切り落とした時刻と解釈して、「ちょうど $t$ にカフェに着いたら電池は減らない」「$t$ にカフェから出たら減る」と解釈した方がやりやすい気がする。

出発
A1       減る
B1 - A1  増える
A2 - B1  減る
...
BN - AN  増える
T  - BN  減る

「減る」ときに0以下にならなければOK。ちょうど0になるのはアウト。

最初と最後を忘れないように。

Python3

C - Duodecim Ferra

• 長さ $L$ の棒を、各長さが整数になるように12本に分割する
• 分割の方法が何通りあるか、答えよ
• $1 \le L \le 200$

問題名はラテン語で「12の鉄」？

ARCの中～後半などの数えあげでは問題をこのような問題に帰着させることが解法の一端となることもある、教育的な問題。

なかなか一からこれを導き出すのはヒラメキが必要と思うが、

• $a_1+a_2+a_3+ ... a_N=L$ となる $a_i \le 0$ である数列 $a$ の作り方は、${}_{L+N-1}C_{N-1}$

というのが成り立つ。

• 重複組合せの公式と例題（玉，整数解の個数） | 高校数学の美しい物語

今回は各棒の長さは1以上ないといけないので、あらかじめ12本に1ずつ配って、残り $L-12$ を振り分けるとよい。

Python3

E - Sequence Matching

• 長さ $N$ の整数列 $A$ と、長さ $M$ の整数列 $B$ が与えられる
• 長さが同じになるように、双方から要素を削除する
  • 1つも削除しなくてもいいし、全て削除してもよい
• 「双方から削除した要素数の合計」を $x$、「削除した結果、$A'$ と $B'$ で異なっている箇所数」を $y$ とし、$x+y$ の最小値を求めよ
• $1 \le N,M \le 1000$

レーベンシュタイン距離というのがあり、今回の問題と概念が近い（というか説明は異なるが結果的にはそのもの）。

• レーベンシュタイン距離

以下のDPを使う。整数列 $S$ の先頭 $i$ 要素を $S_{1～i}$ と表現する。

• $DP[i][j]=$ $A_{1～i}$ と $B_{1～i}$ からなる整数列から計算した $x+y$ の最小値

$i,j=0$ の時は空とする。

すると、片方が空の時は全部消すしか無いので、以下は自明に決まる。

A\B|  -  1  3  1
---+------------
-  |  0  1  2  3
1  |  1
2  |  2
1  |  3
3  |  4

ここで、「$S$ と $T$ の最良な結果」とは、$x+y$ が最小になるようにした場合に残った整数列 $S',T'$ を指すとする。 説明のための概念であり、何かしら存在していることがわかれば、その具体的な形はわからなくて問題ない。

$A_i$ と $B_j$ が同じ場合は、$A_{1～i-1}$ と $B_{1～j-1}$ の最良な結果の後ろにそのまま残せばよい。

• $DP[i][j]=DP[i-1][j-1]$

$A_i$ と $B_j$ が異なる場合は、以下の4通りの選択肢があり、一番少なくなるものを採用すればいい。

• $A_i$ を消す
  • $x$ が1増える。$A_{1～i-1}$ と $B_{1～j}$ の最良な結果と同じになる
• $B_j$ を消す
  • $x$ が1増える。$A_{1～i}$ と $B_{1～j-1}$ の最良な結果と同じになる
• 両方残す
  • $y$ が1増える。$A_{1～i-1}$ と $B_{1～j-1}$ の最良な結果の後ろに、異なる要素をそのまま残す
• 両方消す
  • $x$ が2増える。$A_{1～i-1}$ と $B_{1～j-1}$ の最良な結果と同じになる

まぁ、両方消すのは常に両方残すより悪いので無視して、3つを比較すればよい。

• $DP[i][j]=\min(DP[i-1][j],DP[i][j-1],DP[i-1][j-1])+1$

Python3

F - Range Xor Query

• 長さ $N$ の数列 $A_1,A_2,...,A_N$
• 以下の $Q$ 個の2種類のクエリを処理せよ
  • '1 X Y': $A_X ← A_X \oplus Y$ で更新する
  • '2 X Y': $A_X \oplus A_{X+1} \oplus ... \oplus A_Y$ を出力する
• $1 \le N,Q \le 3 \times 10^5$

Fenwick木やセグメント木といえば、数列の累積和を更新しながら管理する方法が代表的だが、「累積XOR」でもできますよ、という問題。

いやまぁ、それだけの典型色強めな問題だけど、緑diffってマジですか。

Python3