LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@flowerhill

AtCoder Beginner Contest 371 振り返り

Last updated at Posted at 2024-09-21

ABC371の振り返りです。久しぶりに書きます。

結果

A,Bの2完でした。今回むずかった

スクリーンショット 2024-09-21 16.39.41.png

スクリーンショット 2024-09-21 16.40.55.png

解説

A問題

初っ端から難しかったです。「これ真面目にかんがえちゃだめだ」と思って全パターン洗い出しました。
欲をかいて何度か真面目に解こうとしたので時間がかかってしまいました。

main :: IO ()
main = do
  [sab, sac, sbc] <- words <$> getLine

  putStrLn $ case (sab, sac, sbc) of
    ("<", "<", "<") -> "B"
    (">", "<", "<") -> "A"
    (">", ">", "<") -> "C"
    (">", ">", ">") -> "B"
    ("<", ">", ">") -> "A"
    ("<", "<", ">") -> "C"

B問題

こっちは難しくなかったです。最初にFalseのArrayをつくって、都度更新していきました。

main :: IO ()
main = do
  [n, m] <- getInts
  abs <- replicateM m do
    [a, b] <- words <$> getLine
    return (read @Int a, b)

  let arr = listArray @UArray (1, n) $ replicate n False

  foldM_
    ( \acc (i, s) -> do
        if s == "M" && not (acc ! i)
          then do
            putStrLn "Yes"
            return $ acc // [(i, True)]
          else do
            putStrLn "No"
            return acc
    )
    arr
    abs

C問題(upsolved)

これは難しかった…
問題を見て解けないやつだなと思って速攻で諦めました。

この問題のポイントは

  • 頂点を固定した時、GとHが同型であることをどう判断するか？

で、これを判断するには以下の2つを考える必要があります。

  1. GとHの頂点を固定した場合、同型でない辺をどう判断するか？
  2. 問題文の定義に従う場合、Hが同じ番号の頂点をつないでいなくても同型になりうるが、これをどう判定するか？

1について何が言いたいかというと、たとえばGの頂点を G1, G2, .. Gn, Hの頂点をH1, H2, .. Hnとすると例えば

  • G1とG2を繋ぐ辺が存在し、H1とH2を繋ぐ辺が存在しない
  • G4とG8を繋ぐ辺が存在し、H4とH8を繋ぐ辺が存在する
  • G10とG15を繋ぐ辺が存在せず、H10とH15を繋ぐ変が存在する

といったことをどう判断するかということです。
これは問題文から

GにはMG​本の辺があり、i本目 (1≤i≤MG​)の辺は頂点ui​と頂点viを結んでいます。
HにはMH​本の辺がありi本目(1≤i≤MH​)の辺は頂点ai​と頂点bi​を結んでいます。

とあることから、accumArrayをつかって以下の様に求めます

let g = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((u, v), True), ((v, u), True)] | u : v : _ <- uvs]
    h = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((a, b), True), ((b, a), True)] | a : b : _ <- abs]

こうすると、対応する頂点が繋がってる場合はTrueを、繋がっていない場合はFalseを返すarrayができます。ある頂点同士が繋がっているかどうかは

g ! (i, j)
h ! (i, j)

だけで求められます。すごいぞarray。

次に

問題文の定義に従う場合、同じ番号の頂点をつないでいなくても同型になりうるが、これをどう判定するか？

ですが、これはグラフの頂点が Hi -> Hi' のような対応関係があった場合

  • G1とG2を繋ぐ辺が存在し、H1'とH2'を繋ぐ辺が存在する
    • ただし、H1' = H2, H2' = H3
  • G4とG8を繋ぐ辺が存在し、H4'とH8'を繋ぐ辺が存在する
    • ただし、H4' = H8, H5' = H10
  • G10とG15を繋ぐ辺が存在せず、H10'とH15'を繋ぐ変が存在する
    • ただし、H10' = H8, H15' = H5

の様な時にも同型と言えてしまうわけです。（図示すると一発なのですが、面倒なのでここではやりません）

で、これを考慮すると、当然Hは全ての組み合わせで同型を考える必要があることになります。

じゃあこれをどう解くかと言うと、permutationsを使います。

permutationsを使うと、以下のように配列の全ての組み合わせを求めることができます。

ghci> import Data.List
ghci> permutations [1..3]
[[1,2,3],[2,1,3],[3,2,1],[2,3,1],[3,1,2],[1,3,2]]

これを使って、グラフの写像を書くと

ps <- permutations [1 .. n]  -- リスト内包表記の中なので、こういう書き方になってる
let m = listArray @UArray (1, n) ps

として書くことができます。このように書くと、keyが写像後、valueが写像前として扱うことができるので

[ g ! (i, j) == h ! mij
  | i <- [1 .. (n - 1)],
    let mi = m ! i,
    j <- [(i + 1) .. n],
    let mij = (mi, m ! j)
]

で同型の判断ができます。
愚直に全探索している形になりますが、ノード数が1≤N≤8なので、計算量的にも問題ありません。

で、問題で聞かれていることは

同型でない辺の金額を求め、その合計値を算出し、その中から最小値を求める

ことですから、このように書きます

minimum
  [ sum
      [ if g ! (i, j) == h ! mij then 0 else aij ! mij
        | i <- [1 .. (n - 1)],
          let mi = m ! i,
          j <- [(i + 1) .. n],
          let mij = (mi, m ! j)
      ]
    | ps <- permutations [1 .. n],
      let m = listArray @UArray (1, n) ps
  ]

補足ですが、各辺同士の金額を求めるarrayは以下のように書いておきます。

let ass1 = zipWith (++) (tail $ inits $ repeat 0) (ass ++ [[]])
    aij = listArray @UArray ((1, 1), (n, n)) $ concat $ zipWith (zipWith max) ass1 $ transpose ass1

わざわざこのようにしているのは、A1,3の金額とA3,1の金額が同じなので、これをarrayで取得できるようにしているためです。

全体のコードはこのようになります

main :: IO ()
main = do
  n <- readLn @Int
  mg <- readLn @Int
  uvs <- replicateM mg getInts
  mh <- readLn @Int
  abs <- replicateM mh getInts
  ass <- replicateM (n - 1) getInts

  let ass1 = zipWith (++) (tail $ inits $ repeat 0) (ass ++ [[]])
      aij = listArray @UArray ((1, 1), (n, n)) $ concat $ zipWith (zipWith max) ass1 $ transpose ass1
      g = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((u, v), True), ((v, u), True)] | u : v : _ <- uvs]
      h = accumArray @UArray (||) False ((1, 1), (n, n)) $ concat [[((a, b), True), ((b, a), True)] | a : b : _ <- abs]

  print $
    minimum
      [ sum
          [ if g ! (i, j) == h ! mij then 0 else aij ! mij
            | i <- [1 .. (n - 1)],
              let mi = m ! i,
              j <- [(i + 1) .. n],
              let mij = (mi, m ! j)
          ]
        | ps <- permutations [1 .. n],
          let m = listArray @UArray (1, n) ps
      ]

D問題(upsolved)

Cより簡単な問題です。
累積和を求めて、rからlを引くのですが、1個ポイントがあります。

−10^9≤X≤10^9

とXの範囲が大きいため、全ての要素を作って計算するとTLEになります。そのため、rとlに一番近い最右の位置をもとめるために二分探索を使う必要があります。(今回は二分探索使うの気づかず時間内に解けませんでした、、)

IntMapにちょうどlookupLEやlookupLEがあったので、これを使うとこうなりました

main :: IO ()
main = do
  n <- readLn @Int
  xs <- getInts
  ps <- getInts
  q <- readLn @Int
  lrs <- replicateM q getInts

  let xm = IM.fromAscList $ zip xs [1 .. n]
      pAccum = listArray @UArray (0, n) (scanl' (+) 0 ps)

  forM_ lrs \(l : r : _) -> do
    let r' = IM.lookupLE r xm
        l' = IM.lookupGE l xm

    print $
      if isNothing r' || isNothing l'
        then 0
        else pAccum IA.! (snd . fromJust) r' - pAccum IA.! ((snd . fromJust) l' - 1)

全体を振り返って

Cを飛ばしたのは正解だったのですが、二分探索に気づけなかったのは痛かったです。とはいえ、二分探索の使い方を学ぶ機会になりました。（境界値とか意外とめんどくさい。。）

おまけ

Rustの回答

Dはunwrap_or_else()がべんりでした。

lower_bound, upper_boundについて

拾いものですが、参考になりました。ややこしいなと思っていたのですが半開区間だったのですね。
https://rsk0315.hatenablog.com/entry/2022/08/12/130515

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?