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 回目) 。

AtCoder Beginner Contest 061

http://abc061.contest.atcoder.jp/

  • Rank: 364th
  • Performance: 1185
  • Rating: 923 (+44) (Highest!)

3完。

A: Between Two Integers

所感

49s で解けた書けた。過去最速。

B: Counting Roads

解法

隣接行列を使ってカウント。

所感

時間かかりすぎ (12m)。

C: Big Array

解法

(a, b) というタプルのリストを作り、それを a の昇順でソート。0 に b を足していく畳み込みをして、K 以上になった時点で a を出力。

所感

C# で書いた。ソートに使う比較関数を、ラムダ式で渡せるのが便利。C++ でもできるのかしら。(C の高階関数といえば関数ポインタだったけど)。

D: Score Attack

解法

重みの正負を反転させ、Bellman-Ford 法で最短経路探索。

ただし、頂点 1 -> N 間に閉路がないにも関わらず、全体として見たときに閉路がある場合に inf と判定されてしまうので、適当な回数 (> 2N) 更新して最短距離が N 回目以降に更新されたときのみ inf 。

所感

グラフ問題だったので諦めようかと思っていたが、見た感じ典型だったので、蟻本を引っ張り出し写生した。結局 (コンテスト時間内には) 通せなかったが、グラフ問題に手が出始めたので競プロのモチベが向上した。

Haskellで分数の演算

Haskell で分数を扱うには、Data.Ratio モジュールの Ratio a 型を使う。
% 演算子を使い、\displaystyle\frac{a}{b}a % b のように表現される。

ghci> import Data.Ratio
ghci> :t (%)
(%) :: Integral a => a -> a -> Ratio a
ghci> :t 2 % 3
2 % 3 :: Integral a => Ratio a
ghci> 5 % 10
1 % 2
ghci> 2 % (-3)
(-2) % 3
ghci> (-2) % (-3)
2 % 3

Ratio a 型は、Num、Fractional、Real 型クラスのインスタンスである。
そのため、特に型注釈のない小数などの多相定数は Ratio a 型になることができる。

ghci> 1.2 :: Integral a => Ratio a
6 % 5
ghci> -1.3 :: Ratio Int
(-13) % 10
ghci> 1.5 / 2 :: Ratio Integer
3 % 4

演算子 +-*/ が使える。

ghci> (1 % 6) + (2 % 9)
7 % 18
ghci> (1 % 6) - (2 % 9)
(-1) % 18
ghci> (2 % 3) + 1
5 % 3
ghci> 0.5 - (1 % 2)
0 % 1
ghci> (2 % 3) * (3 % 4)
1 % 2
ghci> (2 % 3) * (-3.5)
(-7) % 3
ghci> (2 % 3) / (3 % 4)
8 % 9
ghci> 3 / (1 % 3)
9 % 1
ghci> ((-5) % 2) / 0.2
(-25) % 2

divmod を使いたいときは、代わりに Data.Fixed モジュールの div'mod'を使う。

ghci> import Data.Fixed
ghci> :t div'
div' :: (Real a, Integral b) => a -> a -> b
ghci> (13 % 5) `div'` (4 % 5)
3
ghci> (99 % 4) `div'` 5
4
ghci> (99 % 4) `div'` (-5)
-5 -- 負の無限大に丸められる
ghci> 2.99 `div'` (1 % 2)
5
ghci> :t mod'
mod' :: Real a => a -> a -> a
ghci> (13 % 10) `mod'` (2 % 5)
1 % 10
ghci> (13 % 10) `mod'` 0.7
3 % 5
ghci> (13 % 10) `mod'` (-0.7)
(-1) % 10
ghci> ((-13) % 10) `mod'` 0.7
1 % 10
ghci> ((-13) % 10) `mod'` (-0.7)
(-3) % 5
ghci> 2.99 `mod'` (1 % 2)
49 % 100

Ratio a 型の値から分子を取り出すには numerator 関数、分母を取り出すには denominator 関数を使う。

ghci> :t numerator
numerator :: Ratio a -> a
ghci> :t denominator
denominator :: Ratio a -> a
ghci> numerator (2 % 3)
2
ghci> denominator (4 % 2)
1 -- 2 % 1

Float、Double 型の数値を Ratio a 型に変換するには、toRational 関数を使う。ただし、誤差が発生することがある。

ghci> :t toRational
toRational :: Real a -> a -> Rational
ghci> toRational (0.5 :: Float)
1 % 2
ghci> toRational (2.4 :: Double)
5404319552844595 % 2251799813685248

なお、Rational は Ratio Integer の型シノニムである。

逆に、Rational 型の分数を小数などに変換するための fromRational 関数も提供されている。こちらも誤差が発生することがある。

ghci> :t fromRational
fromRational :: Fractional a => Rational -> a
ghci> fromRational (1 % 2)
0.5
ghci> fromRational (1 % 3)
0.3333333333333333