問題 N車両の電車をM人で点検する。最初、i番目の人はXi車両目にいる。 点検には時間がかからないが、隣の車両への移動には1分かかる。 すべての車両を少なくとも1人が点検した状態にするのにかかる時間は最低何分か？ 1 1 考え方 Nが大きいので、車両の状態…

問題 1からNまでの数字をすべて書き出したとき、「1」は何回書いたか？ 1 考え方 愚直に数えると、O(N*桁数)かかってしまって間に合わない。 以下、1からではなく、0から考えても問題ない。 桁DP 最大桁から考える。 ここで、Nが3桁「xyz」であると仮定する…

問題 N種の料理からM種を順番に選んで食べる。 このとき、各料理自体の満足度の他に、料理iの直後に料理jを食べた場合の追加満足度もある。 満足度の最大値を求める。 1 0 0 考え方 N種からM種選んで、その順番を列挙する方法だと、O(2^18 * 18!)で間に合わ…

問題 n個の整数a_iが与えられる。 高々k回、整数xを整数a_iから一つ選んでかける、という操作を行える。 各整数のORをとったものa_1 | a_2 | ・・・| a_nの最大値はいくつになるか？ 1 1 2 0 考え方 直感的に、xが2以上なので、x^kをかけた方が最大bitを更新…

問題 (0,0)->(x,x)->(2x,0)->(3x,x)->・・・のようなぎざぎざした線を考える。 今、整数点(a,b)をこの直線が通る事がわかっている。 可能なxの中で最小のものを返す。なければ-1を返す。1 考え方 まず、y軸の方は0からxまでしか変化し得ないので、b以上でな…

div2Bのレベルなの・・・？ 問題 n個の要素からなる数列aと整数mが与えられる。 空でない部分列の和がmで割り切れるような部分列があるかチェックし、あるならYES、ないならNOを返す。1 2 0 考え方 各a_iはmod mを取っておいても問題ない。なので、問題は「0…