よく知らないHaskellを使っていくスタイル。
水着→サンタ服→めがね→その他有象無象の順番で書いたので問題の難易度が上がるほど経験値が少なそうなコードに。
クソコードを晒す勇気が足りなくて体が震える。こたつほしい。
コードを書く前にこのサイトを読みました。
Haskellで競技プログラミング IO編
http://qiita.com/siquare/items/ec0c01c81c22ce060405
コードを書いているときはこのサイトを参考にしました。
Haskellのリスト操作関数リストアップ(一覧)
http://uid0130.blogspot.jp/2014/07/haskell.html
水着
水着の提出数が多いのは一番難しいから提出数が多いのであって、血眼になって「早く脱げよぐへへ」する紳士が多いのではないと声を大にして言いたい。
多倍長な整数を扱える言語勢はとりあえず階乗を求める関数を作って10と15でテストした後に提出してtimelimitに引っかかるまでが第一段階。
巨大な数に掛け算をする計算コストとか○○を法として合同とかいう数学の呪文を思い出して1回の掛け算ごとに末尾の0やmod(10**6)の処理をするように改良して提出してやっぱり何かダメで引っかかるのが第二段階。ここがスタートライン。
具体的な数を思いつけないから雑な例を出すけど、元の数が
111111111111114
こんな数だったとして下9桁取ると
111111114
これに500かけると
55555557000
になって0を削除すると
55555557
となってなんか桁足りないよね。と思い至ってゴールとなる。
2の倍数や5の倍数を処理するのがよさそうだけど、計算途中の数の桁を少し多めに取っておいて最後に削る方法で通ってしまったのでここで考えるのをやめた。
サンタ服
本来関数型の強さが出る問題であるはずなのだが計算前のごちゃごちゃした整形が酷くて良さが全く出ていないコード。[10]と[1,3,4]を渡すと[1,2,1,6]が返るcutが平和なのが救い。
[x * y | x <- [1,2,3], y <- [4,5,6]]
と書くと
[4,5,6,8,10,12,12,15,18]
のような総当りしたリストが帰ってくるのでその最小値を取る。
めがね
見ろよこれ。is_match_yx関数もcalc関数で帰ってくるリストも問題に合わせて座標軸をy, xとしているのにsearch関数だけx, yなんだぜ。IOが比較的まともに見れるようになったのに台無しである。
テストケースの条件をみてNとMが最大値を取ったとしても総当りで良さそうなので愚直に計算。
haskellは
[[1,2,3],[4,5,6]] == [[1,2,3], [4,5,6]]
True
みたいな比較ができるのでとある座標からパターンと同じサイズを切り取って比較する。
必ずどこかで一致するという条件なので一致しない場合は考えない。
to_sとかいう関数作っているけど今ならintercalate使う。
この3つができれば後は消化試合。無事完走。
そんなことより艦これのお飾り材料イベントまだやってない。
追記
Haskellは関数型なんだからその気になればワンライナーだよね。
例えばセーラー服の問題はこのように書ける。
main=readLn>>=sequence.flip replicate getLine>>=putStrLn.let f x=if tail x==[]then head x else head x++"_"++f(tail x)in f
水着はこう。
main = readLn >>= \n -> print $ flip mod 1000000000 $ foldl (let func a b = mod (let stripzeror n = if n `mod` 10 == 0 then stripzeror (n `div` 10) else n in stripzeror(a*b)) (let mod5count n x = if x `mod` 5 == 0 then mod5count (n+1) $ x `div` 5 else n in 1000000000 * (10^(mod5count 0 (b+1)))) in func) 1 [1..n]
見づらい。
0 件のコメント:
コメントを投稿