A - Capitalized?
Regular Expressionがあればそれで一発？
シグネチャを決める。
import Data.Char
abc338a :: String -- S
-> Bool -- 答え
abc338a (c:cs) =isUpper c && all isLower cs
B - Frequency
シグネチャを決める。
abc338b :: String -- S
-> Char -- 答え
結果
配列で数える。
最頻の文字が複数ある場合に対応するため、最大個数を求めるステップと、その個数だけある文字を取り出す段階を分ける。
import Data.Array
abc338b :: String -> Char
abc338b cs = head [c | (c,k) <- assocs cnt, k == x]
where
cnt = accumArray (+) 0 ('a','z') [(c, 1) | c <- cs]
x = maximum $ elems cnt
個数を左、文字を右にした対の最大値を取り出すと、最頻の文字の中でアルファベット順で最も遅いものが選ばれてしまうので、個数をマイナスにして最小値を取り出すと唯一に決まる。
import Data.Array
import Data.Tuple
abc338b :: String -> Char
abc338b cs = snd . minimum . map swap . assocs $
accumArray (+) 0 ('a','z') [(c, -1) | c <- cs]
C - Leftover Recipes
シグネチャを決める。
abc338c :: Int -- N
-> [Int] -- Qi
-> [Int] -- Ai
-> [Int] -- Bi
-> Int -- 答え
とりあえず料理Bを無視して料理Aだけ作るとしたとき、作れる個数は $Q_i / A_i$ の最小値。
Aを作る個数を0からこの上限まで試して、残りの材料で作れる料理Bの個数も同様に導く。
合計の最大値をとる。
結果
abc338c _n qs as bs = maximum [s + tfun s | s <- [0..smax]]
where
smax = minimum [div q a | (q,a) <- zip qs as, a > 0]
tfun s = minimum [div (q - a * s) b | (q,a,b) <- zip3 qs as bs, b > 0]
別解
$s = 0,1,\dots$について $Q_i - s A_i$ を求める代わりに、$Q_i$から$A_i$を引くことを繰り返す。$s$の最大値は引けなくなったときがそれなので自然に判る。
abc338c :: Int -> [Int] -> [Int] -> [Int] -> Int
abc338c _n qs as bs =
maximum $
zipWith (+) [0..] $ -- Aを作る個数を加える
map bfun $ -- Bの作れる個数
takeWhile (all (0 <=)) $ -- どれかがマイナスになったら終了
iterate afun qs -- QiからAiを引くことを繰り返す
where
afun xs = zipWith (-) xs as -- Aをもう一つ作る
bfun rs = minimum [div r b | (b,r) <- zip bs rs, b /= 0] -- Bの作れる個数
takeWhile～iterateはunfoldrでかっこよくなるけど、そこまで凝らなくてもね。
qs : unfoldr step qs -- QiからAiを引くことを、引けなくなるまで繰り返す
where
step qs
| all (0 <=) qs1 = Just $ (qs1, qs1)
| otherwise = Nothing
where
qs1 = zipWith (-) qs as
D - Island Tour
シグネチャを決める。
abc338d :: Int -- N
-> Int -- M
-> [Int] -- Xi
-> Int -- 答え
島は数珠つなぎになっているので、元々はどちら向きにでも回ることができる。島の番号が増える向きを「順回り」、逆を「逆回り」と呼ぶことにする。
橋をどれか一つ落とすと、どちらか片方でしか行けなくなる。（逆に言うと、どちらかの回りが必ず妨害される。）
島$A$と$B$ ($A < B$)の間を移動するとき、順回りで渡る橋は$F = B - A$本、逆回りでは$R = N - F$本。
順回りで使う橋のどれかを落としたとき、逆回りの行程が必要になる。順回りで使う橋とは、橋$A$から$B-1$のこと。
逆に、それ以外の橋を落としたときは、順回りの行程が必要になる。全ての橋について、どちらかの行程が必ず必要である。
全ての行程について、その橋を落としたときに必要になる行程を足し込むことで、ツアー全体の行程が得られる。その最小値が求める値。
しかしこれを素朴にやると、要素$N$個の配列に$M$回の足し込みを行うため$O(NM)$で間に合わない。
足し込むべき行程は、橋$A$から橋$B-1$が$N - F$で、それ以外、つまり1から$A-1$までと$B$から$N$までは$F$で一定値である。1から順に見て変化するのは1,X,Yのとき。
これは累積和による積分の出番。
結果
import Data.Array
abc338d :: Int -> Int -> [Int] -> Int
abc338d n _m xs = minimum $ scanl1 (+) $ elems da -- 累積して最小値をとる
where
da = accumArray (+) 0 (1,n)
[ p
| (x0, x1) <- zip xs (tail xs) -- Xi, Xi+1
| let (a, b) = (min x0 x1, max x0 x1) -- A < B にする
, let f = b - a -- F
, let r = n - f -- R
, p <- [ (1, f) -- 1～にFを足す
, (a, r - f) -- A～にRを足すように差分をインパルス
, (b, f - r) -- B～にFを足すように差分をインパルス
]
]
別解
ユーザ解説 by AngrySadEightは、思いがけない切り口からの解法だった。
橋$N$を落としたときの総行程は、上で言う順方向の距離の総和として計算できる。
その他の橋を落とすことを一般化して考える代わりに、橋$N$が落ちたまま、島の方を一つ手前にずらす。つまりそれぞれ1減らす、ただし$0$は$N$に戻す。
すると、1だった島が$N$になることにより、この島発着の行程が全て、その時点の順方向から逆方向に切り替えることになる。
より詳しく見ると、最初の番号で$X$と$Y$を結ぶ行程$(X < Y)$があったとして、ずらすことで$X$が1から$N$に変わるとき、この行程は初めて、逆方向に切り替えられる。
さらにずれて今度は$Y$が1から$N$に変わるとき、逆方向だった行程が順方向に戻される。
一回転させることで、全ての行程が2度切り替えを受ける。
元の島$X$が1から$N$に変わるときに起きる行程の変化量を調べておき、初期状態の順方向の総和を初期値として累積和をとると、それぞれのステップでの行程の距離が得られるので、その差以上値をとればよい。
abc338d :: Int -> Int -> [Int] -> Int
abc338d n m xs = minimum $ scanl1 (+) $ elems diffs
where
diffs = accumArray (+) 0 (0,n)
[ p
| (x0, x1) <- zip xs (tail xs) -- Xi, Xi+1 の間の行程
, let d = abs $ x - y -- 行程の長さ
, let d1 = n - d - d -- 1度めの切り替えでの増分
, p <- [ (0, d) -- 初期状態での総行程はdの総和
, (min x y, d1) -- 1度めの切り替え
, (max x y, -d1) -- 2度めの切り替えで元に戻る
]
]
ひとつめの解法とこの別解とで、根底の考え方は違うのに、結果として出てきたコードはどちらも累積和を用いた、似たような計算をするのは興味深い。
E - Chords
シグネチャを決める。
abc338e :: Int -- N
-> [[Int]] -- Ai, Bi
-> Bool -- 答え
フレンズさんのtweetの絵が判りやすい。どこで切っても同じで、開いて一本にしたときに線が重ならないとは、（全て異なる文字による）括弧の対応がとれていることと同じなので、スタックで判定できる。
このとき、切る位置はもちろん自然にNと1の間にすると、AとBの小さい方が先に出現し、大きい方が後に出現する位置だと判るので、先に出現する方が開き、後が閉じ括弧となり、「今K番の括弧は開き中かどうか」を、スタックの中を探したり、別に表を持ったりする必要すらない。
結果
import Data.Array
abc338e :: Int -> [[Int]] -> Bool
abc338e n abs = loop [] $ elems circle
where
circle = array (1, n + n)
[ p
| (i, a:b:_) <- zip [1..] abs
, p <- [ (min a b, i) -- 開き括弧
, (max a b, -i)]] -- 閉じ括弧
loop _ [] = False -- 最後まで交差はなかった
loop js (i:is) | i > 0 = loop (i:js) is -- 開き括弧はpush
loop (j:js) (i:is) | i + j == 0 = loop js is -- スタックトップと一致する閉じ括弧はpop
| otherwise = True -- 違うなら、交差した。
公式解説のコードは、開きか閉じかを示す0/1と番号のタプルで真面目にやっていた。
符号を流用するこれの方がズボラだ…
F - Negative Traveling Salesman
シグネチャを決める。$U_i,V_i,W_i$は手抜きする。
abc338f :: Int -- N
-> Int -- M
-> [[Int]] -- Ui, Vi, Wi
-> Maybe Int -- 答え 経路がないとき Nothing
考える
さっぱりわからなかったのでアライさんのヒントを見る。
F問題は巡回セールスマンなのだ！ 最初にワーシャルフロイドで全点間最短経路問題を求めておけばあとは普通にbitDPやるだけなのだ！
「普通に」でどうしていいかまだ判らなかったので公式解説を見た。
つまり、「意図的に目的地として設定して移動した先の頂点の集合だけを考える。次の目的地まで行く経路に、初めて通る頂点があるかもしれないが、それは無視してよい。
なぜなら、その頂点も意識して通った方が低コストなら、そのように選んだ順路もどこかで意図的に探索されるから。」
なるほど。最小コストをDPして、その添え字は次のようにする。
- 意図的に到達済みの頂点集合 $S$ 、$N \leq 20$なのでビット表現で扱う
- 訪問を終えて最後に至った頂点 $i$
（頂点が頂点集合に含まれないような状況については、コスト無限大とする）
すると、$cost[S][i]$は、
- $i \not\in S$ のときは $\infty$
- 到達済み頂点が1つ $|S| = 1$ のときは当然0
- 複数のときは、$S$の$i$意外に到達済みの全ての場合に対して、何らかの終点$j$から$i$に向かったときのコストの最小値 $\displaystyle \min_{j \in S, j \neq i} \left ( cost[S \setminus \{i\}][j] + dist[j][i] \right )$
とすることで集めるDPで計算できる。
bitDPでは、部分集合を表す整数はより小さな値になるので、添え字の小さい方から順に値を確定できるのが面白い。
ワーシャルフロイド法は骨の髄まで命令型配列なのでSTモナドで計算し、結果をrunSTArrayでimmutable配列として取り出し、Arrayを使った暗黙の集めるDPで書いてみた。
が、どうあがいてもTLEする。
結局、ワーシャルフロイド法の結果をSTArrayのまま持ち、コストのDPもSTモナドで命令的に回してやったら2616ms, 175MBでACできた。
上のArray実装のときの集める関数 costf が原型を保って流用できてはいるが、本体の計算を関数型でできなかったのはくやしい。
G - evall
シグネチャを決める。
import qualified Data.ByteString.Char8 as BS
abc338g :: BS.ByteString -- S
-> Int -- 答え
皆目見当も付かない。
すごいHなの人のtweet の「すごい綺麗」さを理解するためには何とかするしかない。
（といっても、公式解説のコード例もユーザ解説のコード例も、問題の難解さに見合わないコンパクトさで言葉が出てこない。
降参。