A - A Recursive Function
これは階乗の計算。
abc273a n = product [1 .. n]
結果
main = readLn >>= print . product . enumFromTo 1
B - Broken Rounding
シグネチャを決める。
abc273b :: Int -- X
-> Int -- K
-> Int -- 答え
例では途中の桁での四捨五入をしてみせたりしているが、実際のところは$i=0$から、1の位から順に行うので、ある桁についてやるときにはそれより下の桁は全て0になっている。
すると『1の位について四捨五入を行う。（1の位は0になる。）結果を10で割る。』という計算を $K$ 回繰り返し、$10^K$ を掛けて戻せばよいとわかる。
結果
abc273b x k = loop 1 k x
loop m 0 x = x * m
loop m k x = loop (m * 10) (pred k) (if 5 <= r then succ q else q)
where
(q,r) = divMod x 10
C - (K+1)-th Largest Number
シグネチャを決める。
abc273c :: Int -- N
-> [Int] -- Ai
-> [Int] -- 答え
なんだかややこしい言い回しをしているが、$A$ の要素を持つ多重集合を考えたとき、大きい方から順に、その値の多重度、いくつ重複して入っているかを聞いている。
結果
Data.IntMap でカウントすればよい。
import qualified Data.IntMap as IM
abc273c :: Int -> [Int] -> [Int]
abc273c n as =
take n $ (++ repeat 0) $ -- 後半足りない分は0を補い、前からN項を取り出す
map snd $ IM.toDescList $ -- 大きい方から、個数だけ取り出す
IM.fromListWith (+) [(a, 1) | a <- as] -- Aiの個数をそれぞれ数える
D - LRUD Instructions
何やらデータ量が多く、（一度全てのクエリを取り込んで、吟味してから計算するタイプでなくて）クエリに対してその場で結果を返すことの繰り返しをする向きの問題なので、前処理の計算とクエリごとの計算に分けてシグネチャを決める。
その前にざっくり方針を考えると、前処理では、壁になっているマスの位置を座標の集合のようなデータ構造で記録しておき、クエリではこれを利用して、現在位置から、壁と外壁に注意しながら移動先を求める、をクエリの数だけ繰り返すことになるだろう。
ぶつかることで壁が壊れる、というようなギミックはないので、前処理で求めたデータはクエリで変更を受けない。よってクエリ処理は高橋君の移動先の位置だけ返せばよい。
-- 前処理
abc273dp :: Int -> Int -- H,W
-> Int -- N
-> (Int, Int) -- ri, Ci
-> {- 分析したデータ -}
-- クエリ処理
abc273d :: {- 分析したデータ -}
-> (Int, Int) -- 高橋君の現在位置
-> Char -- di
-> Int -- li
-> (Int, Int) -- 高橋君の移動後の位置
水平方向の移動の場合は、現在位置の行に関して、現在位置から直近の壁の座標が知りたい。
すると、行ごとに、壁の位置の整数集合 IntSet を作っておけば、lookupLT, lookupGT で必要な情報が得られる。これを row map rm :: IntMap IntSet とする。
垂直方向の移動の場合は列に関して考えることになる。つまり、水平と垂直の両方のデータ構造を持っておく必要があるとわかる。後者を column map cm :: IntMap IntSet とする。
クエリに対しては、次のような手順になる。
- まず、現在位置の行または列のマップを検索して壁の集合を取り出す。（存在しない場合は当該の行または列には壁がないので移動に制限がない。）
- 得られた集合に対して、現在位置から移動する向きに近い値を検索する。（存在しない場合は壁に当たるまで移動できる。）
- 見つけた壁にぶつかる手前、もしくは $l_i$ だけ移動した先の近い側に到着する。
上の手順のうち、場合によって差し替える、テンプレートパターンの穴の内容は以下のようになる。
実際は、「集合検索の向き」とそれ以降は（キー以外）一致している。
| 向き | 使うマップ,キー | 集合検索の向き,キー | 壁の手前は | $l_i$を | 近い側とは |
|---|---|---|---|---|---|
L |
rm, r | LT, c | succ | 引く | max |
R |
rm, r | GT, c | pred | 足す | min |
U |
cm, c | LT, r | succ | 引く | max |
D |
cm, c | GT, r | pred | 足す | min |
結果
lookupの結果見つからなかった場合を特別扱いするとややこしいので、番兵をうまく配置する。すなわち、壁にぶつからない場合に$1$または$H,W$で止める代わりに、$0$と$H+1,W+1$にも壁をおいておく。これを受けて、rmを検索して何もない場合、外周の壁$0$と$W+1$だけのあるデフォルト集合を使う。
import qualified Data.IntMap as IM
import qualified Data.IntSet as IS
import Data.Maybe
type M = IM.IntMap IS.IntSet
type POS = (Int, Int)
abc273dp :: Int -> Int -> Int -> (Int, Int) -> (Int, Int, M, M)
abc273dp h w n rcs = (h, w, rm, cm)
where
rm = sub w [(r, [c]) | (r,c) <- rcs]
cm = sub h [(c, [r]) | (r,c) <- rcs]
sub ub xyss = fmap (mkset ub) $ IM.fromListWith (++) xyss
mkset ub ys = IS.fromList $ 0 : (succ ub) : ys
abc273d :: (Int, Int, M, M) -> POS -> Char -> Int -> POS
abc273d (h, w, rm, cm) (r, c) d l =
case d of
'L' -> (r, sub decrs rs c)
'R' -> (r, sub incrs rs c)
'U' -> (sub decrs cs r, c)
'D' -> (sub incrs cs r, c)
where
rds = IS.fromAscList [0, succ w] -- row default set
cds = IS.fromAscList [0, succ h] -- column default set
rs = IM.findWithDefault rds r rm
cs = IM.findWithDefault cds c cm
decrs = (IS.lookupLT, succ, (-), max)
incrs = (IS.lookupGT, pred, (+), min)
sub (lkup, sp, op, minmax) s x = minmax (sp $ fromJust $ lkup x s) (op x l)
入出力のドライバ部分も含めた完全なコードはこちら。
前処理部で IntMap IntSet を作って、クエリ部で「マップを検索し、対応がないときデフォルトの集合を返す」とする役割分担を、
前処理部で「マップを検索し、対応がないときデフォルトの集合を返す関数」を作り、クエリ部は関数を呼び出すだけ、と切り直すと、
クエリ部は $H,W$ を知らなくてもよくなる。結果
E - Notebook
これまた、大量のクエリを処理する問題。
整数列は逆順に考えて [Int] で表現でき、ノートは IntMap [Int] で表現でき、毎回のクエリに対する出力は常に整数列の末尾なので、クエリによって起きる状態の変更を管理することが主目的とわかる。
状態の型を決める。
type State = ([Int], IM.IntMap [Int])
クエリを処理する部分は、入力を高速に処理するために ByteString を使い、クエリは引数があったりなかったりなので、これをそのまま受け取るようにする。
import qualified Data.IntMap as IM
import qualified Data.ByteString.Char8 as BS
abc273e :: State -> BS.ByteString -> State
結果
先頭の1文字だけで種類を判別し、状態遷移を行う。
abc273e (as, mp) li =
case BS.index li 0 of
'A' -> (x:as, mp)
'D' -> (drop 1 as, mp)
'S' -> (as, IM.insert x as mp)
'L' -> (IM.findWithDefault [] x mp, mp)
where
Just (x,_) = BS.readInt (BS.words li !! 1)
この結果の左側が数列に対応するので、その先頭要素、ただし空リストのときは $-1$ を出力すればよい。
(2022-10-17追記) cirno3153氏による「公式解説への補足」 で
この問題は永続スタックを作る問題である、と読み解くことができます。
と指摘されるまで、逆にそんなことを全然気にしていなかった。Haskellでは当然全てのデータはimmutableなので何の疑問もなく実装して終わりだったので。
対して命令型言語では、リストで $A$ を表し、ノートをマップで表し、ここにリストを格納したつもりでも、実際には「参照」しか保存されておらず、ADD や DELETE を破壊的に実現してしまうと、ノートに保存した数列も壊れてしまう。参照にならないように SAVE LOAD でクローンを作るとそれはそれで大変なことになる。言われてみればその通り…なんでこんな簡単な問題がEなのかと思ったら、そういう事だったのね…
感想
それなりに工夫が必要な問題はDぐらいで、C,D,Eはどれも IntMap を振り回していただけで終わってしまった感じ。
（といいつつFはどうしていいかわからない。）
G - Row Column Sums 2
2022-10-17 解けたので追記。
シグネチャを決める。
abc273g :: Int -- N
-> [Int] -- Ri
-> [Int] -- Ci
-> Int -- 答え
行や列の総和だけが問題なので、行や列を入れ替えても場合の数は変わらない。
行列の要素は非負整数で、総和は0,1,2のいずれかである。
$R_i = 0$ のとき、その行は全て0しかありえないと確定する。
$R_i = 1$ のとき、その行のどこか一か所が1で、他は全て0となる。
$R_i = 2$ のとき、その行に1が2か所現れるか、1か所だけ2が現れるかのどちらかである。
同じことが列についても言える。
1行めから$N$ 行めまで順に、$R_i$ に従ってどのように値を置くかを考えるとき、
$C_j = 0$ である列には0しか入れられない。
$C_j = 1$ である列に一度1を置いたら、それ以降その行には0しか入らなくなる。つまり以降は $C_j = 0$ な行と同じ扱いになる。
$C_j = 2$ である列には1を2度置けるか、2を一度だけ置ける。2を置いたとき以降は $C_j = 0$ な行と同じ扱いになり、1を置いたときは以降は $C_j = 1$ な行と同じ扱いになる。
ということは、それぞれの列にあとどれだけ値を置くことができるか、という容量の初期値が $C_j$ で、行ごとに $R_i$ に従って値を置くときにこれを消費していくと考えられる。
ところで、最初に述べたように、それぞれの行が実際どこかは関係ないので、「あと1入れられる列は何列残っているか」「あと2入れられる列は何列残っているか」の二つの数だけ押さえておけばよい。行 $i$ を考えるときのこの2つの数を $cnt_{i,1}, cnt_{i,2}$ とする。
$R_i = 0$ のとき、その行はオール0で、場合の数は1、カウントは $cnt_{i+1,1} = cnt_{i,1}, cnt_{i+1,2} = cnt_{i,2}$ で変化なし。
$R_i = 1$ のとき、残カウント=1の列のいずれかを選んで1を置く場合の数は $cnt_{i,1}$、カウントは$cnt_{i+1,1} = cnt_{i,1} - 1$ と減って、2の側は変化なし。
残カウント=2の列のいずれかを選んで1を置く場合の数は $cnt_{i,2}$、 カウントは $cnt_{i+1,2} = cnt_{i,2} - 1,$ $cnt_{i+1,1} = cnt_{i,1} + 1$ となる。
$R_i = 2$ のとき、残カウント=1の列を2つ選んで1を置く場合の数は ${}_nC_r (n = cnt_{i,1}, r = 2)$、カウントは $cnt_{i+1,1} = cnt_{i,1} - 2$ と減る。
残カウント=2の列を2つ選んで1を置く場合の数は ${}_nC_r (n = cnt_{i,2}, r = 2)$、カウントは $cnt_{i+1,2} = cnt_{i,2} - 2,$ $cnt_{i+1,1} = cnt_{i,1} + 2$ となる。
残カウント=2の列を1つ選んで2を置く場合と、残カウント=1の列と=2の列を1つずつ選んで1を置く場合は、まず残カウント=2の列を1つ選んで1を置き、これが変化して残カウント=1の列が1つ増えたものも含めてそれらから1つ選んで1を置く、という手順に統合される。その場合の数は $cnt_{i,2} \times (cnt_{i,1} + 1)$ で、カウントは $cnt_{i+1,1} = cnt_{i,1} + 1 - 1 = cnt_{i,1},$ $ cnt_{i+1,2} = cnt_{i,2} - 1$ となる。
行$i$を考えるとき、行$1$から$i-1$までは値を確定させているので、置くべき数の残りは $\sum_{j=i}^N R_j$ で、これは行ごとに固定の値である。つまりこの値と $cnt_{i,1} + 2cnt_{i,2}$ は等しい。これを $\textit{rest}_i$ と名付けると、 場合 $(cnt_{i,1}, cnt_{i,2})$ は2変数でなく $cnt_{i,1} = \textit{rest}_i - 2 cnt_{i,2}$ なので $cnt_{i,2}$ の1変数で表現できる。
よって、$cnt_{i,2}$ をキーにした一次元配列にそれぞれの場合の数を入れて、行ごとに数えるDPができる。全ての行について計算したとき、$cnt_{N+1,1} = cnt_{N+1,2} = 0$ と尽きており、つまり配列の添え字0の要素に求める場合の数が入っている。
結果
ある残カウントの行を消費するとき、必要な数だけ残っていることを確認する必要がある。
それにつけても accumArray は便利。
import Data.Array.Unboxed
abc273g :: Int -> [Int] -> [Int] -> Int
abc273g n rs cs
| conflict = 0 -- ΣRiとΣCiが一致しない
| otherwise = vn ! 0
where
cntA = accumArray (+) 0 (0,2) [(c,1) | c <- cs] :: UArray Int Int
[_, cnt1, cnt2] = elems cntA
rest0 = cnt1 + cnt2 * 2
conflict = sum rs /= rest0
v0 :: UArray Int Int
v0 = listArray (0, cnt2) $ replicate cnt2 0 ++ [1]
(vn, _) = foldl step (v0, rest0) rs -- sndは0はなず
modBase = 998244353
reg x = mod x modBase
add x y = reg (x + y)
mul x y = reg (x * y)
step vr 0 = vr
step (v, rest) 1 = (v1, rest - 1)
where
v1 = accumArray add 0 (bounds v)
[ p
| (c2, cnt) <- assocs v
, cnt > 0
, let c1 = rest - c2 - c2
, let ps = [(pred c2, mul cnt c2) | c2 >= 1] ++ -- 2の列に1を置く
[(c2, mul cnt c1) | c1 >= 1] -- 1の列に1を置く
, p <- ps
]
step (v, rest) 2 = (v1, rest - 2)
where
v1 = accumArray add 0 (bounds v)
[ p
| (c2, cnt) <- assocs v
, cnt > 0
, let c1 = rest - c2 - c2
, let ps = [(pred c2, mul cnt $ c2 * succ c1) | c2 >= 1] ++ -- 2の列に1を置き、1の列に1を置く
[(c2, mul cnt $ nC2 c1) | c1 >= 2] ++ -- 1の列に1を2つ置く
[(c2 - 2, mul cnt $ nC2 c2) | c2 >= 2] -- 2の列に1を2つ置く
, p <- ps
]
nC2 n = div (n * pred n) 2