星4以下埋めが終わった
典型90問の星4以下の問題を全て解いた。いやー星4以下だけでもかなりボリュームあったなーって思う。特に043と079は難しかった(どっちも解説AC)
ただ全部写経はせずにACとれたからきっと成長してるはず、夏までに入水したい。
明日からは星5以上の問題を解いていく、おやすみー
典型90問 061~070
061 - Deck(★2)
dequeを使うのかと思ったけど中央部分へのアクセスが重かったことを思い出したのでappendをうまく使う方法で実装した。
たしかinsertは遅いんだよなっておもったから上側と下側の配列を別々につくってappendで挿入の操作を書いた。 AC
063 - Monochromatic Subgrid(★4)
Hの制約が小さいことに着目してbit全探索。 途中で配列のコピーをとるときに参照渡しをしていたせいで何回かバグらせた。
deepcopyを使うことで解消した。
064 - Uplift(★3)
階差の数列を作ることで土地が隆起(沈降)した場合にそこでの高さをすべて変更する必要がなくなる。アイデア自体は簡単だが添え字がちょっとややこしい。
Submission #31942523 - 競プロ典型 90 問
10進法からn進法に変換する関数をネットから取ってきたらWAになってしまった。
また気を取り直して正しそうな関数をもう一度とってきたら次はコーナーケースのN=0の場合に引っかかってしまった。
このあたりは自分でライブラリを作っておいた方がいいかもしれない。
典型90問 051~060
052 - Dice Product(★3)
分配法則の式変形を考えるともとめるのは
055 - Select 5(★2)
愚直に実装しても間に合う。
058 - Original Calculator(★4)
で割ったあまりを考えることと、の制約がかなり大きいことを加味すると周期性を考えればよいことがわかる。
典型90問 041~050
042 - Multiple of 9(★4)
Kが9の倍数であることとKの各桁の和が9の倍数であることは同値。
さらにDPテーブルを次のように定め、遷移は各桁の最高位の数に着目して考える。
043 - Maze Challenge with Lack of Sleep(★4)
01BFSというやつらしい。かなり苦戦した。 下の記事がめちゃめちゃわかりやすかった。
またそのまま書いてもギリギリTLEするので入力の受け取りを工夫する必要があった。 AC
044 - Shift and Swapping(★3)
右方向へ配列をシフトする操作を愚直に書くと計算量が膨大になるので、それをメモするところがポイント。
046 - I Love 46(★3)
46で割ったあまりでそれぞれの数字が何回登場したかを記録しておけば全探索できる。
048 - I will not drop out(★3)
問題文を言い換えると1分で,点の問題が解けるということなのでこれらをまとめた配列を降順にソートして上からK個分の合計得点を出力すればよい。
050 - Stair Jump(★3)
見るからにDP