A. Snowball

問題文に書かれている処理をそのまま実装． 解答例

B. Squares and Segments

解答例

横幅および縦幅を広げてしまうと必要なSegment数が増えるため，なるべく正方形に収まるようにするのが最適．対称性より横幅$\ge$縦幅とする．すると横幅は$n$個以上入る正方形の一辺$p$とすればよい^[1]．$p \times p \ge n$より$p \ge \sqrt{n}$となり，$p$は整数であるから$ceil(\sqrt{n})$が最適．縦幅は余り部分も必要であるから$ceil(n/$(横幅)$)$として求まる．

別解(editorial)

求めたい値は縦幅と横幅を$p$,$q$としたとき$\min{\{p+q\}} \text{ s.t. } p \times q \ge n$である．ここで$|q-p| \ge 2$は無駄：例えば$p=3,q=5$のとき15個までしか入らないが，$p=q=4$とすれば$p+q=8$を保ちつつ16個入れることが可能．$p=3,q=6$のときも$p=4,q=5$とすることで2個分得する．これは要するに先の「横幅および縦幅を広げると必要なSegment数が増える」に対応し，気持ちとしては「横幅と縦幅を近づけて正方形に近くしたい」という認識でよい気がする．

従って解は対称性より$(p,q)=(r,r)$または$(r,r+1)$という形に限られる．editorialでは$r=floor(\sqrt{n})$とした後で$(r,r),(r,r+1)$, さらに丸めについても考えて$(r+1,r+1)$も試している．$r$を$1$から$ceil(\sqrt{n})$まで動かして確かめても$O(\sqrt{n})$で間に合うし，この方針を採っている人が多い印象．

C. Postcard

解答例

とりあえず記号（とそれとペアの文字）を消去したもの$t$を考える．この文字列は必ず残るため，$|t|$が$k$より大きいとImpossible．等しければそのまま出力．小さければ記号の利用を考える．まず'*'があればこれ1個から任意文字数作ることが可能なため，適当な1つを$k-|t|$文字出して残りの'*'及び'?'を0文字にすればよい．無い場合は'?'を使う：$k-|t|$個以上'?'があればその数だけ文字を出現させればよい．足りなかったらImpossible．

最初書き直したときに「i番目を見ているとき，'*'がi+2番目にあれば～～」という処理を採用していたのだが，これは先頭がa*などのときに不発になる．

D. Sum in the tree

解答例

解法

editorialがよく分からなかったので自分流に書き換えてみた．よって誤りがあるかも．

求めるべき値が$\sum a_i$の最小値であるから，$a_i$の値はなるべく増やしたくない． まず偶数深さの葉$i$については$a_i$を何にしようが他の頂点に影響しないため，素直に$a_i=0$とできる．

葉でない場合はどうするか．ここで頂点$i$の親を$p$, $i$の子を$c_1,...,c_k$とする．いま$s_i = s_h + a_i$, $s_{c_j}=s_i+a_{c_j}$である．$\sum a$を最小化したいという要請に合わせて変形すると$a_{c_j} = s_{c_j} - s_i = s_{c_j} - s_h - a_i$．前2項は奇数深さゆえ所与であるから，$a_i$の値を決めれば$a_{c_j}$も決まる，すなわち$a_i$の値に応じ$i$のすべての子について値$a_{c_j}$が変化する．$a_i$を1増やすと$a_{c_j}$が1減るから，$\sum a_{c_j}$が$k$減ることとなる．よって$a_i$をできるだけ大きく取って損することはない（$k \lt 1$，すなわち$i$が葉の場合を除くが，これは先に議論した）． $a$の各要素は0以上であるから，$a_i$の最大値は$a_{c_j}=0$が現れるときであり，$a_i=\min\{s_{c_j}\}-s_h$となる．構成不可能な場合はこれが0未満になってしまうか否かで判別可能．

気持ちとしては「$a_i$を小さく持ってしまうと，子らが$s_{c_j}$を再現するために各$a_{c_j}$にその分を持たなければならず，$\sum a$が増大する．よって$a_i$で出来るだけ負担してあげる」という感じ．

実装はDFSでよい．奇数深さ頂点の場合は$a_i = s_i - s_h$の左辺がすべて所与であるからこの式で求まる．偶数深さ頂点の場合は先に述べた処理をそのまま行えばよい．

もう少し簡潔な考察？：$s_i$が取れる値の範囲に着目すると$[s_h, \min\{s_{c_j}\}]$ となる．対応する$a_i$の値は$[ 0, \min\{s_{c_j}\} - s_h]$．先の議論から$a_i$は大きいほうがよいので右端を採用．

---

1. 横幅,縦幅を$w,h$とする．$w$が$p$未満であるとするとき，$w \ge h$であったから$wh \le ww \le (p-1)^2 \lt n$（$\because$ $p$の定義$(p-1)^2 \lt n \le p^2$）となり$n$個入らない．反対に$w$が$p$より大きいときを考える．$w=p$のときの$h$が$q$であるとすると，$w=p+1$のときの$h$は$q$以下になる（$\because$ $n \le pq$, $n \le (p+1)h$より$q=ceil(n/p)$, $h=ceil(n/(p+1))$）から縦横の差が広がって正方形から遠ざかる． ↩︎