HaskellでDP(動的計画法)に向けて - Study : Google Code Jam 2009 - Round 1-C Problem C その２ [Google Code Jam]
fix(不動点演算子）を用いると再帰を抽象化できるそうで（という理解であっているのかな）、
昨日のコードを見直しました。
runSTの中で(f = solve' as)を束縛しないと、
runSTとは別のST s環境にバインドされてしまう罠にずいぶん悩まされました。
解答アルゴリズムでdo式を使うとアルゴリズムが見えづらくなるので
liftM*に置き換えてみたけれど、見やすくなったのかどうか・・・？
昨日のコードを見直しました。
runSTの中で(f = solve' as)を束縛しないと、
runSTとは別のST s環境にバインドされてしまう罠にずいぶん悩まされました。
解答アルゴリズムでdo式を使うとアルゴリズムが見えづらくなるので
liftM*に置き換えてみたけれど、見やすくなったのかどうか・・・？
HaskellでDP(動的計画法)に向けて - Study : Google Code Jam 2009 - Round 1-C Problem C [Google Code Jam]
Haskellって、一度ある引数で計算した関数を同じ引数で呼ぶと再度計算しちゃうんですね。
せっかく参照透明なんだから覚えてくれててもよさそうなもんだけど。
全部おぼえたらメモリが爆発するかもだから、関数定義で再計算の可能性があると宣言すると
覚えてくれるとかならないものでしょうかね。
プログラムコンテストではDPを使わないと計算量が爆発する問題がよく出るということで
Haskellではどうするのだろうと試してみました。
Wikipediaを参考にControl.Monad.STとData.Mapを使ったメモ化の実装をしてみました。
題材はGCJ2009 Round1Cの問題Cです。
下記のコードで、Largeサイズの解答に約16秒でした。
しかし型がやたらにややこしいですね。
また[Monad m a]から[a]を取り出すのにハマってしまいました。。。
ロジックを考えるよりも型エラーを取るほうに、まだまだ四苦八苦しています。
ちなみに問題を解くアルゴリズムの本体は53行目以降です。
そこまでは標準入力からの読み込みとメモ化の道具のライブラリとなっています。
再帰の際に「withMemo (Memo r) f」を書いているのがイマイチかも。
せっかく参照透明なんだから覚えてくれててもよさそうなもんだけど。
全部おぼえたらメモリが爆発するかもだから、関数定義で再計算の可能性があると宣言すると
覚えてくれるとかならないものでしょうかね。
プログラムコンテストではDPを使わないと計算量が爆発する問題がよく出るということで
Haskellではどうするのだろうと試してみました。
Wikipediaを参考にControl.Monad.STとData.Mapを使ったメモ化の実装をしてみました。
題材はGCJ2009 Round1Cの問題Cです。
下記のコードで、Largeサイズの解答に約16秒でした。
しかし型がやたらにややこしいですね。
また[Monad m a]から[a]を取り出すのにハマってしまいました。。。
ロジックを考えるよりも型エラーを取るほうに、まだまだ四苦八苦しています。
ちなみに問題を解くアルゴリズムの本体は53行目以降です。
そこまでは標準入力からの読み込みとメモ化の道具のライブラリとなっています。
再帰の際に「withMemo (Memo r) f」を書いているのがイマイチかも。
HaskellでGCJ (反省会 - Google Code Jam 2012 - Round 1-A Problem B) [Google Code Jam]
問題BもHaskellでやってみる。
条件によって処理を選択して次の状態を生成していく、という方針でしょうか。
こういうのは書きづらいですね。良いパターンを知りたいです。
case ofで連結版
今回は条件が3つだからいいですけれど、もっと増えるとしんどそう。
条件をリストにして、パターンマッチ機構で条件が成立するまで実行する版
これも、条件が増えるとリストが長ったらしくなっていまいち感が。
実行速度はcase ofの連結版と大体同じでした。
連結関数で連結版
smallサイズでは良いのですが、largeサイズにすると計算が終わりません。。。
solve関数を外に出したり中に入れたりいろいろ試したのですがうまく行きませんでした。
comb関数で一つ目の引数が正を返したら２つ目以降は評価しないと思うので、
計算量は変わらないと思うのですが。
リスト版と連結関数版の全ソースを載せておきます。
リスト版
連結関数版 - largeを解答不能
判定関数の真偽が反転しているのは、途中までspanでやっていたのですがbreakも
試してみたかったからです。
条件によって処理を選択して次の状態を生成していく、という方針でしょうか。
こういうのは書きづらいですね。良いパターンを知りたいです。
case ofで連結版
今回は条件が3つだからいいですけれど、もっと増えるとしんどそう。
条件をリストにして、パターンマッチ機構で条件が成立するまで実行する版
これも、条件が増えるとリストが長ったらしくなっていまいち感が。
実行速度はcase ofの連結版と大体同じでした。
連結関数で連結版
smallサイズでは良いのですが、largeサイズにすると計算が終わりません。。。
solve関数を外に出したり中に入れたりいろいろ試したのですがうまく行きませんでした。
comb関数で一つ目の引数が正を返したら２つ目以降は評価しないと思うので、
計算量は変わらないと思うのですが。
リスト版と連結関数版の全ソースを載せておきます。
リスト版
連結関数版 - largeを解答不能
判定関数の真偽が反転しているのは、途中までspanでやっていたのですがbreakも
試してみたかったからです。
HaskellでGCJ (反省会 - Google Code Jam 2012 - Round 1-A Problem A) [Google Code Jam]
B-small, B-largeをつまらないミスでWAしてeliminateされました。
本番に弱いなあ、まったく。
なんか悲しいので、勉強ついでにHaskellで解答を組んでみました。
入力パーサのコツを見つけるのにずいぶん手間取りましたが、なんとか以下の形になりました。
なにぶん初心者なので、よりシンプルな書き方があったらぜひコメントください。
まずは入力パーサの方式について。
IOアクションで、1行毎に数値1つ、および数値のリストを入力します。
数値1つを取得するIOアクション
IOモジュールのreadLnライブラリを利用します。
これは、標準入力から読み込んだ行をread関数で任意の型に変換して返してくれます。
入力したい値の型指定を、「IO a」の形で記述するのが最初はわかりづらいような。
数値のリストを取得するIOアクション
標準で良いライブラリが見つからなかったので、シンプルになるように作ってみました。
gcjの入力はスペースで区切られているので、wordsで個々の文字列のリストに分割してから
map関数でreadを適用します。
「mapM readIO」は「return . (map read)」と等価とのことで。
上記のIOアクションを用いて、入力をパースするアクションを組み立てます。
データ1つぶんを取得してタプルにするアクション
データを取得しながら、問題を解いて解答を表示するmainアクション
「sequence $ replicate t 」にたどり着くのには手間取りました。
「replicate t (IO a)」で問題数ぶんのIO aを生成し、sequence関数でIO aを順に実行します。
これでgetDataの結果のリストを取得するアクションを生成できるので、
「map solve ds」で解のリストを生成します。
あとはzip関数で問題番号と解の組みをタプルにし、format関数で解答文字列にして
purStrLnで表示します。
これ、mapを二重にかけるのってどうなのでしょうね？一重で行けないかな？
問題を解くアルゴリズムは、solve関数以下に実装します。
関数5つだけ。こういう問題は関数型に向いているのかな。
[p1, p2, ..., pA]から、[p1, p1*p2, p1*p2*p3, ..., p1*p2*p3*...*pA]を生成する関数initproductsを
作るのも時間がかかってしまいました。
初め、List.initsしたリストをproductsして生成しようとしたらまあ遅い遅い。
ex1関数は、
を変形した結果です。
文字の先頭からi文字目までBSで戻った場合、で計算しているので、(a-i)で計算しています。
A文字すべてをBSで消すパターンは、a+b+1 > b+2なので計算しないようにしています。
(zipの第一引数のリスト生成で[1..a]にしているところ)
一つ目のrealToFracは引数をカッコでくくらないとコンパイルが通りませんでした。なんでかな？
ghc -O2でコンパイルして、A-largeのサイズで解答時間は15秒くらいでした。
本番に弱いなあ、まったく。
なんか悲しいので、勉強ついでにHaskellで解答を組んでみました。
入力パーサのコツを見つけるのにずいぶん手間取りましたが、なんとか以下の形になりました。
なにぶん初心者なので、よりシンプルな書き方があったらぜひコメントください。
まずは入力パーサの方式について。
IOアクションで、1行毎に数値1つ、および数値のリストを入力します。
数値1つを取得するIOアクション
IOモジュールのreadLnライブラリを利用します。
これは、標準入力から読み込んだ行をread関数で任意の型に変換して返してくれます。
入力したい値の型指定を、「IO a」の形で記述するのが最初はわかりづらいような。
数値のリストを取得するIOアクション
標準で良いライブラリが見つからなかったので、シンプルになるように作ってみました。
gcjの入力はスペースで区切られているので、wordsで個々の文字列のリストに分割してから
map関数でreadを適用します。
「mapM readIO」は「return . (map read)」と等価とのことで。
上記のIOアクションを用いて、入力をパースするアクションを組み立てます。
データ1つぶんを取得してタプルにするアクション
データを取得しながら、問題を解いて解答を表示するmainアクション
「sequence $ replicate t 」にたどり着くのには手間取りました。
「replicate t (IO a)」で問題数ぶんのIO aを生成し、sequence関数でIO aを順に実行します。
これでgetDataの結果のリストを取得するアクションを生成できるので、
「map solve ds」で解のリストを生成します。
あとはzip関数で問題番号と解の組みをタプルにし、format関数で解答文字列にして
purStrLnで表示します。
これ、mapを二重にかけるのってどうなのでしょうね？一重で行けないかな？
問題を解くアルゴリズムは、solve関数以下に実装します。
関数5つだけ。こういう問題は関数型に向いているのかな。
[p1, p2, ..., pA]から、[p1, p1*p2, p1*p2*p3, ..., p1*p2*p3*...*pA]を生成する関数initproductsを
作るのも時間がかかってしまいました。
初め、List.initsしたリストをproductsして生成しようとしたらまあ遅い遅い。
ex1関数は、
を変形した結果です。
文字の先頭からi文字目までBSで戻った場合、で計算しているので、(a-i)で計算しています。
A文字すべてをBSで消すパターンは、a+b+1 > b+2なので計算しないようにしています。
(zipの第一引数のリスト生成で[1..a]にしているところ)
一つ目のrealToFracは引数をカッコでくくらないとコンパイルが通りませんでした。なんでかな？
ghc -O2でコンパイルして、A-largeのサイズで解答時間は15秒くらいでした。
反省会 - Google Code Jam 2012 - Qualification Round - Problem C. [Google Code Jam]
前回のProblem Bの間違いの答えは、
『P=2のときTi=2を見事に数え漏らします』
Problem C.
もう恥ずかしすぎですが晒します。
間違いは一箇所です。
あと、肝心のif文はもう少し良く書けますね。
CAUTION : Code listed below is WRONG at Large-size input, because of my small mistake.
『P=2のときTi=2を見事に数え漏らします』
Problem C.
もう恥ずかしすぎですが晒します。
間違いは一箇所です。
あと、肝心のif文はもう少し良く書けますね。
CAUTION : Code listed below is WRONG at Large-size input, because of my small mistake.
反省会 - Google Code Jam 2012 - Qualification Round - Problem B. [Google Code Jam]
いよいよ始まりましたGoogle Code Jam 2012。
まずは予選です。
Problem A.
単にアルファベット26文字をマッピングするだけなので省略します。
Problem B,Cですが、考え方はあっていたのに大ポカをやらかしてLargeで誤答してしまいました。
というわけで今回のお題は反省会です。
Problem B.
問題の内容は以下になります。
・N個のスコアを、分割した結果の差が1以内で3つに分割
・N個のうち、S個については、分割した結果の差が2になる
・分割した結果の最大値がP以上の数を数える
まずは分割した結果の差が1以内の条件で、分割した結果の最大値がちょうどPとなる最小値を
考えてみると、
(P-1, P-1, P)
となります。
次に分割した結果の差が2の場合を考えます。
先ほどの最小値から1引いた状態 (P-1, P-1, P-1)について1点だけ移動させると、
(P-2, P-1, P)となり、条件を満たします。
さらに続けると、
(P-2, P-1, P-1) => (P-2, P-2, P) : OK
(P-2, P-2, P-1) => (P-3, P-2, P) : NG
となります。
ここで、分割した結果の点数は0以上でなくてはならないので、
P-2 >= 0を満たすことが必要です。
というわけで実装したのが、恥ずかしながら以下の結果です。
なんとなく楽しいのでC++11のRange based forを使っています。
なにが恥ずかしいって、なんでわざわざ div 3した結果で判定しているんでしょうか。
そして肝心の大ポカですが、3つめのif分の"d > 0"が誤りです。
『分割した結果の点数は0以上』を判定したつもりだったのですが……
これ、ある条件で数え漏らします。
（そしてその条件がsmallにはなくlargeにのみ出現する罠)
この問題、こんなワケのわからない判定文を書かなくても、以下の条件で見るだけでOKでした。
・Ti >= (P-1) + (P-1) + P = 3P-2 のときは無条件に数え上げ
・Ti = (P-1) + (P-1) + (P-1) or (P-2) + (P-1) + (P-1) = > 3P-3, 3P-4の時は、
Sがまだ残っていれば数え上げ
ただし、 P-2 < 0のときは数え上げない
・上記以外は無視
Largeでも100問しか無いので余裕です。
まずは予選です。
Problem A.
単にアルファベット26文字をマッピングするだけなので省略します。
Problem B,Cですが、考え方はあっていたのに大ポカをやらかしてLargeで誤答してしまいました。
というわけで今回のお題は反省会です。
Problem B.
問題の内容は以下になります。
・N個のスコアを、分割した結果の差が1以内で3つに分割
・N個のうち、S個については、分割した結果の差が2になる
・分割した結果の最大値がP以上の数を数える
まずは分割した結果の差が1以内の条件で、分割した結果の最大値がちょうどPとなる最小値を
考えてみると、
(P-1, P-1, P)
となります。
次に分割した結果の差が2の場合を考えます。
先ほどの最小値から1引いた状態 (P-1, P-1, P-1)について1点だけ移動させると、
(P-2, P-1, P)となり、条件を満たします。
さらに続けると、
(P-2, P-1, P-1) => (P-2, P-2, P) : OK
(P-2, P-2, P-1) => (P-3, P-2, P) : NG
となります。
ここで、分割した結果の点数は0以上でなくてはならないので、
P-2 >= 0を満たすことが必要です。
というわけで実装したのが、恥ずかしながら以下の結果です。
なんとなく楽しいのでC++11のRange based forを使っています。
なにが恥ずかしいって、なんでわざわざ div 3した結果で判定しているんでしょうか。
そして肝心の大ポカですが、3つめのif分の"d > 0"が誤りです。
『分割した結果の点数は0以上』を判定したつもりだったのですが……
これ、ある条件で数え漏らします。
（そしてその条件がsmallにはなくlargeにのみ出現する罠)
この問題、こんなワケのわからない判定文を書かなくても、以下の条件で見るだけでOKでした。
・Ti >= (P-1) + (P-1) + P = 3P-2 のときは無条件に数え上げ
・Ti = (P-1) + (P-1) + (P-1) or (P-2) + (P-1) + (P-1) = > 3P-3, 3P-4の時は、
Sがまだ残っていれば数え上げ
ただし、 P-2 < 0のときは数え上げない
・上記以外は無視
Largeでも100問しか無いので余裕です。
Google Code Jamの入力〜解答〜出力をテンプレートで実装してみるテスト [Google Code Jam]
Google Code Jamでは標準入力からテキストでデータを入力して、
そのデータを元に解答を計算して出力する、という定形処理になるので、
この定形処理の部分をテンプレートでうまく書けないかな、と試してみたテストです。
使い方はこんな感じ。
先日のGCJ2009 Round2-A問題の解答です。
・入力からデータを生成する関数オブジェクト
・生成したデータを処理して解く関数オブジェクト
を渡すと、それらを使って入力データを処理します。
……ううむ。思っていたほどシンプルにはならなかったなあ。
問題を解く関数オブジェクトへの引数の型を内部でstd::pairのテンプレート型に使っているので、
入力から出力へは何らかの型を渡す必要があります。
と書いてから思ったけれど、std::pairって許されるのかな?
うん、多分使わない。
そのデータを元に解答を計算して出力する、という定形処理になるので、
この定形処理の部分をテンプレートでうまく書けないかな、と試してみたテストです。
使い方はこんな感じ。
先日のGCJ2009 Round2-A問題の解答です。
・入力からデータを生成する関数オブジェクト
・生成したデータを処理して解く関数オブジェクト
を渡すと、それらを使って入力データを処理します。
……ううむ。思っていたほどシンプルにはならなかったなあ。
問題を解く関数オブジェクトへの引数の型を内部でstd::pairのテンプレート型に使っているので、
入力から出力へは何らかの型を渡す必要があります。
と書いてから思ったけれど、std::pair
練習 - Google Code Jam 2009 - Round2 - A - for large [Google Code Jam]
問題の解き方をいろいろシミュレーションして気がついたこと。
単に、上の行から順に、条件を満たすように行を埋めていけば良かったという。
難しく考えすぎるのも良くないですねえ。
上に移動する行を捜すのとswap操作は同時にできるので、
同時にやってループ回数を減らすとか小賢しいことをしてみたりして。
計算量は O(n2)ですがn=40なのでまあ大したことは無いでしょう。
単に、上の行から順に、条件を満たすように行を埋めていけば良かったという。
難しく考えすぎるのも良くないですねえ。
上に移動する行を捜すのとswap操作は同時にできるので、
同時にやってループ回数を減らすとか小賢しいことをしてみたりして。
計算量は O(n2)ですがn=40なのでまあ大したことは無いでしょう。
mick.neumann さん
-
nice! 3
記事 47
テーマ パソコン・インターネット
プロフィール
ブログを紹介する
