A - Rated for Me
シグネチャを決める。
abc104a :: Int -- R
-> String -- 答え
問題文の述べるとおりに場合分けをする。
結果
abc104a r
| r < 1200 = "ABC"
| r < 2800 = "ARC"
| otherwise = "AGC"
B - AcCepted
シグネチャを決める。
abc104b :: String -- S
-> Bool -- 答え
普通に
入力は少なくとも4文字あることが保証されているので、1,2文字目、中間、末尾の文字、と分けて、全て空でないことが保証できる。
また、入力には英文字しか含まれないことも保証されている。
よって、
- 先頭が
A - 2文字めが小文字
- 中間を大文字と小文字で選り分けたとき、大文字は
Cがひとつだけ - 末尾が小文字
を調べればよい。
import Data.Char
abc104b1 (c1:c2:s) = c1 == 'A' && isLower c2 && cs == "C" && isLower cN
where
cs = filter isUpper $ init s
cN = last s
有限オートマトン
問題の条件に合うような文字列を受理する有限オートマトンを考えると、
- 最初に
Aを受け取る - 続いて小文字を1つ受け取る
- 続けて小文字を0個以上受け取り、
Cを受け取る - 続いて小文字を1つ受け取る
- 受理状態、さらに小文字が続いても受理状態
素直にコードに直す。
abc104b s = q0 s
where
q0 (c0:s0) = c0 == 'A' && q1 s0
-- q0 "" = False 不要
q1 (c1:s1) = isLower c1 && q2 s1
-- q1 "" = False 不要
q2 (c2:s2)
| isLower c2 = q2 s2
| c2 == 'C' = q3 s2
q2 _ = False -- "" と C以外の大文字の場合
q3 (c3:s3) = isLower c3 && q4 s3
q3 "" = False
q4 (c4:s4) = isLower c4 && q4 s4
q4 "" = True
q4 は q4 s4 = all isLower s4 に短縮できる。
これを q3 に埋め込めんで q3 s3 = not (null s3) && all isLower s3 に短縮できる。
q2 は分岐がいろいろなのでロジックが複雑だけど、
q2 s2 = case dropWhile isLower s2 of
'C':s3 -> q3 s3
_ -> False
q0 と q1 は q0 (c0:c1:s1) = c0 == 'A' && isLower c1 && q2 s1 と埋め込みできる。
結局、同等の計算が次のようにまとまる。
abc104b (c0:c1:s2) = c0 == 'A' && isLower c1 &&
case dropWhile isLower s2 of
'C':s3 -> not (null s3) && all isLower s3
_ -> False
正規表現
いわゆる「正規表現」があれば /^A[a-z]+C[a-z]+$/ とマッチさせるだけの話なんだが。
（英文字しか来ないことを使えば /^A\w+C\w+$/ でもいい）
C - All Green
シグネチャを決める。横着する。
abc104c :: Int -- D
-> Int -- G
-> [[Int]] -- p_i, c_i
-> Int -- 答え
動的計画法
答えは $[1, \sum p_i]$ この上限は 1,000 と小さな範囲。
難易度 $i$ の問題について、0 問から $p_i$ 問までそれぞれ解いたときの得点の追加を考え、$k$ 問解くことで得られる最大の点数、をDPで更新していく。
import Data.Array.Unboxed
import Data.Bool
abc104c :: Int -> Int -> [[Int]] -> Int
abc104c _d g pcs = head [k | (k,s) <- assocs arrD, s >= g]
where
sump = sum $ map head pcs
arr0 = listArray (0, sump) $ 0 : repeat (-1) :: UArray Int Int
arrD = foldl' step arr0 $ zip [100, 200 ..] pcs
step arr (i100, p:c:_) = accumArray max (-1) (0, sump)
[ (k + j, s + i100 * j + bool 0 c (j == p))
| (k,s) <- assocs arr, s >= 0, j <- [0 .. p]]
はまやん氏のユーザ解説「でやったほうが良かったかも」に相当する。
公式解説のやり方
- 中途半端に解くのはいずれかの難易度一つで十分
- 全問解く難易度の選択を $2^D$ とおり総当たりする
という方針。難易度の低い方から順に、全問解くか保留するかを再帰的に選び、保留した最大の難易度を、後で中途半端に解くために覚えておく。
abc104c :: Int -> Int -> [[Int]] -> Int
abc104c _d g pcs = recur 0 0 0 0 $ zip [100, 200 ..] pcs
where
recur :: Int -- 解いた問題数
-> Int -- 合計得点
-> Int -- 解かなかった最大難易度の得点
-> Int -- 同上の問題数
-> [[Int]] -- 残りの p_i, c_i
-> Int -- 答え
recur cnt acc _ _ _ | acc >= g = cnt -- 早上がり
recur cnt acc i100 pi []
| i100 > 0, k < pi = cnt + k -- 使えるものの個数が足りる
| otherwise = maxBound -- 使い切っても足りないか、使えるものがない
where
k = divrup (max 0 $ g - acc) i100
recur cnt acc i100 pi ((j100, pj:cj:_) : ipcs) = min b1 b2
where
b1 = recur (cnt + pj) (acc + j100 * pj + cj) i100 pi ipcs -- j は全て使う
b2 = recur cnt acc j100 pj ipcs -- j を保留
divrup x y = negate $ div (negate x) y
あっ。
「$c_i, G$ はすべて100の倍数である。」と、難易度 $i$ はひとつ $100i$ 点なので、全て 1/100 で考えれば良かったのか。
D - We Love ABC
シグネチャを決める。長いので ByteString を使う。
import qualified Data.ByteString.Char8 as BS
abc104d :: BS.ByteString -- S
-> Int -- 答え
こういう問題は中央の B に注目して考え、左の A の個数と右の C の個数の積が、$j$ を固定した $(i,j,k)$ の個数。
$1 \leq j \leq N$ について順にこれを数えればよい。
$S_j$ が B のときは答えを数え、A,C のときは左右のその文字の個数が増減する。
? が混じることで、少しだけ変化する。
中央が B のときだけでなく、? のときも答えを数えることになる。
また、注目していない位置の ? は何であってもよいので、そのようなバリエーションの個数全てについて、ABC数を倍増させて数える必要がある。
中央が B のとき：
左の A 右の C を一つ選んだとき、それを選択できる文字列は $2^Q$ とおりある。
左は ? 右は C を選ぶとき、それを選択できる文字列は $2^{Q-1}$ とおりある。
左は A 右は ? を選ぶとき、それを選択できる文字列は $2^{Q-1}$ とおりある。
左は ? 右も ? を選ぶとき、それを選択できる文字列は $2^{Q-2}$ とおりある。
中央が ? のとき、上の $Q$ を $Q-1$ にしただけの場合がある。
これらを数えるために、
- 現在注目している位置 $j$
- $j$ より左の
Aの個数cA - より左の
?の個数cQL - より右の
Cの個数cC - より右の
?の個数cQR
を追跡する。
結果
import Data.List
import Data.Bool
abc104d :: BS.ByteString -> Int
abc104d bs = summ $ snd $ mapAccumL step (0,0,cC0,cQ0) $ BS.unpack bs
where
cC0 = BS.count 'C' bs
cQ0 = BS.count '?' bs
p3Q = modPower 3 cQ0
p3Q1 = bool 0 (modPower 3 (cQ0 - 1)) $ cQ0 > 0
p3Q2 = bool 0 (modPower 3 (cQ0 - 2)) $ cQ0 > 1
p3Q3 = bool 0 (modPower 3 (cQ0 - 3)) $ cQ0 > 2
step (cA, cQL, cC, cQR) 'A' = ((succ cA, cQL, cC, cQR), 0)
step (cA, cQL, cC, cQR) 'C' = ((cA, cQL, pred cC, cQR), 0)
step (cA, cQL, cC, cQR) 'B' = ((cA, cQL, cC, cQR), res)
where
res = summ $ map prodd [[cA, cC, p3Q],[cQL, cC, p3Q1],[cA, cQR, p3Q1],[cQL, cQR, p3Q2]]
step (cA, cQL, cC, cQR) '?' = ((cA, succ cQL, cC, cQR1), res)
where
cQR1 = pred cQR
res = summ $ map prodd [[cA, cC, p3Q1],[cQL, cC, p3Q2],[cA, cQR1, p3Q2],[cQL, cQR1, p3Q3]]
-- モジュロ計算は省略
なぜ僕はまず「シグネチャを決める。」のか。
最近発表されたポエムに「競技プログラミングのコードは全てを main() に突っ込んでいて汚い。実務ではそんなプログラムは書かない。」というような主張があった。
C++ などでコードを書くガチ勢な人たちは大抵そうしているせいで、そうしないといけない、と思い込んでいるのかもしれないが、別にそんなことはない。
解説を書く人たちはぜひ、解説には綺麗なコードを示してほしいと願っているが、あえてそうしないという主張も読んだことがあるので（フレンズさんだったかな？要出典：追記しました）人それぞれとしか言いようがない。
人それぞれなので、自分は、（自分の力の及ぶ範囲で）エレガントなコードを示したい、と考えてこれを続けている。
Haskellで競技プログラミングをする人で「interact 使うとIOと純粋を簡単に隔離できていい」という主張がときどき見られる。
自分はこれの気持ちが全くわからない。
答えを求めるアルゴリズム本体こそが問題の中心で、read系処理までの「手前の部分」は、ORMのような、プログラムの外とのインピーダンス整合をとる部分にすぎない。
問題の入力データは、例えば今回のC問題では、全て整数の文字列表記で
\begin{array}{ll}
D & G \\
p_1 & c_1 \\
\vdots \\
p_D & c_D
\end{array}
と与えられるそれは、
abc104c :: Int -- D
-> Int -- G
-> [[Int]] -- p_i, c_i
-> Int -- 答え
というシグネチャで関数に与えられるべきものであることは自明で、このシグネチャを設定すれば、それより手前の前処理がどう read すればよいかも自明になる。
例えば実際にはこうなっている。
main :: IO ()
main = do
[d,g] <- bsGetLnInts
pcs <- replicateM d bsGetLnInts
let ans = abc104c d g pcs
print ans
bsGetLnInts :: IO [Int]
bsGetLnInts = unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
ここを作るのは、AIにやらせるまでもなく、機械化できそう。
Rust だとこんなのが提案されて
入力形式の指定書式がそのまま採用されたライブラリが一般化しているようだ。
（公式ドキュメントに
The macro’s user interface is basically the same with tanakh’s input macro.
と明記されている。）
HaskellでもTemplate Haskellとか型レベルプログラミングとかで、やればできるだろう。
だから僕は、シグネチャを決める。
追記
発掘しました。
基本的に実装例にはwriter解がそのまま貼ってあります。writer解というのはつまり「私たちにとって読みやすいコード」です。
なので、
「人に見せるコードは整えて欲しい」に対する答えは「人に見せるコードではありません」
「人に見せるコードを用意して欲しい」に対する答えは「その必要はないと考えています」
「人に見せるコードでないなら解説に載せないで欲しい」に対する答えは「その通りだと思います」