駆け出し出遅れプログラミング初心者の日記

 初めましての方は初めまして、鳥居です。

今回は桁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だった場合には、それのさらに一個下の値は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

　…いや、だから何だって話なんですが…(;'∀')

父のやっているレースゲームを見ていると、やっぱりドライブっていいもんだなあと。

まあ、流石にレースゲームのように公道を自由気ままに走ってると警察の方につかまってしまうので行くときは安全運転で行きますが…(*_*;

こういう、「普通ではできないことをシミュレーションしてできる」というのはゲームの醍醐味かもですね。

　どうも、鳥居です。

ここ最近父がレースゲームに興味を持ち出したようで、folza horizonというゲームをやっています。(と言っても金欠なのでまだ体験版しかプレイできていませんが…orz)

そういえば自分も昔がグランツーリスモとかやってたなあとしみじみ。全くレースゲームの腕は上がりませんでしたが…orz

皆さんこんにちは、重傷を負っている鳥居です。

前回さらっとモナドに触れたり触れなかったりして結局大やけどしてしまったのですが、今回はさらにモナドについて深く掘り下げたり掘り下げなかったりしたいと思います。もしかしたらその過程で命を落とすことになるかもしれませんが、その時は黙とうでもしてやってください。

さて、前回は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)

早速ですが、皆さんは「モナド」という言葉は聞いたことがあるでしょうか？

ぶっちゃけ筆者が「モナド」という言葉を初めて目にしたのは、persona３というゲームの「深層モナド」という隠しダンジョンの名前からでして…って、そんなことはどうでもいいか。

恐らく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型の値と、ｆという「a型の値を引数にとり、Maybe b型の値を返す」関数が与えられた場合、ｘにｆを適用した値(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

まあ、もう少しだけ考えてみることにしますか。

https://www.amazon.co.jp/%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0-OCaml-%E3%80%9C%E9%96%A2%E6%95%B0%E5%9E%8B%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E5%9F%BA%E7%A4%8E%E3%81%8B%E3%82%89GUI%E6%A7%8B%E7%AF%89%E3%81%BE%E3%81%A7%E3%80%9C-%E4%BA%94%E5%8D%81%E5%B5%90%E6%B7%B3-ebook/dp/B00QRPI1AS

上の書籍で記されているヴァリアント型(これも代数的データ型の一つのようです)の例を参考にしてひも解いてみたいと思います。

この本では代数的データ型を、

「作り方に複数の方法があるようなデータ(型)」

と定義しているようです。

例えば、「図形」という抽象的な型があるとします。

図形といえば、

・点

・円

・長方形

・正方形

などの種類がありますよね？

これらをそれぞれ別個の型として扱うよりも、まず大きく

・図形

と定義してから

・図形の点

・図形の円

・図形の長方形

・図形の正方形

とまとめたほうが、なんていうか、気持ちいい(？)ですよね？(何を言ってるんでしょう私は…)

そういったときに役立つのが代数的データ型となります。

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」に相当しそうです。(本当に回りくどくなってしまった)

さすがにこれ以上長ったらしく書くと収拾がつかなくなりそうなので今日はこの辺にしておきます。お見苦しい文章をお見せしてしまい本当にすみませんでした。機会があればもう少しだけ掘り下げてみたいと思います。

小さいころから何度か見てきましたが改めて見るとすごい迫力ですね(;'∀')

皆さんも機会があればぜひ田老に見に来てください(*^_^*)

余談ですが3.11の津波は17ｍの高さまで来たんですね…(;・∀・)(写真の線の一番上のところまで)

自然の脅威ってすごい。

最後に何枚か写真を挙げておきます(@_@)

曇りだったのが若干悔やまれますがそれでもなかなか良い風景でした

というかこどふぉ自体ロシアとかアメリカとかの時間に合わせているようで日本だと夜中にしか参加できないのがなんとも(それでも参加している方は多いようですが…)

私は参加できなかったのでとりあえず問題だけでもちょろっと見てみましたが難しい…

https://codeforces.com/contest/1295/problem/A

Ａ問題からしてこれですからね…orz

問題の要旨としては、

・デジタル式の時計の一部分で表すことができる最大の整数はいくつか

みたいな感じですかね(相変わらず説明力が…)

例えば2が入力として与えられた場合、|を二個並べることにより１が表現できこれが最大の数になり、３だと

ー|

　|

みたいに並べて7が表示できてこれが最大の整数となる…こんな感じかな(*_*;

多分法則さえわかればすぐに解ける問題っぽいですが、頭の悪い私には難しい。

とりあえずチャレンジするだけしてみますが、すぐに解説みてしまうかも。

追記：これ多分２で割り切れる場合には１で全部埋めるのが最大の数で割り切れない場合には７を

先頭につければよさそうな感じですね…(まだ実装はできていませんが…)

さらに追記：普通にACしました。というか本当に上で書いたとおりでした。

int main()
{
ll t;
cin >> t;
rep(i,t){
ll n;cin >>n;
ll n2=n/2;
if(n%2 ==0){
rep(i,n2){
cout << 1;
}
}else{
cout<<7;
rep(i,n2-1){
cout <<1;
}
}
cout<<endl;
}
}

一応これがACしたコードです。(ライブラリを貼ると長くなるのでmain関数部分だけ貼ってますが…)

もう少しきれいなコードをかけるようになりたい(・.・;)あとrep文を回して数字を表現するってどうなんだ。TLEの可能性もあるし…。

B以降は…見なかったことにしておこう…。

こんにちは

…あー無理みたいですね…

htm要素だけなら大丈夫ですがjavascriptを埋め込むのはダメっぽいです…orz(なんか方法あるのかな…)