一問一答十三週目
概要
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
六十三日目
自力AC。という条件から、
までAを全探索し、
の最小値を求める。
六十四日目
自力AC。与えられるのいずれかを基準として、使用できるアルファベットを絞り込んでいくイメージ。候補となるアルファベットが、各
にどれだけ含まれてるか調べ、最小個数がそのアルファベットの個数となる。
六十五日目
写経AC。操作後の配列の符号が、「」となる場合と「
」となる場合があり、そのうち手数が少ない方を答える問題。符号を変更する必要があるときだけ操作すればよい。累積和が0になる場合を漏れなく条件に入れること。
六十六日目
自力AC。シャワーボタンを押す間隔が、シャワーが出続ける時間
より長ければ
を足す。短ければ
を足す。if文でもいいけど、min関数使った方がすっきり書ける。
六十七日目
解説読みAC。"K個目の小さい数"を、"K番目の数"と勝手に解釈していた。
を
で昇順ソートした配列を作り、
となるときの
が答え。
このほかに、バケツソートというアルゴリズムを使用する解法もある。大きい一次元配列を準備して、番目に
を足していく。その配列に対して、
となるときの
が答え。
六十八日目
解説読みAC。「二の字」に分割線を引くか、「T字」に分割線を引くかで場合分けする。最初の区切り線でループを回し、残った部分はなるべく面積が等しくなるように分割すればよい。
一回上記探索を行ったら、チョコを90度回転させて再度ループを回す（ループ対象の辺を縦横変更する）。一回目と二回目で求めた差分のうち、より小さい方が答え。
六十九日目
自力AC。合計成績が10で割り切れるか否かで場合分けすれば素直に解ける問題。
ただ、この問題はメモ化再帰に因るDPで部分和をすべて列挙できる。DP解法については、写経ACだったが、考え方はなんとなく理解できた。
分割した小さな問題は、「ある時点で、与えられる要素を足す場合と足さない場合のポイントを求める」で、それをメモ化再帰してベースケースに辿り着くようにすればよい。
むすび
扁桃炎に罹って苦しみました。健康第一。また、体調崩して以降、一意専心の気持ちがやや弱くなってきているので、目の前の問題に集中するよう心掛けたいです。
一問一答十二週目
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
五十九日目
6→5→… となるように目が出るケースを考えればよい。
六十日目
典型的なグラフ探索問題という印象。DFS か BFS をきちんと勉強する必要があります。
六十一日目
条件分岐の洗い出しがキモ。
「一個の S と二個の C で SCC を作る」場合と「C 四個でSCCを作る」場合が考えられる。
前者は(Sの個数 x2) ≦ (Cの個数) の場合で、(Sの個数) + (余ったCを4で割った商)が答えとなる。後者は (Sの個数 x2) > (Cの個数) の場合で、(Cの個数を2で割った商)が答えとなる。
六十二日目
公式の解説通り、移動距離の総和が初めてXを超えるような時刻 t を愚直に求めればよい。
むすび
スピードはまだまだだけど、きちんと考えれば割と太刀打ちできるようになってきた気がする。
一問一答十週目
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
五十一日目：C - AtCoDeerくんと選挙速報 / AtCoDeer and Election Report
比の計算。割り算したときの誤差ってよくわからん。
五十二日目：C - Coloring Colorfully
目標は、「0101...」or「1010...」なので、そうなるための最小手数を地道に計算すればよい。
五十三日目：C - 一次元リバーシ / 1D Reversi
操作をするたびに、BW か WB がひとつずつ減っていくので、もとの文字列からそれらの数を数え上げればよい。
五十四日目：C - Boxes and Candies
貪欲法でいけるらしいけど、復習できておらず。
むすび
根詰めすぎるのは、何事もよくないかもしれない。
一問一答九週目
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
四十七日目： C - こだわり者いろはちゃん / Iroha's Obsession
愚直に調べる問題。嫌いな数字が入っていたら、おおもとの N を1増やして試す、を繰り返せばよい。
四十八日目：C - いっしょ / Be Together
与えられた数の平均値を四捨五入したものを目標値として、各値との差の二乗和を計算すればよい。decimal モジュールで、正確な四捨五入が可能。
また、全探索でも間に合う。
四十九日目：C - 高橋君とカード / Tak and Cards
見事に部分点。DP を使いこなせれば満点取れるみたいだけど、DP の概念をつかみあぐねている。満点の解答はまだ復習できておらず。。
五十日目：C - たくさんの数式 / Many Formulas
S の長さが小さいので、全探索すればよいことはわかったが手が動かなかった…DFS を使って解きたかったけど、再帰の動作がまだイメージできておらず、実装できないのよね。。
i 番目の数に対して、「i+1 番目の数を連結させる」のか、「i+1 番目を足し算する」のかの選択しに分かれるのがポイントよね、きっと。
むすび
もやもやしているのだが、これを超えたら違う世界が見えてきそうな気がするもやもや。がんばろう。
一問一答八週目
AtCoder Virtual Contest で、一日一問 ABC-C 問題を解いてます。一週間ごとにさらっと内容をおさらいします。
四十一日目：C - 座圧
の各要素が、何番目に大きい数字なのか変換すれば
になる。set 型を取り、ソートして、辞書型を活用すればよい。
四十二日目：C - 総和
いもす法で解けた。部分列の和を求めるので、の各要素が何回出てくるかわかれば、「各要素 × 登場回数の和」として求められる。
正攻法は解説にも載っている通り、1からi番目までの和をすべて記録し、それらの差を取ることで部分和を計算する。
四十三日目：C - 単調増加
尺取法であることはわかった。右側を伸ばしていき、左側を追従させていく。けど、変数の名前がよろしくない気がするなぁ。。
四十四日目：C - ピアニスト高橋君
全列挙でパワープレイ。
四十五日目：C - 柱柱柱柱柱
動的計画法。解きやすいパターン。二個前か一個前のコストが小さい方からi番目に移動すればよい。漸化式解くパターン。
四十六日目：C - 背の順
身長と出席番号の二次元配列を取り扱う問題。身長でソートして、その順に出席番号を出力する。operater.itemgetter を利用すると、ソートするkeyを指定し易くなることを学んだ。
むすび
ABC-123 敗北。緑になる日はいつのことやら。
Python学習メモ：lru_cache によるメモ化再帰
概要
ツイッターで python の lru_cache が超便利だと見かけたので試してみた。感動したので記事にした。
使い方
LRU キャッシュを適用したい関数の前に、@functools.lru_cache() と書くだけ。引数については公式ドキュメントやググったらすぐ出てくるので割愛。
LRU（Least Recently Used）はキャッシュの管理方法です。こちらもググったら出てきます。
import functools
@functools.lru_cache(maxsize=None)
def fib(n):
"""
"""
if n < 2:
return n
return fib(n-1) + fib(n-2)
@functools.lru_cache(maxsize=None)
def fact(n):
"""
lru_cache を使ったメモ化再帰による階乗計算
"""
if n == 0:
return 1
return n * fact(n-1)
print([fib(n) for n in range(100)])
print("=====================================================================")
print(fact(15))
結果
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170, 1836311903, 2971215073, 4807526976, 7778742049, 12586269025, 20365011074, 32951280099, 53316291173, 86267571272, 139583862445, 225851433717, 365435296162, 591286729879, 956722026041, 1548008755920, 2504730781961, 4052739537881, 6557470319842, 10610209857723, 17167680177565, 27777890035288, 44945570212853, 72723460248141, 117669030460994, 190392490709135, 308061521170129, 498454011879264, 806515533049393, 1304969544928657, 2111485077978050, 3416454622906707, 5527939700884757, 8944394323791464, 14472334024676221, 23416728348467685, 37889062373143906, 61305790721611591, 99194853094755497, 160500643816367088, 259695496911122585, 420196140727489673, 679891637638612258, 1100087778366101931, 1779979416004714189, 2880067194370816120, 4660046610375530309, 7540113804746346429, 12200160415121876738, 19740274219868223167, 31940434634990099905, 51680708854858323072, 83621143489848422977, 135301852344706746049, 218922995834555169026]
=================================================================
1307674368000
コピペしただけなので超見づらいけど、PC が固まることなく計算できた。
注意事項
公式ドキュメントに、「結果のキャッシュには辞書が使われるので、関数の位置引数およびキーワード引数はハッシュ可能でなくてはなりません。」とあった。よくわからんけど、関数の引数にリストとかは使えないらしい。
URL
LRU（Least Recently Used）とは - IT用語辞典 e-Words
functools --- 高階関数と呼び出し可能オブジェクトの操作 — Python 3.7.3 ドキュメント
python3.2以降のlru_cacheが素敵すぎて。 - BlankTar
