ChatGPTを用いてAtCoder Beginners Contest 294に参加した
A問題からE問題の５問を30分で解くことができた。
だそうで、急いでラッダイト運動に参加してこようと思います。
A - Filter
数として read するまでもなく、末尾が 0,2,4,6,8 な語だけ取り出せばよい。
結果
main = getLine >>
getLine >>= putStrLn . unwords . filter abc294a . words
abc294a :: String -> Bool
abc294a s = elem (last s) "02468"
B - ASCII Art
ord のような関数を持ち出すまでもなく、それぞれの数を対応する文字に置き換えられる。
結果
main = getLine >>
getContents >>= putStrLn . unlines . map abc294b . lines
abc294b :: String -> String
abc294b = map ((tbl !!) . read) . words
tbl = '.' : ['A'..'Z']
C - Merge Sequences
シグネチャを決める。
abc294c :: Int -- N
-> Int -- M
-> [Int] -- Ai
-> [Int] -- Bi
-> ([Int],[Int]) -- 答え
元々 $\{ A_i \}$ も $\{ B_i \}$ も昇順なので、まるごとソートする代わりに、「マージソート」のマージ操作をすれば整列される。
そのとき、マージ結果を求める代わりに、現在位置が何番目で、A側とB側のどちらの数を取ったかを記録すればいい。
結果
mergeは、現在位置と $A_i, B_i$ の列をとり、$A_i$ を選んだら Left 番号, $B_i$ を選んだら Right 番号 を結果のリストに置く。
import Data.Either
abc294c :: Int -> Int -> [Int] -> [Int] -> ([Int],[Int])
abc294c n m as bs = partitionEithers $ merge 1 as bs
merge k (a:as) (b:bs)
| a < b = Left k : merge (succ k) as (b:bs)
| True = Right k : merge (succ k) (a:as) bs
merge k [] bs = [Right i | (i,_) <- zip [k..] bs]
merge k as [] = [Left i | (i,_) <- zip [k..] as]
Data.Either.partitionEithers を使わなくても、A側の番号だけを返す定義にして、A側とB側を入れ替えて2度実行するというズボラなやり方をしてもいい。
abc294c :: Int -> Int -> [Int] -> [Int] -> ([Int],[Int])
abc294c n m as bs = (merge 1 as bs, merge 1 bs as)
merge k (a:as) (b:bs)
| a < b = k : merge (succ k) as (b:bs)
| True = merge (succ k) (a:as) bs
merge k as _ = map fst $ zip [k..] as
bsが先に尽きたときは2つめの等式でasの残りに正しく番号が振られ、bsを残してasが先に尽きたときも2つめの等式で空リストが生成される。
あるいは、A側の結果から、出現しなかった数を取り出す計算で、B側を復元することもできるだろう。
D - Bank
問題をよく読むと、「既に呼ばれている人は誰か」を気にする必要はないことがわかる。イベント2で、呼ばれていない人や、受付に行った人を呼ぶことはないことが保証されている。
つまり、イベント1は無視して、イベント2で終わった人だけチェックし、そうでない最小の番号の人がイベント3で呼ばれる。
MEXというやつだが、普通にIntSetを用いて解けばよいだろう。
結果
1からNをIntSetに入れておき、イベント2で呼ばれた人を消し、イベント3では残っている人の最小の番号を返す。
import Control.Monad
import qualified Data.IntSet as IS
main = do
[n,q] <- map read . words <$> getLine
let is0 = IS.fromAscList [1..n]
foldM_ (\is _ -> do
ev <- map read . words <$> getLine
case ev of
[1] -> return is -- （何もしない）
[2,x] -> return $ IS.delete x is -- xは立ち去る
[3] -> print (IS.findMin is) >> return is -- まだ居る最小の番号を出力
) is0 [1..q]
命令型の場合は、まだ居るかどうかの大きさNのフラグ配列を持ち、イベント3に対して、まだ居る最小の番号を、毎回先頭から検索していると大変なので、「前回のイベント3で調べた最終の番号から再開する」ロジックが必要になるのかな。
E - 2xN Grid
シグネチャを決める。$v_*, l_*$ は横着する。
abc294e :: Int -- L
-> Int -- N1
-> Int -- N2
-> [[Int]] -- v1i, l1i
-> [[Int]] -- v2i, l2i
-> Int -- 答え
それぞれの行の内容がランレングス圧縮された形で与えられて、それを展開したときに、同じ位置に同じ文字がくる箇所を数えろ、と言っている。
$L \leq 10^{12}$ と膨大なので、本当に展開して数える訳にはいかない。
圧縮された状態のまま、同じ文字数ずつ消費して、それが同じ文字のランであれば結果にその長さを足しこむ、という方針で計算する。
結果
abc294e :: Int -> Int -> Int -> [[Int]] -> [[Int]] -> Int
abc294e l n1 n2 vls1 vls2 = loop 0 vls1 vls2
loop acc ([v1,l1]:vls1) ([v2,l2]:vls2) =
acc1 `seq`
case compare l1 l2 of
LT -> loop acc1 vls1 ([v2,l2-l1]:vls2)
EQ -> loop acc1 vls1 vls2
GT -> loop acc1 ([v1,l1-l2]:vls1) vls2
where
acc1 = if v1 == v2 then acc + min l1 l2 else acc
loop acc _ _ = acc
acc1 `seq` は無くても動くが、スペースリークが抑えられて少し速くなる。
この問題では「少し速くなる」程度だが、foldlをダッシュに置き換えたり、その中の関数を正格評価するように調整したりする必要にちょくちょく迫られるのは、
A programming language is low level when its programs require attention to the irrelevant.
「プログラミング言語は、そのプログラムが無関係なものに注意を払う必要がある場合、低レベルである。」(by みんなの自動翻訳TexTra)
「この文の意味は、低水準言語では、本質的でない細かい動作まで記述しなければならないということです。」(BingAIによる補足説明）
に該当するのだろうか。（確かに、本来気にしなくてもいいはずの部分なのだけど。）
F - Sugar Water 2
というか今回そもそも
が流れてくるまで、ABCがあったことも気づかなかった。
今までの過去問でときどき遭遇していた濃度問題は全て敗退していたので、テリー氏に従ってググったところ、ABC034DがやはりWA,TLEで終わっていたので、大人しく解説を読んだ。
目標とする濃度を設定した後、個々の液体に関して、溶質が絶対量でどれだけ過不足があるかを計算し、その合計が負なら足らなくて薄くなる、さもなくば足りている、と判断する。
液体が $W$[g]、濃度が$100P$[%]のとき、溶質は $WP$ [g] ある。
目標の濃度が$100Q$[%]のとき、$WP - WQ$ [g] の過不足がある。
$P$と$Q$だけを比較しても判断できず、$W$によってこの値は符号を含めて変わりうるのが、ややこしいポイント。
公式の解説スライドをさらに見ると、この種の問題を「平均の最大化問題」と呼ぶらしい。
結果
目標の濃度に対して、$C_j,D_j$ のそれぞれの過不足を求める。これを大きい順に番号を振ると、つまり、ある必要量以上に余剰のある溶液の個数が得られるので、これを持つ Map を作る。
$A_i,B_i$のそれぞれの過不足に対して、これを補填できる$C_j,D_j$の個数が上のMapを一度検索することで得られるので、その総数がK以上になるような濃度の下限を二分探索で探す。
命令型言語で、ソートした配列に対する二分探索した結果の添え字により、ある値以上の要素の個数を数える計算は、キー以上の値の個数を持つ Map への lookupGE と同等である。
import qualified Data.Map as M
import Data.Maybe
abc294f :: Int -> Int -> Int -> [[Int]] -> [[Int]] -> Double
abc294f n m k abs cds = binsearch prop 0 100
where
pm q a b = fromIntegral (100 * a) - q * fromIntegral (a + b) -- 濃度qに対する過不足
prop q = cnt >= k
where
cdm = M.fromDescList $ -- Ci,Diの濃度qに対する過不足のMap
flip zip [1..] $
sortBy (flip compare) [pm q c d | c:d:_ <- cds]
cnt = sum -- Ai,Biに対して濃度q以上にできるCj,Djの個数の和
[ maybe 0 snd $ M.lookupGE x cdm
| a:b:_ <- abs, let x = - pm q a b
]
binsearch f l h = loop l h
where
loop l h
| term = l
| f m = loop m h
| True = loop l m
where
m = (l + h) / 2
term = h - l <= l * 1e-9 -- HとLの差がL*10^-9以下になったら止める
binsearchはABC292Fと同じものだが、決め打ちで100回ループではTLEしたので、問題の要求する精度を満たしたところでループを終えるように変えている。
判定関数の中でData.Mapを生成するので割と重く、ループ回数を節約する必要があった。
結果は3948msとギリギリ。
感想
食塩水問題完全に理解した。
（しかし公式解説には誤差のない値を得る方法 by MMNMMというさらにブッとんだ話があって、とうてい理解が及ばない。今後の課題袋に入れておく。）
AI
AIに話を戻して、画像の機械学習を妨害する加工のように、プログラミング演習問題の問題文にもそういう細工をすることになるのかしら。
その前に、プログラミングの授業がなくなってしまうのかしら。
東大京大をはじめとして、文系理系問わず、リテラシーレベルのデータサイエンス教育を目的としたPython入門講義が蔓延している現状だけど、ExcelにAIが載って、やりたいことを伝えたら勝手にやってくれるようになれば、その程度の授業は本当に不要になってしまう。
ドライワロス。
人知の及ばないような並列計算のアクロバティックなプログラムをAIが紡いで、そのコードの正しさをAI支援のcoq的なもので保証するとか、量子コンピュータのプログラムを作るとか、そういう方向に進んでいくなら夢があるけど。
計算機の能力
問題Eの $L \leq 10^{12}$ は、今のCPUの速度を考慮に入れて、naiveな解法を防ぐための設定になっている。シングルタスクなアルゴリズムを念頭に置いた場合、これはなかなか突破されそうにない。
一方、問題Fの $N,M \leq 5 \times 10^4$ は、最近のGPUだとCUDAコアが1万個とか載って、タワー型マシンにそれを4枚突っ込んだり、4Uラックマウントに8枚突っ込んだりできるみたいなので、全ての場合をエレファントに求めることも可能な時代になりつつある？