2020年 6月 29,30日
まえがき
前もこの動画貼ったかも。被ってたらごめん。
ブログ書いてから寝るぞ。・・・・(7/1 07:09)
何した
大学の課題(つかれた)
最近折り鶴を折りまくってます。折って折って折りまくってる。
具体的に
今日解いた問題
ABC161 F- Division or Subtraction
- [約数列挙,約数の個数,割った余り]
Nの約数について成り立つモノの数+（N-1)の約数の個数が答えだった
以下テキトウに文章書くけど、全て無意味。
N-1の約数で1以外のものは,Nの約数じゃなさそう。
だから、KをN-1の約数とすると、
N -> N - K -> N-K-K -> ... -> 1 となります。(操作をα回すると、N - αKとなり、αK = (N - 1))
また、KがNの約数でないとき、N-K, N-2K , N-3K...,がKの倍数にならないことは簡単な数式で示せる。
テキトウなxを用いて、
N-αK = xK (αは操作回数)であるとする。
するとN= (α+x)K となり、Nが元々Kの倍数ってことになっちゃあう。矛盾。って感じで良いと思う。
でまぁ、K = (N-1の約数)の時は、最終的にNが1になる。
次、その他にはどんな物があるか。
とりあえず、√N 以上のものについてかんがえてみると,(N以外では)√Nより大きいものについては、操作が N - K しか行われないことが分かる（√Nより大きくて、Nの約数であるものはN以外に無いため)
ABC060 D- Simple Knapsack
- [ナップザックDP,特殊な制約,解説AC]
今回の制約は,荷物の重さが4種類しかない。というところでした。
僕は,DPのテーブルをdp[w0]から始めれば大きくならないんじゃないか？とかかんがえて詰みました。
重さの種類が4つしかないことから、重さ1,2,3,4として、重さ1がx個、重さ2がy個、...を全探索してあげて、重さ1のx個は価値が高い方からx個、重さ2のy個は価値が高い方からy個。としてやれば良い。
最大で254 (= 58 < 108)なので間に合いマス。(ちなみに、重さ1からx個取った時の価値なんかは累積を取ってやると楽そう)
ABC139 E= League
- [vectorの削除,トポロジカルソート,計算量,グラフ,閉路を持たないグラフ]
世界で一番難しい問題です。
グラフ的に解くほうは理解できません。
いや、グラフを使わない方も理解できません。
(あれ？）
ABC082 D- FT Robot
- [DP,操作]
上下に動く、というのと左右に動く、は目標(x,y)を目指すにあたって互いに干渉しない。
a0,a1,a2,...,an みたいなのを足したり引いたりしてxを目指そう。みたいな感じの問題に変えることが出来る。
dp[i][j]:= i回移動したとき座標jにいることが出来るか。みたいな感じでやると良い。
あとがき
以下は毎回記事に貼っているテンプレート
基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)
