問題 女子N人、男子M人いて、ここから女子P人、男子Q人だけ選ばれてチョコを渡すことが許される。 前もって、ある女子からある男子へプレゼンを渡したときの幸福度の情報が与えられる。 選ばれた男女の幸福度の合計値の最大値を答える。N,M P 考え方 女子に…
問題 無限に長い一直線上に箱が並んでおり、-100のところに赤玉がR個、0のところに緑玉がG個、100のところに青玉がB個ある。 1回の操作で、一つの玉を左右どちらかに移すことができるが、同じ箱に違う色の玉をいれる状態を作ってはいけない。 すべての箱に玉…
問題 N*Nの正方形のタコ焼き器が与えられ、各マスごとにおいしさが決められている。 店員がQ人いて、P[i]マス以下の長方形のマスを使って焼くことができる。 店員ごとに焼きあがるタコ焼きのおいしさの合計値の最大値を答える。N Q,P 考え方 任意の長方形の…
問題 整数N,Kが与えられる。 次の条件を満たす文字列が作れる場合、そのような文字列の一つを返す。なければ空文字を返す。 ・文字長はN ・各文字はAまたはBのどちらか ・i 考え方 memo[i][j][k]:=文字長iで、Bをj個含み、(i,j)のペア数がk個になっている文…
問題 N人いて、a番の人よりb番の人の方が順位が高い、という情報がM個与えられる。 1番の人の考えられる最高順位は？ 考え方 ハッシュに1を入れておいて、aの情報にハッシュに入っている番号が該当すれば、bをハッシュに追加。 これで、ハッシュは1よりも順…
問題 N人とK席があり、各人は順番に以下のルールによって席に座る。 ・i番目の人はp[i]の確率で「空いていれば座る」、(1-p[i])の確率で「両隣に人がいなければ座る」 ・どちらも満たせない場合は、座らない 空いている席数の期待値を求める。 考え方 空いて…
問題 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 解けなかった。 出会える人のグラフを作って、そのグラフの中で頂点集合を選んで、その頂点と隣接頂点がグラフすべての頂点をカバーしているような最小の頂点集合…
問題 高さの違うN個の積み木が並べてある。 隣り合う2つを交換する操作を何回か繰り返して、h_1 h_i+1 > ... > h_Nとなるようにしたい。 そのようにする最小交換回数を返す。N 積み木の高さ 考え方 高さの小さい積み木から左右のどちらかにその積み木より高…
問題 各頂点が整数点の多角形と線分Lが与えられる。 多角形を線分が分断し複数の多角形に分割するとき、分割後の多角形の数を返す。 線分は多角形をちゃんと分割するように与えられる。 考え方 よく考えると(←)、「線分によって分割される切断面の数＋1」が…
問題 n頂点の有向グラフが与えられ、各頂点にはアルファベット1文字が書かれている。 任意頂点から進んで、アルファベットを順番に回収して長さkの文字列を作る。 頂点にたどり着いたとき、アルファベットを回収してもしなくてもよい。 このとき、可能な辞書…
ISUCON4に初参加した。 予選通過ならずっぽいけど、いろいろ勉強になったので、記録しておく(だらだら書き)。 チーム aomoriringoさん、matsu4512さん、自分。 おおよその役割分担は、 aomoriringo : アプリ周り中心 matsu4512 : DB周り中心 自分 : その他 …
問題 無向木が与えられる。 クエリとして、頂点a,bが与えられるとき、aとbに辺を追加したら閉路ができる。このとき、閉路を形成する辺の数を返す。V Q 考え方 Qが10^5まであるので、O(n)な解法だと間に合わない。 頂点aから頂点bまでの距離がわかっていれば…
問題 木が与えられる。 木の辺を以下のルールで削除していく。 ・最初にどこかのノードを決める ・ノードから辺を渡って別のノードへ移動する ・今いるノードにつながる辺を一つ削除し、今いるノードにとどまる 辺が無いノードには移動できない。削除や移動…
