AtCoder465振り返りです。
参加ペース落としているので3週間ぶりの参加です。
結果
ABCの3完でした。
ふりかえり
A問題
- 問題
- 回答
A > B * 2 / 3
式変形すると
A * 3> B * 2
となります。
-- Main
main :: IO ()
main = do
[a, b] <- getInts
printYn $ 3 * a > 2 * b
B問題
- 問題
- 回答
1時間経過するごとに、金額を加算していきます。
駐車の終了時刻をtと置くと、駐車料金は以下のように場合分けできます。
tは終了時刻なので、t=lの時はY(円)になるのがポイントです。
| $t$(時刻) | 金額(円) |
|---|---|
| $t \in [1, L]$ | $Y$ |
| $t \in (L, R]$ | $X$ |
| $t \in (R, 23]$ | $Y$ |
これをHaskellで書くとこうなります。
-- Main
main :: IO ()
main = do
[x, y, l, r, a, b] <- getInts
let step t
| t <= l || t > r = y
| l < t && t <= r = x
| otherwise = error $ "invalid step pattern t: " <> show t
print $ foldl' (\acc t -> acc + step t) 0 [a + 1 .. b]
C問題
- 問題
- 回答
まず問題文に書いてある通りにoの度に反転する方法を考えてみます。
Sの文字数がNであることと、対象の配列Aの長さがNであること
一回の配列の反転にかかる計算量がO(N)であることから
全体の計算量は最悪O(N ^ 2)となります。
2≤N≤5×10^5であることから、O(N^2)は最悪2.5 x 10^11となり、TLEすることが予想されます。
そこで、計算量をどう抑えるかを考えます。
oの度に反転することが計算量悪化の原因なので、反転の回数をできるだけ減らせばよさそうです。
反転回数を減らすには、どうすればよいでしょうか。
反転するかどうかはoが来る度に変わることと、先頭の1文字目は反転するしないに関わらず同じであることから、先頭の1文字目を除いてoが来る度に反転する・しないを切り替え、最後に反転有無を判定させれば1回で済みそうです。
やり方は偶奇判定など色々思いつきますが、今回はxorを使いましょう。
この方法で反転回数を1回に減らすことができます。
しかし、この方法だけでは不十分です。
このやり方だけでは、反転する配列の数は先頭のk項だけという制約を満たすことができません。
そこで、問題文の例をトレースして観察してみます。
S = ooxoo であるとき、k回目の操作で配列Aの先頭k項の数字に着目してみると、以下のようになっていることがわかります。
-
k=1:{1}(S1 = o) -
k=2:{2, 1}(S2 = o) -
k=3:{2, 1, 3}(S3 = x) -
k=4:{4, 3, 1, 2}(S4 = o) -
k=5:{5, 2, 1, 3, 4}(S5 = o)
反転は最後の1回でまとめてやることに決めたので、配列を反転せずに列挙してみます。いま反転しているかわかるように、カッコ書きで反転あるなしを記載しておきます。
-
k=1:{1}(S1 = o, 反転なし) -
k=2:{1, 2}(S2 = o, 反転なし) -
k=3:{3, 1, 2}(S3 = x, 反転あり) -
k=4:{4, 3, 1, 2}(S4 = o, 反転あり) -
k=5:{4, 3, 1, 2, 5}(S5 = o, 反転なし)
箇条書きにして整理してみると、反転の有無によって値を先頭に追加しているか末尾に追加しているかが変わってきそうに見えます。
表にして整理してみます。
この表をみると、表が反転していない場合: 末尾に追加, 表が反転している場合: 先頭に追加していることがわかりますね。
| $k$ | 追加する値 | $S_k$ | 反転の有無 | 追加位置 | 結果 |
|---|---|---|---|---|---|
| 1 | 1 | - | - | (初期値) | ${1}$ |
| 2 | 2 | o | 反転なし | 末尾 | ${1, 2}$ |
| 3 | 3 | x | 反転あり | 先頭 | ${3, 1, 2}$ |
| 4 | 4 | o | 反転あり | 先頭 | ${4, 3, 1, 2}$ |
| 5 | 5 | o | 反転なし | 末尾 | ${4, 3, 1, 2, 5}$ |
値を先頭・末尾にどちらにも追加したいならどうすればよいでしょうか？
リストの先頭・末尾両方に値を追加したいなら両端キューが使えます。
Haskellの両端キューといえばData.Sequenceですね。
これで解法が見えてきました。
-
oが出てくる度に反転有無のフラグを切り替え、最後に反転有無を判定して反転する- 反転有無の切り替えは
xorで行う
- 反転有無の切り替えは
- 両端キューを持っておき、1項ずつ追加する
- 先頭と末尾どちらに追加するかは追加時の反転有無フラグによって切り替える
- 反転なし: 末尾に追加
- 反転あり: 先頭に追加
- 両端キューは
Data.Sequenceを使用する
- 先頭と末尾どちらに追加するかは追加時の反転有無フラグによって切り替える
これを実装に起こすとこのようになります。(先頭一文字は判定有無を考慮しなくてよいので、両端キューはSeq.singleton 1で初期化しています。)
-- >>> solve "ooxoo"
-- >>> solve "ooooooo"
-- >>> solve "xooxoxoxoxoxxoo"
-- [5,2,1,3,4]
-- [7,5,3,1,2,4,6]
-- [15,11,10,7,6,3,1,2,4,5,8,9,12,13,14]
solve :: String -> [Int]
solve s = if rn == 1 then reverse qnLst else qnLst
where
qnLst = Seq.toList qn
(rn, qn) = foldl' step (0 :: Int, Seq.singleton 1) $ zip (tail s) [2 ..]
step (rev, q) (c, n)
| c == 'o' =
if rev == 1
then (rev `xor` 1, n :<| q)
else (rev `xor` 1, q :|> n)
| c == 'x' =
if rev == 1
then (rev, n :<| q)
else (rev, q :|> n)
-- Main
main :: IO ()
main = do
_ <- getInts
s <- getLine
printList $ solve s
全体を振り返って
B問題でt=lの時の条件に気づけたこと、C問題で両端キューを使えば解けることに気づけたのは成長を感じました。
ただ今回もD問題解けなかったので、コンテスト中に解きたい…！！
D解けるように引き続き精進がんばります！
(来週は関数型まつりでお休みします。)