AtCoder 復習 1
参考：【解説 実況】ABC240 AからD【かつっぱ】 - YouTube
A,B は簡単すぎるので飛ばします。
ジャンプ問題。真偽値を持つ DP で解ける。
スタックを用いる。整数の個数を扱う際に [整数, 個数] と配列で管理する方法が賢すぎた。
pop() とかも忘れないようにしたい。(deque とかも似た操作だよね)
先頭に a を入れたり入れなかったりして文字列 S が回文なれば Yes
コーナーケース (only a) も考慮する必要があって実装がちょっと面倒。
おしりから考えるタイプの問題。文字追加を沢山行うため、リストを用いるよりかは deque を使うのがよい。
BFS練習
DP練習。部分和？というらしい。ガバガバコードでも通った。
B 問題だがやや難しい。
N 個みかんを選んだときに条件を満たすかどうかを全探索で調べていく。
while 文を使うと全探索がらくにできる。
解法はすぐ浮かぶが、実装を丁寧に行う必要がある。かも。
リストのおべんきょうが深まってるとらく。isupper とか islower を初めて知った。
def で無双しよう！
D問題は二分探索っぽいですが、実装が大変そうなので解きませんでした。水色diffだし無理して解く必要はないかなーと。
bit全探索！Cのbit全探索にしては実装がやや大変？
数学問題の中の整数問題。抽象的な等差数列を具体的に考えていく必要がある！
整数問題は (整数)×(整数)=整数 の形に持ち込めると強い。
数学力が要求される。包除原理を知ってるかどうか。
あと pow の使い方を知ってるかどうか。
DP問題。小さい順に実験していくと、過去の結果を利用できる。というわけでDPを実行。
包除原理
恐らく貪欲法
単品
itertools 練習
クエリによる文字列操作の典型問題に慣れよう。
数学問題？なのかよくわからん
2重ループで解けるが、どう実装するか問題
余事象を考えるタイプ
消すのは 0,1,2 個のいずれかになる。if 文のゴリ押しで解ける。が、きれいじゃない。
数学問題。N 個の点から 3 点選び、それが同一直線状に存在するかどうかを調べよ、というもの。
C - Sum of product of pairs ACコード(新) ACコード(旧)
数学問題？ΣΣAiAj を求める問題。ACコードが 2 つあるが、やっていることは同じ。
因みに解説は社長が行ったみたいです。
for 文と配列の超基本問題。B問題でもいい。
数学問題。座標 0 に到達できるかどうかを考えてから方針を分岐する。
越えられないならその座標を、越えられるのなら偶奇で分けて出力する。
bit全探索。だがちょっと難しい。二次元配列で考えるbit全探索なので、今まで一次元しか扱っていない人だと少し躓くかも。
基本的には考えられる全探索を行い、その各々のループについて全てのマスを全探索で調べればよい。
したがって、一次元は
for文(bit全探索開始！) → for文(条件を満たすか全探索開始！)
の二重だったが、本問は二次元配列なので
for文(行についてbit全探索開始！) → for文(列についてbit全探索開始！) → for文(行について条件を満たすか全探索開始！) → for文(列について条件を満たすか全探索開始！)
という四重ループを実装する必要がある。
実装力が要求される、気がする。小数点以下をどう処理するかが難しい。そこで replace() を使うという変態的発想で解ける。
bit全探索の超基本！やったことない人は本問を使うとよい。
D - I hate Factorization ACコード
A⁵－B⁵=X を満たす A,B∈ℤ をひとつでも求めればよい！
数学問題に見せかけて全探索で解ける、実装力要求タイプである。
クエリによる文字列操作に慣れよう！文字を追加する操作があるので、配列よりも deque を用いる方がよい。
数学問題？サイコロの期待値を求め、累積和を求める問題。慣れておきたい。
分裂した敵にも同じ行動を繰り返すので 2 倍して +1 する必要がある！
難易度は低いが、考察力が要求される。
最小公倍数 LCM を求める問題。
長さが与えられて三角形ができる個数を求める問題。
bisect を使うとよい。
D - Powerful Discount Tickets ACコード
heapq を使う。
BFS練習
bit全探索。やや難しいかも。
今まで解いた問題を列挙しただけで満足してしまった。定期的に復習しつつ、DPの理解度を深めつつ、様々なアルゴリズムを習得したい。
ACコードの殆どがきたなかったり、余計な部分を迂回していたり、簡略化できる部分もあると思いますが、温かい目で見守ってください（）
