Explore "Full-Stack" in depth!

情報系の専門学校で、今は機械学習に的を絞って学習中。プログラミングを趣味でやりつつ、IT系のあらゆる知識と技術を身に付けるべく奮闘中。

ABC137にHaskell縛りで参加しました!

概要

随分お久しぶりですね。 数カ月ぶりに記事を更新します。
今回は ABC137 に参加しました。

Haskell縛り ということで参加した本ABCですが、
非常に有意義なものになりました。
ここでは自分が解けた問題、ギリギリ解けなかった問題について取り上げます。

Haskellで競プロをやっている人の参考になれば幸いです。


A - +-x

開始2分で解きました。
これは問題文を愚直に実装するタイプの問題でしたね。

main = do
    [a,b] <- map read . words <$> getLine :: IO [Int]
    print $ maximum [a+b,a-b,a*b]

3つの演算でどれが一番大きい値になるかを答えられればOK.
特に述べることもないですね。

B - One Clue

開始7分で解きました。

k(黒の連続する数),x(黒の座標)が渡され、
黒の座標としてあり得る点を全て出力する、みたいな問題でしたね。

main = do
    [k,x] <- map read . words <$> getLine :: IO [Int]
    let xs = [a | a <- [x-k+1..x+k-1]]
        in putStrLn $ unwords $ map show xs

この問題のポイントは、

  • 数直線に 200001 個の石が置かれているということ
    • そして -100000 ~ 100000 の値を取るということ
  • それに対して、 k,xの値は -100 ~ 100 ということ

つまり、今回の場合
どうやってもxが端 になったり、
kが巨大すぎて片方が壁にくっついてしまう ということがない。
連続してk個置かれていたら必ずk通りの置き方が存在する ということです。

もし数直線が 0~5 の値しか取らないときに

n=2
k=5

となってしまうと、

○ ○ ○ ○ ○ ● | ● <- 数直線を超えてしまっている

というケースを考慮する必要があります。
こうなると私には解けません。いやわかんないけど。
少なくともこんなにスパッと解けることはなかったと思います。

上記解法を見ていただければわかると思うのですが、
取りうる座標の最小値から最大値までを列挙するためにリスト内包表記を用いています。

C - Green Bin

TLEで解けませんでした!!!!!

いやー、本当に悔しい。
ABCにHaskell縛りで初参加した私ですが、
最低でもB問題、頑張ってCを解くことを目標にしていました。

ただ解き方が最適でなかったのだと思います。

問題としては、
与えられたn個の文字列のうち
アナグラムのパターンでユニークを取り、
その数を出力すればいいということになります。

abc
bac
cab

であれば全て abc になります。
3つの要素から重複を許さず2つ取り出すと3通り、
その3通りが全て同じパターンを持つので解答は3となります。

私は愚直に

  • 各文字列を全てソートする
    • ソートすることで アナグラムパターンが同じかどうかをチェックできる
  • 文字列を2つ組み合わせで取ってくる
  • あとは全て == 関数でチェックするだけ!

みたいな感じでやりました。

import Control.Monad(replicateM)
import Data.List

comb k ns = filter ((k==).length) (subsequences ns)

main = do
    n <- readLn :: IO Int
    ss <- replicateM n getLine :: IO [String]
    print $ length $ filter (==True) [sort (head s) == sort (last s) | s <- (sss ss)]
        where sss = comb 2

comb 関数はWeb上に落ちていたものを参考にしました。
多分sort処理が長かったのかなー…

コンテスト中のインターネット検索は禁止されていません。

解説を見て勉強しようと思います…


終わりに

Haskell縛りでのABC初参加、とても楽しめましたし勉強にもなりました。
この習慣は是非継続したいところです。

最近ブログ更新してないけどどうしたの?

単純に やりたいことがとても多い のです。
インプットするよりもコード書いてたり何か作ってる時間が非常に長いので、あまり書けずにいますね…。

ただし ブログ続けていこうという気持ちは変わらず持ち続けている ので、
ちょくちょく記事上げていくつもりです。
もう少し落ち着いたらですけどね…。