典型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