典型90問
061 - Deck(★2) dequeを使うのかと思ったけど中央部分へのアクセスが重かったことを思い出したのでappendをうまく使う方法で実装した。 たしかinsertは遅いんだよなっておもったから上側と下側の配列を別々につくってappendで挿入の操作を書いた。 AC 063 …
052 - Dice Product(★3) 分配法則の式変形を考えるともとめるのは AC 055 - Select 5(★2) 愚直に実装しても間に合う。 AC 058 - Original Calculator(★4) で割ったあまりを考えることと、の制約がかなり大きいことを加味すると周期性を考えればよいこ…
042 - Multiple of 9(★4) Kが9の倍数であることとKの各桁の和が9の倍数であることは同値。 さらにDPテーブルを次のように定め、遷移は各桁の最高位の数に着目して考える。 AC 043 - Maze Challenge with Lack of Sleep(★4) 01BFSというやつらしい。かな…
032 - AtCoder Ekiden(★3) 制約が小さいので順列を全探索してもよいことがわかる。 AC 033 - Not Too Bright(★2) コーナーケースに注意する。 HかWのうち一方が1のときはが答えとなる。 AC 034 - There are few types of elements(★4) 連続する部分列…
022 - Cubic Cake(★2) できる立方体のうち最も大きいモノを考えるとその一辺は である。 実際そうなるように分割したときの操作の回数が今回求めたい最小回数である。 各面に対して何回操作を行うかと考えることでその回数は と求まる。 AC 024 - Select +…
012 - Red Painting(★4) マスを赤く塗るクエリと赤で塗ったマスが繋がっているかを判定するクエリを処理する問題。 連結判定なのでUnionFindを使う。 その際マスを数字に対応づける必要があるが、それは とすればよい。(これは左上から順にマスをひとつず…
簡単な解法を自分用にメモしておこうと思います。 001 - Yokan Party(★4) 答えに単調性があるので二分探索を考えます。 答えを決め打ちしての二分探索です。具体的には答えはM以上か?ということを考えます。 仮にK回以上分割してスコアSが得られたとしま…