2020年 6月 3日
今回の記事はおまけ付きです せっかくなので、今後このブログは3才児が書いたものとして温かい目で見ていただけると嬉しいです。
少なくとも私は自身のブログを3歳の頃の僕が書いたものとして見ています。
まえがき
さて、問題です。 今何時でしょう
私は九州男児です。
はぁ
眠気が原因かしらないけど語りが多めです。
トイレに入って「そういえば下宿始めてから足の小指をぶつけることが無くなったな…」ってふと思い、部屋に戻るときにくるぶしぶつけました。
そういえば下宿っていう言葉なんですが、「誰か別の家族の家にお世話になること」だと思っていました。 （つまり、今の僕の状況は"一人暮らし"って言うだけだと思ってた)
おまけ
さて、第一回 にぼにぼのお気持ちプログラミング講座でございます。 講座ではないけど。
前回のC問題ABC169 C- Multiplication 3で,a.bc の形の小数をstring型で受け取ってabcの形（つまり、オーバーフロー？とか気にしないでただしく100倍して受け取りたい)で受け取る。っていうのやったと思うんですけど、abc.xyzとかの形でもabcxyz(1000倍して受け取る)みたいなのやりたいな〜って思って書きました。 動作チェックとかよくわからないことは知らないのですが一応作ったので.
(ちなみに,12.34500みたいなときにどうするかみたいなのはとくに考えてないけど、まぁ1234500を作る。ってなってるんだと思います)
// abc.xyzの形をabcxyzに変換して、更に何倍したのかも返す。 pair<long long, long long> doubleToLL (string s){ pair<long long, long long> ret; ret.first = 0; ret.second = 1; //小数の形じゃなかった時用にsecondは1にしとく long long mul = 1; for(int i = s.size() - 1; i >= 0; i--){ if(s[i] == '.') ret.second = mul; else { ret.first += mul * (s[i] -'0'); mul *= 10; } } return ret; } int main() { string s; cin >> s; pair<long long, long long> a = doubleToLL(s); cout << a.first << endl; cout << 1.*(a.first) / a.second << endl; }
これで、1.234っていう入力に対しては1234として受け取ってくれる(1000倍したよっていうのも教えてくれる)
0.99 は99 として受け取ってくれる(100倍したって教えてくれる)
1010は 1010として受け取ってくれる（1倍したって教えてくれる)
そんなノリです。
ちなみに、Xとして受け取ってくれるのXが返り値.firstで、Y倍したって教えてくれるっていうのが返り値.secondです。
まぁ、一回実装しておくかってぐらいのノリです。
実装の方針としては、返したい値（abcxyz)を返すために、文字列引数sに対して0番目の要素から順に見ていくと、最初の要素を何倍して受け取ればいいか分からないので、小数第X位(Xは文字列s={abc.xyz}のzに対応するやつ）（つまり、一番右のやつ)は1倍して受け取る、その次は10倍〜〜って感じでやっていきました。 abc.xyzの小数点つまり.(ドット)がでてきたら、xを〜倍した後のなので〜を返して上げれば良いや！！っていうノリ
ちなみに返り値2つやるうまい方法は知らないので、（ポインタいじれば2つ返せるらしいけどよくわからないし良いや）このコードが適切かはしりません。
まぁ、難しい実装をしたから公開するぜ！！っていうよりかはなんとなくやろうと思ったからやっただけです。
おまけは終わり。
健康管理
野菜を食べています！！
何した
警察に追われる妄想をした。
具体的に
大学から自転車ででて、左見たら警察がいたので追われる妄想をしながら帰宅した。 昔、パジャマ(+帽子+マスク)で買い物に行ったら帰ってくる途中警察に声掛けられてムカついたのでまだそれ根に持ってます。（盗難自転車だと勘違いされた)。
思い出したら腹たってきたわ。しかもその警察「大学生とは思えない」とか言ってきやがってマジで腹たった カス。 俺はふざけた格好してふざけたことするのが好きなんだよ調子のるなアホ
今日解いた問題
先に言っとくけど解説記事じゃないです。
ABC137 D- Summer Vacation
[優先度付きキュー,(貪欲法)]
こういう問題好きです。（解けなかったけど)
こういうの解きたい解きたい。って何回も言ってる。似てると思える問題に、解ける問題をたくさん解こう。みたいなのもあったよね。
解説を見て、あぁ、M-1日目から順に考えていくのか…ってなったよね。
以下解説PDFより引用
こういった問題は、制約の厳しい方から見ていくと見通しが良くなることが多いです。 したい操作は - 候補の追加 - 候補の中から最大のものを取り出す
にゃあ. 0日目に受けれる仕事は多い。M-1日目に受けれる仕事は少ない（日数の制約上受けれる（というか受けれるっちゃどれも受けれるが、報酬が間に合わない))ので制約がきびしい
候補の追加はN回ぐらい。(僕の実装だと)
候補の中から最大のものを取り出す操作は最大M回。
優先度月queueの操作の計算量はここに書いてあるね。
ちなみに優先度月queueは二分ヒープ（二分木？）とかで構成されてるのを考えて、一回の要素の追加は(log N)だな. ってことで計算量は、 M-1日目から0日目の仕事を決めていくM回のループと、最大N個のqueueへの要素の追加とM個の要素の取り出しで 計算量はM + Nlog(N) + M んで O(M + N log(N))か。
AGC024 C- Sequence Growing Easy
[操作,数列]
(もはやタグ付がテキトウ)
こういう問題テキトウに解いて終わりがち…証明出来ない。。。(ACはしたけど…)
そもそも競プロってACが正義だから証明しなくても良いのかな？(ってか、人類segment Tree空で書けないけど使ったりしてるし、解答への理解が中途半端でも別にええやろ。)
なに書けばいいか分かんないからどんな考えしてたか書きます。
まず、A[0] = 1;は作れるか？ → 作れない。 1個前の要素が存在しないのでA[0] = 1は作れない。 A[0] = 0 しか無理。
A[1] = 2は作れるか？
A[0] = 1 が作れないので作れない。
...
A[i] = k が作れるとき、 A[i+1] = k が作れるか？
→ 作れる。
A[i] = k だから、k個前の数字は0、つまりA[i-k] = 0.
A[i-k+1] = 1, A[i-k+2] = 2, ... , A[i-k+k] = k; こうやってAi-k+kは作られた。
A[i+1] = kを作るには、 A[i-k+1] がまだ0の段階で,A[i-k+2] = 1, A[i-k+3] = 2, ... , A[i-k+k+1] = k; って作ってあげる。
だから、A[i] = k , A[i+1] = k を作るには、 まずA[i+1] = k を k回の操作を行うことで作ったうえで、A[i] = k をｋ回の操作を行うことで作る。
A[i] = k, A[i+1] = L(Lはk未満)の数字は作れるか？
A[i-L] = 0の段階でA[i+1] をL にした後でA[i] = k にすればいいので行けそう。
A[i] = k が作れるとき、A[i] = k, A[i+1] = k + 2; は作れるか？
→作れない
まず、A[i] = kを作った後にA[i+1] = k + 2 にするのは言うまでもなく無理。
A[i+1] = k + 2を作ったあとに A[i] = k を作ろうとすると、 A[i+1-(k+2)] = 0, A[i+1-(k+1)] = 1, A[i+1-(k)] = 2; となっている。
A[i] = k を作るためには A[i-k] = 0じゃなきゃ行けないんだけど、 上の2個めのやつ A[i+1-(k+1)] = A[i-k] が1になってる。
こいつを0に戻すことは不可能だよね…
あああああああああﾑﾘﾑﾘﾑﾘﾑﾘｶﾀﾂﾑﾘ
みたいなことを考えてました。 - まず、与えられたAが生成可能か判定 - 生成可能なら、出力する値はA = {0,1,2,2,0,1,2,3,3,4,5,5}の、なんかまぁ、単調増加の一塊と単調増加が終わった後の右の数字のやつを足す。みたいなノリでやりました。
ちなみに単調増加の一塊っていうのは {0,1,2} , (4番目の要素から){0,1,2,3,}, (8番目の要素から){3,4,5}っていうノリでお話してます。
まぁ、証明は出来なくてもこんなこと考えてたんだなあ。ぐらいのノリで一生読み返さないと思うけどメモりました。
あとがき
Vim使うの下手です。
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
