ABC307 A〜C(Julia)

AtCoder ABC307 AからEの5完でした。Fも後から解けたので概説します。
Juliaで書いてますが、Pythonの人も読めると思います。
正確にかつ簡潔に書くスキルはないので届く範囲は狭いかもしれませんが、この記事が役に立つ人がいれば幸いです。

ここではA~Cを概説します。後半はここにあります。

テンプレ

# (デフォルトでは1行の文字列を受取り)1つの整数に変換する
toI(s=readline()) = parse(Int,s)
# (デフォルトでは1行の文字列を受取り)整数の1次元配列に変換する
toVI(s=readline()) = toI.(split(s))
# f()をn回評価して、配列にして返す
rep(f,n) = [f() for _ in 1:n]
# ブール値を受け取って、標準出力にYes/Noで返す
pYesNo(b) = ifelse(b,"Yes","No") |> println

# メイン関数。入出力を担当。
function main()
	solve() |> println
end

# ソルバ。解くのを担当。
function solve()
end

main()

A問題

問題文を一般化すると、N 週間 = 7N 日間 の入力が与えられるので、7日毎の和にまとめて出力してくださいと。

a.jl

toI(s=readline()) = parse(Int,s)
toVI(s=readline()) = toI.(split(s))

function main()
	n = toI()
	a = toVI()
	xs = solve(n,a)
	println(join(xs,' '))
end

function solve(n,a)
	[sum(a[7i-6:7i]) for i in 1:n]
end

main()

i週目は(7i-6)日から7i日なので、相当する部分配列はa[7i-6:7i]となります。
Pythonのリスト内包表記のような形で簡潔に表現できます。

B問題

N個の文字列が与えられる。それらの相異なるものを連結して回文にできるか。

b.jl

toI(s=readline()) = parse(Int,s)
rep(f,n) = [f() for _ in 1:n]
pYesNo(b) = ifelse(b,"Yes","No") |> println

function main()
	n = toI()
	s = rep(readline,n)
	solve(n,s) |> pYesNo
end

function solve(n,s)
	for i in 1:n, j in 1:n
		i == j && continue
		s1 = s[i]*s[j]
		s1 == reverse(s1) && return true
	end
	return false
end

main()

s = rep(readline,n)でs[i]が$S_i$になります。
Juliaのfor文は二重ループ以上もまとめて書けます。
i == j && continueは、if i == j continue endと等価です。
(i == jなら次のループへ行く)
Juliaでは文字列pとqの結合はp*qになります。
Juliaでは文字列はイミュータブルです。文字列の編集を繰返す場合はStringでなくVector{Char}の形で扱うのが良いかもしれません。
reverseは配列などを逆転させます。文字列のためにもわざわざ定義してあるので、使えます。

C問題

問題のC問題です。
水コーダーの私が21:26にACし、C問題としては200番目くらいだったので、この問題とJuliaがマッチしていたという側面はあると思います。

解答のうちソルバのみ示します。

c_solve.jl

function solve(ha,wa,a,hb,wb,b,hx,wx,x)
    # a,b,xは'#'と'.'からなる配列の配列で、i行目j列目はa[i][j]
    # a2,b2,x2はブール行列('#'=>true,'.'=>false)で、i行目j列目はa2[i,j]
    # aの上下にhx,左右にwxの透明マスを付加した行列a2を作成
	a2 = falses(ha+2hx,wa+2wx)
	for i in 1:ha, j in 1:wa
		a2[hx+i,wx+j] = a[i][j] == '#'
	end
    # bの上下にhx,左右にwxの透明マスを付加した行列b2を作成
	b2 = falses(hb+2hx,wb+2wx)
	for i in 1:hb, j in 1:wb
		b2[hx+i,wx+j] = b[i][j] == '#'
	end
    # xをブール行列x2に変換
	x2 = falses(hx,wx)
	for i in 1:hx, j in 1:wx
		x2[i,j] = x[i][j] == '#'
	end
    # a2から(hx,wx)の大きさの行列を切出す全探索
	for i1 in 1:ha+hx, j1 in 1:wa+wx
        # a3は(i1,j1)を起点とした大きさ(hx,wx)の行列
		a3 = a2[i1:i1+hx-1,j1:j1+wx-1]
        # a2の中の'#'がa3に全て含まれていることを確認
		count(a2) == count(a3) || continue
        # b2から(hx,wx)の大きさの行列を切出す全探索
		for i2 in 1:hb+hx, j2 in 1:wb+wx
            # b3は(i2,j2)を起点とした大きさ(hx,wx)の行列
			b3 = b2[i2:i2+hx-1,j2:j2+wx-1]
            # b2の中の'#'がb3に全て含まれていることを確認
			count(b2) == count(b3) || continue
            # cはa3とb3のbitwise or
			c =  a3 .| b3
            # cとx2が一致すれば、打ち切ってYesを返す
			c == x2 && return true
		end
	end
    # 全探索で全て一致しなければ、Noを返す
	return false
end

今回、対象のグリッドの大きさは高々10程度で、余白をつけても30程度。
なるべく計算量を落とすというよりは、なるべく素直で紛れの少ないアプローチが良さそうでした。

---

後半に続きます。