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に出現回数を保存して解いています。