問題 1〜Nまで書かれたカードがシャッフルされた状態で積んである。 1回の操作で、各カードを1枚抜いて任意の場所に挿入することができる。 カードを上から昇順にするために必要な操作回数を答える。N 考え方 探索を考えると、各数字を上に持ってくるか下に…

問題 leading zeroを許さないn桁の整数x(>0)を考える。 以下の条件を満たすxは何個存在するか？ 「y mod k = 0となるy(>0)が、整数xのsuffixになっている」 答えをmod mで答える。n k m 考え方 条件を満たすxを考えるため、suffix候補のb桁のyを考えてみる。…

問題 整数A,Bについて、A〜Bの整数で、4または9を含む整数はいくつあるか？A,B 考え方 例えば123という数字以下の4,9を含む整数の数を求めたいと考える。 一桁目が0の時は00〜99まででカウントした場合の数になる。 一桁目が1の時は、00〜23まででカウントし…

問題 1〜Nの番号が付けられた建物を直線状に順番に並べて建てたい。 ただし、以下の条件が与えられる。 ・1の建物の高さは0 ・隣り合う建物の高さの差は高々1となるようにしたい。 ・x[i]の建物の高さがt[i]以下 このとき、建物の高さの最大値を求める。 N x…

適当に思いついた問題。 問題 営業日がN日ある。 R人のお客さんが営業日のうちどれかを1/Nの確率で選ぶ。 お客さんが1人以上いる場合は出社しなければならないが、いない場合は休みとなる。 出社しなければならない日数の期待値を求める。N R 考え方 P[i][j]…

問題 C(n,r)を二項係数とし、 C(N, m) + C(N, 2m) + C(N, 3m) + ... + C(N, Nを超えないmの倍数) mod p を高速に求めたい。N=おっきい m=ちいさい p=10^9+7 考え方 C(n,r)= n*(n-1)*...*(n-r+1) / (1*2*...*r) となることを利用して、分母と分子をそれぞれr…

問題 N人の社員がおり、1〜Nの番号が付けられている。1はCTOになっている。 i番の社員の上司がj番の社員であるという情報が与えられる。社員1人につき、上司は1人のみ。 今、すべての社員が上司にN種類の贈り物から1つ選んでプレゼントすることを考える。 各…

問題 試合結果「A-B」が与えられ、Aは自分の点数、Bは相手の点数になっている。 今、2つの試合運びを考える。 「stress-free」な試合運びとは、最初に1-0になって、そのあとは、A-Bになるまで常に相手に点数が勝ち続けた状態で試合が進むことをいう。 「stre…

問題 distinctなN個の文字列が順番に与えられる。 自動補完機能のために、与えらえた文字列毎に1文字以上のprefixを登録しておかなければならないが、以下の条件を満たす必要がある。 i番目に与えられた文字列の登録するprefixは、 ・その文字列全体 または …

問題 整数Xを素因数分解したときの素因数の種類数をw(X)とする。 整数A〜Bのなかで、w(X)=Kとなる整数の数がいくつかるか？2 1 考え方 2が素因数として含まれる＝2の倍数 3が素因数として含まれる＝3の倍数 5が素因数として含まれる＝5の倍数 ・・・ である…

問題 1からNの番号が書かれたN枚のカードが下から昇順になるように重ねてある。 「上からp枚目からc枚を取り出してカードの山に持ってくる」というシャッフルをR回繰り返す。 シャッフル後に一番上に来ているカードの番号を返す。 考え方 必要なのは最後に一…

問題 2次元グリッドの原点にいて、グリッドに沿って動ける。 毎秒、その場にとどまるか、上下左右に1単位だけ動けるが、いくつかの格子点が通行禁止になっている。 k秒間で、x座標が最大となる点でのx座標の値を求める。通行禁止の格子点数 -10^3 1 考え方 …

問題 n個の整数numbersが与えられる。 各数字を1回につき、1ずつ増やしたり減らしたりできる。 少なくともk個の連続した整数がある状態を作るための最小回数を求める。 -10^7 n k 考え方 与えられた数字から、ある整数集合z,z+1,z+2,...を作ることを考える。…

問題 N個の遺跡isekiがあり、iseki[i]にはl[i]〜r[i]までの(宝石番号の連続した)宝石がある。 遺跡に訪れると、上記の宝石をすべて入手し、報酬としてs[i]だけ得られる。 しかし、宝石はM種類あり、すべてそろえてしまうと、魔王が復活してしまう。 魔王が復…

問題 兵士が(x1[i],y1[i])にいる。 塔が(xt[i],yt[i])に配置されており、塔を起動すると、その塔を中心にすべての兵士が点対称に移動する。塔は何度でもどの順番でも起動することができる。 すべての兵士を(x2[i],y2[i])に配置することができるか？ -10^6 塔…

問題 (0,0)から(x,y)へ移動したい。 ただし、i回目の移動距離はlen[i]でなければならない。 (i回目の移動で整数の座標に移動する必要はない。) ちょうどn回分の移動距離が与えられるとき、n回ちょうどで(x,y)にたどり着くことができるか？ 考え方 移動する座…

問題 ホテルにN人泊りに来る。 i番目の人は、arr[i]日に到着し、dep[i]日に出発する。 ある人にプロモーション活動をすると、その人のレビューはGOOD判定になる。 さらに、プロモーション活動した人が滞在中にホテルに滞在した人(到着日、出発日を含む)もGOO…

0pt Rate: 1243->12631年半ぶりの参加らしい。が、0完でつらい。 250. JanuszTheBusinessman 解けなかった。 出会える人のグラフを作って、そのグラフの中で頂点集合を選んで、その頂点と隣接頂点がグラフすべての頂点をカバーしているような最小の頂点集合…