近々ブログを再開する…予定です。
予定です…(;'∀')
本当に大分間が空いてしまいましたね…orz
予定です…(;'∀')
本当に大分間が空いてしまいましたね…orz
こんにちは。鳥居です。おしさしぶりです。
今日なんですが、実はHaskellのモナドについて調べているうちに俄かに圏論に興味を持ち始めてしまい(結局モナドの記事はエタったままなのですが…orz)圏論について雑にまとめてみようかなと思った次第です。モナドの記事はいつか必ず書く!(フラグ)
…とはいっても、これも残念ながら勉強を始めたばかりの永遠の初心者が書く記事で、あまり深い内容に踏み込むことはありません。ご了承ください。
さて、とりあえず圏についての論というわけで「圏」の定義についてまずは確認していきます。
https://ja.wikipedia.org/wiki/%E5%9C%8F_(%E6%95%B0%E5%AD%A6)
数学の一分野である圏論において中核的な概念を成す圏(けん、英: category)は、数学的構造を取り扱うための枠組みであり、数学的対象をあらわす対象とそれらの間の関係を表す射の集まりによって与えられる。圏はそれ自体、群に類似した代数的構造として理解することができる
…案の定早速わけが分かりませんね(;'∀')
ただ、ここから読み取れることとしては、どうやら圏というのは対象とそれらの間の射と呼ばれる概念から成り立つ代数的構造だといえることでしょうか。
もう少し掘り下げていこうと思います。
「圏論の道案内~矢印でえがく数学の世界~数学への招待」
https://www.amazon.co.jp/%E5%9C%8F%E8%AB%96%E3%81%AE%E9%81%93%E6%A1%88%E5%86%85-%E7%9F%A2%E5%8D%B0%E3%81%A7%E3%81%88%E3%81%8C%E3%81%8F%E6%95%B0%E5%AD%A6%E3%81%AE%E4%B8%96%E7%95%8C-%E6%95%B0%E5%AD%A6%E3%81%B8%E3%81%AE%E6%8B%9B%E5%BE%85%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E8%A5%BF%E9%83%B7-%E7%94%B2%E7%9F%A2%E4%BA%BA/dp/4297107236/ref=sr_1_2?__mk_ja_JP=%E3%82%AB%E3%82%BF%E3%82%AB%E3%83%8A&keywords=%E5%9C%8F%E8%AB%96&qid=1583127028&sr=8-2
この本の中でも圏(category)とは、対象(object)と射(arrow,morphism)とからなるある種のシステムと説明されています。
そしてさらにこの「対象」と「射」は「圏の公理」を満たす限りはどのような種類のものでも構わないと説明されています。
「圏の公理」について説明する前に、まずは簡単な例から始めると、
・水が液体から(温度を上げていくことによって)気体になるという状態変化(この場合は水の液体と気体の状態が対象であり、温度を上げるという操作あるいは温度が上がるという変化が射)
・大小関係にあるもの(自然数など)の間にある大きさの関係(もの自体が対象で関係が射)
などでしょうか。難しい。
とにかくこのようにある概念と他の概念の関係性であったり、ある概念に操作を加えた結果であったりといった「抽象的な関係」を示したものが圏であるといえるでしょう。いえるはず。
次に射についての定義を一つ挙げます。
・どんな射に対しても、域(domain)と呼ばれる対象と余域(codomain)と呼ばれる対象とがただ一つ存在する。射fの域がA,余域がBであることを
f
b <- A
と書き、「fはAからBへの射である」という。また射fの域をdom(f),余域をcod(f)と記す。
先ほど挙げた最初の例を挙げると「液体の水」が域で「気体の水」が余域、「温度を上げること」が射に相当するといえるでしょう。
さらに、射の「合成」について説明します。
・射f,gについて、cod(f)=dom(g)であるならf,gの合成(composition)と呼ばれるdom(f)からcod(g)への射が一意に存在する。これをg◦fと書く。
これについては、ベクトルの合成を思い浮かべてもらえれば分かりやすいと思います。aからb、bからcへのベクトルがそれぞれ存在するときは、aからcへのベクトルも二つのベクトルを足し合わせることによって得られることと同じことと解釈してもよさそうです。
といったわけでとりあえず最初はここまでにしたいと思います。続けれるかどうかは…皆さんの応援次第です。なんつって。(ある程度圏論の話がまとまってきたらそこから改めてモナドについて説明していく所存です。いければだけど。)
詳しいことは後ほどとさせてください…orz
こんにちはです。鳥居です。
今回は二分探索についてまとめていこうと考えています。
とはいえ流石に私なんかより皆さんのほうが二分探索について詳しいと思うので参考にはならないとは思うのですが、、、
とりあえず二分探索の具体的な方法について書くと、
・あるソートされたリストから特定の条件を満たす値(ある数未満の中で最大の値など)を求めるとする
・適当にとても小さい値ととても大きな値(それぞれ-INFとINFとして定義されることが多いですね)をとる。
・それらの値を足して2で割った数(中央値)より大きければ中央値を小さいほうの値に再設定し、小さければ中央値を大きいほうの値に再設定することを繰り返す。
・最終的に小さいほうの値と大きいほうの値の差がなくなった時求めたい値が出てくる
こんな感じですかね。…相変わらず説明が下手だorz。
さて、この二分探索ですが、普通の探索と比べて何が良いのでしょうか?
まず、「走査したいリストの要素数が比較的大きくても計算量が少なくて済む」ところですね。
例えば要素数が10^18ほどあるリストだと、普通の探索では最悪それに比例した時間(10^18)がかかってしまいますが、これが二分探索だとlogがつくおかげでlog10^18=18*log10≒54と、圧倒的に計算量が小さくなります。これは驚きですね。
また、「あるN個の要素からなるリストから二個値を取り出して特定の値を求めたい」時なども、通常はN個要素それぞれに対してN-1個の要素を試していくとおおよそN^2の計算量がかかることになってしまいますが、片方の要素を全て試し、もう片方の要素を二分探索するといった方法を用いればNlogNの計算量となり、これも大幅な時間短縮となります。
このように、アルゴリズムを工夫するだけで計算にかかる時間が驚くほど速くなるというのは非常に魅力的です。是非自分でも取り入れていきたいですね。
こんにちは、鳥居です。
今日は、昨日参加したcodeforcesについて書いていきたいと思います。
というわけで結果なんですが、見事に1完しましたー(^_-)-☆パチパチパチ
はい、爆死しました。
B問題はまだ決まってない値の両隣の値のminとmaxを求めて2で割ればよかった話だったんですね…orz
まだまだ精進が足りないです(*_*;
今ちらっと見たところC問題も計算量O(1)で解けるような問題だったっぽいですね。
常々思うのですが、こういった「難易度自体はそんなに難しくなくても一考察必要」な問題で変に躓かないようにするためにはどうすればよいのでしょう…難しい。
初めましての方は初めまして、鳥居です。
今回は桁DPというやつにチャレンジしてみたいと思います。(実は記事作成途中にデータが吹っ飛んでしまい、一からまた書き直しているところです。…完全に自業自得orz)
https://atcoder.jp/contests/abc154/tasks/abc154_e
まず入力ですが、int型どころかunsigned long long型でもオーバーフローしそうなので、string型で受け取っておくことにします。(C++以外の言語ではこれ以上の値でも受け取れる型があるようなので、それを使ってもいいかもしれません)
さて、肝心の解き方ですが…どう解くんでしょう?(;'∀')(オイオイ)
自力で解くのはあきらめて(はえーよ)、他の方の桁DPについての記事を参照してみたいと思います。
https://torus711.hatenablog.com/entry/20150423/1429794075
「ある整数N以下の整数で、かつ特定の条件を満たす値を求める」ときに使えるのが、桁DPというものっぽいです。まさに今回のような問題ですね。
そして具体的な方法としては、上の桁の値から見ていくDPを考えていくようです。こういったときに桁ごとの値を参照しやすいといった面でもstring型で値を受け取ったほうがいいというメリットがありそうですね。
そしてdpを回していくわけですが、どうやらパラメータとして
・上から見て行ってすでに決まっている桁数
・求めたい値の条件(この場合だとゼロでない値の数[1~3])
そしてもう一つ
・その桁の次に小さい桁を見たときに、その桁の値がすでに決まっている桁と合わせて入力として与えられた値未満かその値と同じか
というフラグが必要になってくるようです。(相変わらず自分で書いてても意味が…(;'∀'))
例えば入力として12345が与えられ、上から二けた目までの数(12~)までが決定しているとして、
・3桁目が3未満だった場合には、それより下の桁は何を選んでもよい。
・3桁目がちょうど3だった場合には、それのさらに一個下の値は4までしか選べない
・3以上の値を3桁目に入れるわけにはいかない
ので、このようなフラグをまえもって準備しておくと後の計算が楽になるっぽいです。
そして、上から順々に値を埋めていって最後に求められているクエリを提出すればよい…らしいです。(初心者なので自信ないorz)
桁DPについて更に知りたい方は(私が書いたこんな残念な記事より)ほかの方の記事を参照してください。(一番下にあげたmaspyさんという方の解法は今回紹介したものとはまた別の解法となっているようなので、特にご覧いただくのをおすすめします。)
http://drken1215.hatenablog.com/entry/2019/02/04/013700
https://maspypy.com/atcoder-%e5%8f%82%e5%8a%a0%e6%84%9f%e6%83%b3-2019-02-09abc-154
皆さんこんにちは、重傷を負っている鳥居です。
前回さらっとモナドに触れたり触れなかったりして結局大やけどしてしまったのですが、今回はさらにモナドについて深く掘り下げたり掘り下げなかったりしたいと思います。もしかしたらその過程で命を落とすことになるかもしれませんが、その時は黙とうでもしてやってください。
さて、前回はMaybeモナドの実装内容について語らせていただきました。その中で、
・return関数という、素のa型のxという値をJust xというMaybe a型の値にして返す関数
・>>=演算子という、Maybe a型の値と「a型の値を引数にとり、Maybe b型の値を返す関数」を引数にとり、Maybe b型の値を返す演算子(関数)
が定義されていることを説明しました。…説明したつもりです。
もう少しMaybe型における>>=演算子について説明すると、
・値としてNothingが渡された場合にはそのままNothingを返す
・値としてJust xと関数f(a型の値を引数にとり、Maybe b型の値を返す関数…くどいですねすいません)が渡された場合にはxにfが適用された値を返す
ふるまいをするものでした。
お詫び・モナドについて詳しく調べていたところもう少しまとめる必要が出てきたのでここから先は執筆中とさせてください(;'∀')(なるべくエタらないようにしますので…)
皆さんこんにちは。相も変わらず鳥居です。
さて、毎回恒例の「素人がプログラミングを雑に勉強しようとして大やけどをする」シリーズをやっていきたいと思います(そんなに恒例になってないかorz)
早速ですが、皆さんは「モナド」という言葉は聞いたことがあるでしょうか?
ぶっちゃけ筆者が「モナド」という言葉を初めて目にしたのは、persona3というゲームの「深層モナド」という隠しダンジョンの名前からでして…って、そんなことはどうでもいいか。
恐らくHaskellを勉強している、あるいは業務などで使用している方なら知っているのみならずゴリゴリに使っているのがモナドだと思われます。また、そうでなくともプログラミングを勉強している方なら一度ならず目にしているのではないでしょうか?
さてそんなモナドですが、ネットで情報を収集していると、
・モナドとは計算を表現する構造である。
・returnメソッドと>>=演算子が定義されている。
・Haskellで入出力を行うためにはIOモナドが必須
・素人は今すぐモナドを深く理解しようとするのをやめろ
といった説明がなされています。…間違っても私が手を出すべきものではないですね…orz
…とりあえず、すこーしずつモナドに手を突っ込んでは引っ込めることをやっていくことにします。
まず具体例としてwikipediaからの引用を見てみることにします.
https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8A%E3%83%89_(%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0)
data Maybe t = Just t | Nothing
上がMaybeモナドの宣言となっています。先頭にdataとついているということは代数的データ型であるということですね。…多分。
使用例を見てみると、
add :: Maybe Int -> Maybe Int -> Maybe Int
add mx my =
mx >>=(\x ->
my >>=(\y ->
return (x + y)))
見たいに使うようです。…早速わけが分かりません。
とりあえず、このadd関数は、
・引数に Maybe Int 型を二つとり
・返り値として Maybe Int型の値を返す
関数でしょうか…?うーん分からん。
などと泣き言をいうのはやめてもうちょい観察してみることにします。
・>>=演算子が存在する。
・解説を見てみると、mxとmyがNothing ではない場合に限りこの関数は成功する。
・さらに解説を見てみると、
return :: a -> Maybe a
return x =Just x
というメソッドがMaybeモナドには実装されている。
といったことがわかります。
おや?一番最初の方で書いた、
・returnメソッドと>>=演算子が定義されている。
というモナドの原則が一番目と三番目の観察結果から見て取れます。ふむ、ちょこっとだけ考える糸口が見えてきました。
returnメソッドから見ていきます。
return :: a -> Maybe a
これがreturnメソッドの宣言内容です。aという型を引数にとり、Maybe aという型にして返すメソッドらしいですね
return x = Just x;
ここでいうJust とはMaybe型を代数的データ型と見たときのコンストラクタに値しそうです。よってこのメソッドは、型aのxという値をJust xという型Maybe aの値にして返す関数となるようです。
次に>>=演算子についてみてみる…その前にHaskellの演算子について少し触れておきましょうか。
Haskellでは、演算子も関数の一つとしてみなされるようです。例えば、
1 + 2
という演算(もちろん答えは3になりますよね?)があった時、
(+) 1 2
という風に、関数っぽく書けるようです。というよりは、1+2の方が(+) 1 2の別名であると言ったほうが正しいでしょうか。
それを踏まえて>>=の宣言も見てみることにします。
(>>=)::Maybe a -> (a -> Maybe b)-> Maybe b
見てもらえばわかる通り(…大丈夫ですよね?)、(>>=)演算子はMaybe型においては
「Maybe a型の値と、「a型の値を引数にとり、Maybe b型の値を返す関数」を引数にとり、Maybe b型の関数を返す」関数であることがわかります。…頭がこんがらがってきた。
具体的な内容は、
NOthing >>= _ =Nothing
(Just x) >>= f =f x
となっています。関数型言語特有のパターンマッチ記法が出てきていますが、それはこの際無視(!)するとして、どうやらこの関数は、
・NothingというMaybe a型の値が与えられた場合にはそのままNothingを返す。(…実際には_というワイルドカードで「a型の値を引数にとり、Maybe b型の値を返す関数」を…難しくなりそうなのでこれ以上は書きません)
・Just xというMaybe a型の値と、fという「a型の値を引数にとり、Maybe b型の値を返す」関数が与えられた場合、xにfを適用した値(Maybe b型の値)が返される
演算子(関数)となっているようです。…疲れた。
さらにその上で先ほどのadd関数を見てみると
add mx my =
mx >>=(\x ->//ここでmxというMaybe Int型の値と\x以降の「Int型の値を引数にとり、Maybe Int型の値を返す関数」を引数にとり、
my >>=(\y ->//ここでmyというMaybe Int型の値と\y以降の「Int型の値を引数にとり、Maybe Int型の値を返す関数」を引数にとり、
return (x + y)))//最終的にxとyを足したものをMaybe Int型にして返す
関数となっている…もう無理。
-------------------------------------------------------------------------------------------------
今回のまとめとしましては、
・素人がモナドを深く理解しようとすると大やけどする
になるでしょうか…ぐふっ(続くかもしれない)。
どうもこんにちは。毎度おなじみ鳥居です。
今回も例によって例のごとく、プログラミング初心者がプログラミング手法について雑にまとめていこうと思います。駄文雑文ご容赦くだ(ry
https://atcoder.jp/contests/abc153/tasks/abc153_e
さて、いきなりですがトキさんがモンスターと戦っています。
モンスターのヒットポイントと攻撃の種類が与えられ、それぞれの攻撃方法について攻撃力と魔力の値が設けられています(同じ攻撃方法を何度も選んでよい)。トキさんがモンスターを倒すまでに必要な魔力の最小値はいくらになるでしょうか?という問題です。
そして結論から言えばこの問題は「個数制限なしナップサック問題」という有名問題をアレンジした問題だそうです。
この「個数制限なしナップサック問題」について簡単に説明すると、
「入れることができる重さの最大値が定まったナップサックに、重さと価値がそれぞれ決められている荷物を、同じものを二つ以上入れてもよいという条件で入れたときに価値の最大値を求めよ」
という問題です。この場合ですと、重さの最大値をモンスターのヒットポイント、荷物の重さと価値をそれぞれトキさんの攻撃力と魔力に対応させればよさそうですね。
さあ、この問題はどう解くべきでしょうか。
以前動的計画法について(雑に)まとめたエントリで、各々の荷物を入れるか入れないかで分けて解こうとすると計算量がとんでもないことになると説明しました。さらに今回は個々の入れれる荷物の量も無制限ですので、その量も鑑みるとさらに計算量が増えることになりそうです。
となると、動的計画法の出番になる予感がしてきます。具体的にはそれぞれの攻撃方法について、ヒットポイントの値を一つずつ増やしながら攻撃回数と攻撃力の数を掛けた値までdpテーブルを埋める方法が考えられそうです。
…なんですが、この方法でもまだ計算量が多くなりそうです。攻撃回数まで考えると三重ループになってしまいますからね…orz
どうしましょう。どうしましょうか。お手上げです。
こんなときは私たち競プロerにとってのバイブル、通称蟻本の助けを借りましょうか。
https://www.amazon.co.jp/dp/B00CY9256C/ref=dp-kindle-redirect?_encoding=UTF8&btkr=1
この本の中で個数制限なしナップサック問題はこんな風に解けばよいと書いてあります(私自身の読解ミスがあるかもしれません。また、説明文中のiはi種類目までの荷物の選び方、jは重さの最大値、w[i]はi番目の荷物の重さを表していると思ってください)
「dp[i+1][j](iの種類を一つ増やしたときのdpテーブルの値)の計算においてk(>=1)個選ぶ場合は、dp[i+1][j-w[i]](すでに求めてある、iの種類を一つ増やして重さからw[i]を引いたときの値)の計算においてk-1個選んだ場合と同様であるため、dp[i+1][j]の漸化式におけるk>=1の部分の計算はすでにdp[i+1][j-w[i]]の計算時に行っている。よってその値に価値を足したものと、今現在の値を見比べて適している数でdpテーブルを埋めればよい」
…はい。自分で書いててわけが分からなくなりましたorz。まだまだ勉強が足りなさそうです(:_;)
とにかく(投げた)、このような計算方法でdpテーブルを埋め最終的に求められている解を出せばよさそうです。
いくつか注意しなければならないのが、ABC153-Eの問題では「モンスターの体力を決めたときの魔力の最小値」を求めるべき(魔力の値を決めたときのモンスターのヒットポイントの最大値を求めると計算量がオーバーしてしまう)ことと、答えはdp[H]<=dp[i]<dp[H+maxA_i]の間の最小値であること(dp[H]をmaxA_iまで更新する必要がある)でしょうかね。うん、やっぱり訳が分からなくなって(ry
以上で私の雑な説明は終わりです。ぶっちゃけ他の方の簡潔かつ丁寧な説明記事をご覧になられたほうがいいですね…orz
http://drken1215.hatenablog.com/entry/2020/01/26/225000
上にけんちょんさんという競プロ界隈では知らない人はいないであろうすごいお方が書いた今回の問題の解説のリンクを貼ったので、もしよろしければこちらを参照してください。(私の書いたものよりずっと分かりやすい説明が載ってますので…)
どうも、鳥居です。今回はHaskellやOcamlなどの関数型言語に特有の代数的データ型について考えてみたいと思います。例によって超初心者が書き下した雑文なので多々到らない部分があると思いますがご了承ください(;'∀')
https://ja.wikipedia.org/wiki/代数的データ型
さて、この代数的データ型ですがwikipediaではこのように書いてあります。
「代数的データ型の値(データ)の感覚的な説明としては、引数で与えられた他のデータ型の値を、コンストラクタで包んだようなもの、である。」
…はて、何のことでしょうか…(@_@)
コンストラクタってあれですよね。Javaとかでクラスを作るときにフィールドの値を初期化するときとかに使うあれですよね。それでデータ型の値を包むっていうのは…どういう意味だ(+o+)
とりあえずHaskellで代数的データ型を宣言するときにどう書くのか見てみますか。
data Node = Leaf Integer | Branch Node Node
…うーん、分からん。
などと泣き言をのたまうのはやめてよくよくどういう意味なのか考えてみるとどうやら、
・まずある複数の型を表す抽象的で大きな型がある
・その型に含まれる型をその大きな型に代入(?)することで抽象的だったその大きな型の具体的な型が決定する
…感じみたいです(*_*;
うん、素人が雑に手を出すべきやつではなかったorz
まあ、もう少しだけ考えてみることにしますか。
上の書籍で記されているヴァリアント型(これも代数的データ型の一つのようです)の例を参考にしてひも解いてみたいと思います。
この本では代数的データ型を、
「作り方に複数の方法があるようなデータ(型)」
と定義しているようです。
例えば、「図形」という抽象的な型があるとします。
図形といえば、
・点
・円
・長方形
・正方形
などの種類がありますよね?
これらをそれぞれ別個の型として扱うよりも、まず大きく
・図形
と定義してから
・図形の点
・図形の円
・図形の長方形
・図形の正方形
とまとめたほうが、なんていうか、気持ちいい(?)ですよね?(何を言ってるんでしょう私は…)
そういったときに役立つのが代数的データ型となります。
Ocamlでの宣言方法を例にとると、
type figure=(*figure型の宣言*)
|Point(*点*)
|Circle of int(*円*)
|Rectangle of int * int(*長方形*)
|Square of int ;;(*正方形*)
といった感じに宣言します。具体的に値を生成するときは、
let c = Circle 3;;
と記述します。こうすることで
val c:figure(*cはfigure型*) = Circle (*cはCircle(円)である*) 3;;
といった感じで構築されます。…難しい('Д')
ここで先ほどのwikipediaの説明に戻ってみます。
「代数的データ型の値(データ)の感覚的な説明としては、引数で与えられた他のデータ型の値を、コンストラクタで包んだようなもの、である。」
上の例だと、「Circle」がどうやらコンストラクタで、「figure」が代数的データ型に相当しそうです。
じゃあ、3は…?
すみません。説明不足でしたね(:_;)
コンストラクタを定義したときの
of int
や
of int * int
は、大きさを決めるときに必要なものでした。円だと、
・int型の値一個を半径として引数にとって
・半径×半径×3.14
が大きさとして返されればいいですし、長方形だと
・int型の値二つを引数にとって
・縦×横
を大きさと返せばよいわけです。(本当に申し訳ございません。ここらへんは後で文章を推敲しますorz)
…ということは? そうですね。「引数で与えられた他のデータ型」が上での「3」に相当しそうです。(本当に回りくどくなってしまった)
さすがにこれ以上長ったらしく書くと収拾がつかなくなりそうなので今日はこの辺にしておきます。お見苦しい文章をお見せしてしまい本当にすみませんでした。機会があればもう少しだけ掘り下げてみたいと思います。