ABC398の振り返りです。今回3週間ぶりの参加でした。
結果
ABCの3完でした。
ふりかえり
A問題
- 問題
- 回答
問題文の条件
- 各文字は
-または=である - 回文である
- 文字列中に
=は 1 個または 2 個含まれる。 2 個含まれる場合、それらの=は隣接している
を読み替えると、
- nが奇数の場合: 真ん中が
=になり、これ以外が-になる - nが偶数の場合: 真ん中が
==になり、これ以外が-になる
と読めます。
ここから、
- nが奇数の場合
nを2で割った数の'-' + "=" + nを2で割った数の'-'
- nが偶数の場合
nを2で割った数 - 1 の'-' + "=" + nを2で割った数 - 1の'-'
（割った後の余りは切り捨て）
で答えが得られるとわかります。
これをコードに起こすと、以下のようになります。
main :: IO ()
main = do
n <- readLn @Int
let s = replicate (n `div` 2) '-'
putStrLn $
if odd n
then s ++ "=" ++ s
else tail s ++ "==" ++ tail s
B問題
- 問題
- 回答
数をソートして、グルーピングします。
例えば、入力が1 4 1 4 2 1 3の場合、昇順ソートすると
[1, 1, 1, 2, 3, 4, 4]
これをグルーピングして、
[[1, 1, 1], [2] [3] [4, 4]]
で、全てのリストの長さを取ると
[3, 1, 1, 2]
このうち、3以上の値と2以上の値がそれぞれ1つ以上あればYesになります。
コードは以下の通りです。
main :: IO ()
main = do
as <- sort <$> getInts
let cnt = sortOn Down $ map length $ group as
printYN $ length cnt >= 2 && head cnt >= 3 && (head . tail) cnt >= 2
ちなみに、最初のコードでは最後の行を以下のようにしており、これが原因で1ペナになってしまいました。
printYN $ length cnt >= 2 && head cnt == 3 && (head . tail) cnt == 2
このコードの場合だと、1 1 1 1 2 2 2 のような3つ以上、2つ以上同じ数を含む入力を考慮できません。
同じようにソートしてグルーピングすると
[[1, 1, 1, 1] [2, 2, 2]]
それぞれの長さを取ると
[4, 3]
となります。
これは正解なのですが、誤ったコード例だと正しく判定されずWAになります。
C問題
- 問題
- 回答
まず、zip [1 ..] <$> getIntsで番号と数を紐付けます。
その後、数でソート、グルーピングし、数が一つしかないものだけfilterして抽出します。
その後、数が最大のものの番号を出力したいので、fst $ maximumOn sndでsnd、つまり数が最大のものの番号を取得します。
main :: IO ()
main = do
n <- readLn @Int
as <- zip [1 ..] <$> getInts
let as' = sortOn snd as
t = concat $ filter (\l -> length l == 1) $ groupOn snd as'
print $ if null t then -1 else fst $ maximumOn snd t
解いている間はなぜか再帰でがんばろうとして2ペナだしましたが、そんなことする必要はありませんでした。
ちなみに、数の出現回数をIntMapで持っておいて、valueが1のもののみ取得する方法もあります。
こっちのほうが若干早いです。
回答はこちらにおいています。
main :: IO ()
main = do
n <- readLn @Int
as <- getInts
let im = IM.fromListWith (+) $ map (,1) as
ks = IM.keys $ IM.filter (== 1) im
pos = fromMaybe (-1) $ safeMaximum ks
im2 = IM.fromList $ zip as [1 ..]
print $ fromMaybe (-1) $ IM.lookup pos im2
全体を振り返って
今回はペナを多めに出してしまいました。
問題文の誤読や方針の誤りが原因なので、もう少ししっかり考えられるようにしたいです。
おまけ
今回もRustで解いてみました。
Bはcombinations(5)、CはHashMapに出現回数を保存して解いています。