A - Anyway Takahashi
計算する内容は $(a+b)\times(c-d)$だと問題文に明記されているので、これ以上説明することはない。
結果
せっかくなので main から書いてみる。
readの型が明示されていないが、defaultingでIntegerになっていると思われる。
main = do
li <- getLine
let [a,b,c,d] = map read $ words li
print $ (a + b) * (c - d)
putStrLn "Takahashi"
B - Rectangle Detection
シグネチャを決める。横着する。
abc269b :: [String] -- Si
-> [Int] -- 答え A,B,C,D
行について、「# が現れる」ような行が $A$ 行めから $B$ 行めであることを知りたい。
そのような $A$ 行めの文字列について、「# である」ような文字が $C$ 文字めから $D$ 文字めであることを知りたい。
Haskellの文字列は文字のリストなので、この二つの段階は共通化できる。
それぞれ性質 elem '#', ('#' ==) を満たす先頭の要素と末尾の要素の番号を知りたい、ということになる。
結果
abc269b ss = [a,b,c,d]
where
(a,b) = sub (elem '#') ss
(c,d) = sub ('#' ==) $ ss !! pred a
sub p xs = (head is, last is)
where
is = map fst $ filter (p . snd) $ zip [1..] xs
C - Submask
シグネチャを決める。
abc269c :: Int -- N
-> [Int] -- 答え
数 $N$ の2進表記に対して、1である各桁について、それを1のままにした数と、0にした数の両方が出力に含まれる。そして後者は前者より小さい。
最上位桁から調べて、ビットが1であるとき、そのビットを0にした数から（再帰的に）作られる数のリストに、1のままにした数から（再帰的に）作られる数のリストを連結すればよい。
import Data.Bits
abc269c :: Int -> [Int]
abc269c n = recur n (bit 59)
recur x 0 = [x]
recur x b
| x .&. b == 0 = recur x (shiftR b 1)
| otherwise = recur (xor x b) (shiftR b 1) ++ recur x (shiftR b 1)
(++) はダサいので、「この関数の結果に続けるリスト」を追加の引数にする Haskell の定番の高速化を追加する。
結果
import Data.Bits
abc269c :: Int -> [Int]
abc269c n = recur n (bit 59) []
recur x 0 rest = x : rest
recur x b rest
| x .&. b == 0 = recur x b1
| otherwise = recur (xor x b) b1 $ recur x b1 rest
where
b1 = shiftR b 1
D - Do use hexagon grid
シグネチャを決める。
abc269d :: Int -- N
-> [(Int,Int)] -- Xi,Yi
-> Int -- 答え
「連結成分」と言われたらUnionFind。
通常の碁盤の目状の画像について連結成分を考えるときは全ての画素をUnionFindの要素にするが、この問題設定では無駄が多そうなので、入力に現れる座標のマスのみを要素とする。
それぞれのマスについて、6近傍のマスで入力に現れているものと Union を行う。
最終的な UnionFind で連結成分の個数を数えれば答えが得られる。
結果
自作のUnionFindは要素が整数なので、$(X_i,Y_i)$ に $i$ を対応させる Map を併用し、近傍が現れているかの判断もこれを利用して行う。ついでにその近傍のマスの番号も取得できる。
Data.Maybe.maybe b f ma は、ma が成功して Just a ならさらに続きの処理をした f a を返すが、ma が失敗して Nothing ならデフォルト値 b を返す。
step2で、近傍 zw の番号 j と xy の番号 i を uniteUF するが、zw が入力にない場合は元のままの uf を返すのに使っている。
import qualified Data.Map as M
import Data.Maybe
abc269d n xys = length $ allDivisions $ foldl' step1 (newUF n) xyis
where
xyis = zip xys [0..]
m = M.fromList xyis
step1 uf (xy, i) = foldl' (step2 i) uf $ neighbors xy -- xyと周囲のマスをunionする
step2 i uf zw = maybe uf (uniteUF uf i) $ M.lookup zw m -- 周囲で入力に現れるマスのみ
neighbors (x,y) =
[ (z,w)
| z <- [pred x, x, succ x]
, w <- [pred y, y, succ y]
, z + w /= x + y -- 8近傍のうち(x+1,y-1),(x-1,y+1),そして (x,y) は含まない
]
-- UnionFind APIのみで実装は略
-- 0からN-1を要素とするUnionFindを作る
newUF :: Int -> UnionFind
-- iとjを統合する
uniteUF :: UnionFind -> Int -> Int -> UnionFind
-- 全ての分割を得る
allDivisions :: UnionFind -> [[Int]]
完全版はこちら。
E - Last Rook
シグネチャを決め…られない。
- 答えがわかったら "! X Y" の形式で出力して停止、
- まだわからないなら "? A B C D" の形式で問い合わせ、返答Tが
- -1 なら、何かやらかしたので非常停止
- 0以上の数なら、それを手がかりにして推測を続行するために再帰
という形の再帰的計算になると予想が立つ。
答えが複数ある場合、どれを出力しても正解とみなされます。
などと目くらましが書いてあるが、結局、それぞれの行に必ず1つルークがある、それぞれの列に必ず1つルークがある、という最終状態からどれか一つのルークを隠した場面なので、その「ルークのない行」と「ルークのない列」は唯一に定まる。
行と列で条件が変わらないので、別々に二分探索する。絞り込めていない $2M$ 行の前半分について問い合わせた結果が $M$ なら全ての行にルークがいるので空行は反対側に、1少なければ今調べた範囲に空行がある。
$N \leq 10^3 = 1000 < 1024 = 2^{10}$ なので、10回あれば行は特定でき、列についても同様で、20回あれば間に合う。
結果
行と列の二分探索は共通化する。
範囲は下開区間で扱っている。
$-1$を返された場合の異常系は省略している。プログラムは正しい。
import System.IO
main = do
n <- readLn
i <- loop True n 0 n
j <- loop False n 0 n
putStrLn $ unwords ["!", show i, show j]
loop :: Bool -> Int -> Int -> Int -> IO Int
loop _ _ lb ub | succ lb == ub = return ub
loop vert n lb ub =
do
putStrLn $ unwords $ "?" : map show abcd1
hFlush stdout -- これを入れないと TLE してしまう
t <- readLn
-- if t == -1 then error "something wrong" else
if t == d2 then loop vert n mid ub
else loop vert n lb mid
where
d2 = div (ub - lb) 2
mid = lb + d2
abcd1 = if vert then [succ lb, mid, 1, n] else [1, n, succ lb, mid]
vert引数の意味を取り違え、"! Y X" を出力して WA になりしばらく悩んだ。
サンプルを含めて対角線上に答えがあるテストケースに関してちらほら AC してしまうため、逆に何がおかしいのかしばらくわからなかった。