kuretchi's blog

競技プログラミング初心者のブログです。

AtCoder Beginner Contest 062

http://abc062.contest.atcoder.jp/

  • Rank: 213th
  • Performance: 952
  • Rating: 925 (+2) (Highest!)

2完。うーんという感じ。

A: Grouping

解法

やるだけ。

main :: IO ()
main = putStr . solve =<< map read . words <$> getLine
 
solve :: [Int] -> String
solve [x, y]
    | elem x g1 && elem y g1 = "Yes"
    | elem x g2 && elem y g2 = "Yes"
    | elem x g3 && elem y g3 = "Yes"
    | otherwise = "No"

g1 :: [Int]
g1 = [1, 3, 5, 7, 8, 10, 12]
 
g2 :: [Int]
g2 = [4, 6, 9, 11]
 
g3 :: [Int]
g3 = [2]

所感

C だと明らかに面倒。

B: Picture Frame

解法

やるだけ。

import Control.Monad (replicateM)
 
main :: IO ()
main = do
    [h, w] <- map read . words <$> getLine
    a <- replicateM h getLine
    putStr . solve $ a
 
solve :: [String] -> String
solve a = replicate l '#' ++ "\n"
       ++ (concat . map (\s -> "#" ++ s ++ "#\n") $ a)
       ++ replicate l '#' ++ "\n" where
    l = length (head a) + 2

所感

C だと明らかに面倒 (2 回目)。

ちなみに、迷路などが入力として与えられたとき、この問題のようにあらかじめ外壁で囲んでおくと、その後の実装が簡単になることがあります。

ということなので、多分ほんとは C (C++) で解いて慣れた方がよかった。

C: Chocolate Bar

解法

まず、縦か横の長さが 3 の倍数のときは明らかに 0 。

あとは、縦で 3 分割する場合 (パターン 1) と、縦で 2 分割したあと横に分割する場合 (パターン 2) (縦横が逆の場合も同様) があるので、いい感じに探索すれば良い。

パターン 1 は、横の長さを 3 で割り、残りを 2 で割るといい感じになる。コンテスト中、横の長さを 3 で割ったものを最短辺、その 2 倍を全体の長さから引いたものを最長辺として実装していたので、無限に WA が出た。

パターン 2 は、分割する位置を 0 - H 間で全探索すればよい。残りは (なるべく) 中央で分割すると最適。

所感

デバッグが下手すぎる気がした。

D: 3N Numbers

解法

分からず。データ構造ゲーっぽかった (優先度付きキュー) 。

所感

勉強を決意した (INF 回目) 。