書籍読んでて途中の計算に詰まったので個人的にメモ
今回読んでる書籍はオイラーのゼータ関数論という本.
続きを読む『ケーキの切れない非行少年たち』という本がありますね.
円形のケーキが三等分できない非行少年についてのお話です.
通常ケーキの三等分について想像しやすい切り方は以下の通りですね
でも三等分について無理に扇形にする必要ないようにも確かに思います.
例えば以下のような切り方で三等分する方法について考えてみましょう.
どうせすぐ3桁に落ちると思いますが,一旦4桁達成しました.
Pythonでやっていますし,Python前提の話も書くと思います.
ちなみに1001 = 7 * 11 * 13です.これ素因数分解でもたまに出るので注意が必要です(何の話だ
なんだか「茶色になりました」とか「緑になりました」とかいったブログの記事はちょくちょく見かけるので自分も書いてみようかなと思いました.
今後の当面の目標はEとFを安定して解けるようになるといったところですかね.Eはたまに解けて,更にFはもう少し時間があれば解けたというのが1~2問あったかなくらいなので,とりあえずEとFです.たまに大事故でDでつまづくことがありますがそんなの知りません.アーアーキコエナイー
なんというか他の「入緑しました」みたいな記事にあるような勉強らしい勉強はしておらず,その回の解説で必要だったメソッド等は一旦組んでみたり検索して探してみたりするくらいのコトを繰り返しただけです.しかし自分はそんなに頭はよくないし飲み込みもそんな得意ではないので,今回躓いた問題に限定してという感じでした.あとそんなにAtCoderだけに私生活の時間をとられたくないですし
今のところ結構重宝しているのが,Dijkstra法とUnionFindです.とりあえず困ったらそこらへん使っとけみたいな感じでしたが,使える問題は結構あったのでこの2つはおさえておいて間違いはないと思います.
抑えられるメソッド等はちゃんと抑えておいた方が間違いないです.使える武器は多いに越したことはないです.ちゃんと使えないとただの思考の妨げになると思うので注意は必要な部類だとは思いますが…
動的計画法は他の記事ではできるようになったほうが良いという話は多いですし尤もだと思いますが,動的計画法は落とし込み方や実装力のほうが大切で,UnionFindみたいな「これを利用してやればうまくいきそう」みたいな部類のモノではないんじゃねとかいう,自分の中ではそういう認識で,結構身につけるのは大変って認識ですし,自分では今でもそんなにできません.
一応DPコンテストの問題もちょくちょく解いてはみていますが,やっぱ難しいですねこれ.
atcoder.jp
話は変わりますが個人的には連想配列,Pythonの型だとdict型が結構好きで,困ったらとりあえずdictでぶん殴るという感じで生きています.
例えばDPだと
入力分の配列を用意できない→じゃぁdict型を使えばその分いらない領域減らせるよね
とか
例えばUnionFindだと
入力数分のノードが必要だけど入力が任意の数値だった→何個目の入力かという『何個目』をキーとして,実際の入力を値にすればいいじゃん
(『1』つ目の入力→1000,『2』つ目の入力→1500)
みたいな感じでdictは重宝しています.
後者は座標圧縮って呼ばれているらしいです.この前友人と通話していて知りました.
存在確認等もdictで一旦実装することは多いですが,後々考えるとset型のほうが良いよねってなることが多いです.
みたいな感じでこれまで気ままにやってきましたし,おそらくこれからも気ままにやっていくと思います.