Google Code Jam 2018 Qualification Round - Go, Gopher!

対話式問題

あんまりHaskellには向いてない感？
C++で書いたのとあまり変わらない感じになりました。

一部分を置き換えたリストの生成

「リストの一部分を置き換えたリストを生成」する良い方法が思いつかなかったので無理やりです。

listmod.hs

f :: Int -> a -> [a] -> [a]
f n a xs = take n xs ++ (a : drop (n+1) xs)

O(n)で効率も良く無いと思うのですが、もっと良い方法ってあるんでしょうか？

解答の方針

領域の大きさ(1000x1000)とTest2のサイズ(A=200)を比べると、簡単に済ませるにはとにかく一列に埋めていけば良い。

手順

1. (2,2)を要求 -> (1,1), (1,2), (1,3)が返ってくるまで要求し続ける
2. 次に(3,2)を要求 -> (2,1), (2,2), (2,3)が返ってくるまで以下同文
3. 以下同様に
4. 要求されたマス目の数に足りるところまできたら、(0,0)が返ってくるまでひたすら(n,2)を要求する

(i,2)を要求している時に(i-1,1), (i-1,2), (i-1,3)が埋まるのを待っているわけですが、その間に返ってきている(i,* ), (i+1,* )もマークしておくと試行回数を減らすことができる。

実装

gcj.hs

import Control.Monad
import System.IO

f :: Int -> [a] -> a -> [a]
f n xs a = take n xs ++ (a : drop (n+1) xs)

solve :: Int -> Int -> [Int] -> IO ()
solve n a xs = do
    putStrLn $ shows n " 2"
    (x:y:_) <- (map read.words) <$> getLine
    let ns@(n0:n1:n2:nr) = f (((x+1-n)*3)+(y-1)) xs 1
    case n0+n1+n2 of
        3 | n < a  -> solve (n+1) a (nr ++ [0,0,0])
        3 | n == a -> s2 (n+1)
        otherwise  -> solve n a ns

s2 :: Int -> IO ()
s2 n = do
    putStrLn $ shows n " 2"
    (x:y:_) <- (map read.words) <$> getLine
    case (x,y) of
        (0,0) -> return ()
        (_,_) -> s2 n

main = do
    hSetBuffering stdout NoBuffering
    t <- readLn
    replicateM_ t $ do
        a <- readLn
        solve 2 ( (a+2) `div` 3 - 2 )  [0,0,0,0,0,0,0,0,0]

main

hSetBuffering stdout NoBufferingでバッファリングを無効化が必要。

solve

(n-1,* )が埋まるまで同じnで再帰して、埋まったらnを+1して再帰する。
結局要求している(n,2)を中心として3x3のマスしか見ていないので、9マス分だけ用意しておけば良い。2次元リストにすると要素の差し替えが面倒になるので、要素9個のリストを用意。
(n-1,* )をリストの先頭になるように配置しておき、埋まっていないところを0、埋まったところを1とすると、先頭3つの要素の和が3かで判定できる。埋まったらその分リストをスライドする。

s2

要求を満たせるところまできたらひたすら(0,0)が返ってくるまで繰り返すだけ。