C言語でmapが必要になったときのためのライブラリ。 mallocが遅いだろうと思って、 spaghetti sourceのAVL木をmallocを使わずに書き換えたもの。 ソースコード #include<stdio.h> #include<string.h> /* AVL木によるmapの実装 spaghetti sourceの移植だけど、mallocなし版 */ #d</string.h></stdio.h>…

問題 三つの文字列a,b,cが与えられる。 a,b,cの全てに（必ずしも連続しない）部分文字列として含まれる文字列はいくつあるか、求めよ。 制約条件 a,b,cはアルファベット小文字からなる。 a,b,cの長さ≦50

問題 n個の行列が与えられて、それぞれの大きさはN[i]行M[i]列である。 この行列を、好きな順に並び替えて掛け算する。 （ただし、並び替えた順で積が定義されるようにしなけらばならない） このとき、積の行列の要素の数がもっとも多くなるような並び順につ…

問題 フィボナッチ数は、F1=1, F2=1, Fn=Fn-1+Fn-2で定義される数列である。 1以上の整数について、fibonacci positionというものを考える。 1のfibonacci positionは2である。 nのfibonacci positionはFi=nとなるiがあるとき、iである。 ないとき、Fi＜nと…

問題 文字列sが与えられる。 文字列を連続する部分文字列に分割し、それぞれ全てが回文になっているようにしたい。 文字列は最小でいくつに分割する必要があるか、求めよ。 制約条件 sはアルファベット大文字からなる sの長さ≦2500

問題 nxmの長方形のグリッドがあり、各マスは何もないか、ブロックが置かれているかである。 このグリッドを正面から見たものと、横から見たものが与えられる。 グリッドには最小および最大でいくつのブロックが置かれているか求めよ。 制約条件 n,m≦50

問題 双方向キューをいくつか使って、与えられた数列を次のようにソートする。 数列の先頭から項を見ていき、 すでにある双方向キューどれかの先頭にその項を追加する すでにある双方向キューどれかの末尾にその項を追加する 新しい双方向キューを作り、その…

問題 jumpy numberとは、隣り合う桁の数字の差の絶対値が全て2以上であるような数を言う。 low以上high以下のjumpy numberの数を求めよ。 制約条件 low,high≦2*10^9

問題 正の整数が回文であるとは、整数を逆から読んでも同じであることを言う。 ただし、leading zeroはあってはならない。 （12321は回文であるが、123210は回文ではない） K番目（0-indexed）に小さな回文である正の整数を求めよ。 制約条件 K≦1000000000

問題 二つの文字列s,tが与えられる。 s,tをinterleaveに含む文字列の中で、連続する部分文字列のうち回文となっている部分の長さが最長の文字列の、回文となっている部分の長さを求めよ。 文字列Aから（必ずしも連続しない部分文字列として）Bを抜き出した後…

問題 n両の客車からなる電車がある。 一両の長さはlengthで、時刻0に電車の左端がx=0に位置している。 電車は数直線の正の向きに、trainSpeedで移動している。 泥棒が電車の左端から右端へ移動したい。 泥棒が移動する速度はrobberSpeedである。 線路には橋…

問題 数列t[i]が与えられる。 長さKの連続する部分列の中央値の、全ての合計を求めよ。 ただし、長さnの数列の中央値とは、nを小さい順に並び替えたときにn/2番目の要素を指すものとする。 制約条件 t[i]の長さ≦250000 K≦5000 0≦t[i]≦65535

問題 lowerBound以上upperBound以下の整数に表れる数字を全て合計した和を求めよ。（10から14なら、(1+0)+(1+1)+(1+2)+(1+3)+(1+4)） 制約条件 lowerBound, upperBound≦2*10^9

問題 n個の都市が、一方通行の道でつながっている。 それぞれの都市に警察を置くコストがcosts[i]により与えられる。 全ての都市に、「その都市または、その都市へ行くことが出来る都市のどれかひとつ」に警察が置かれている状態にしたい。 この状態で、警察…

問題 n個の幅の等しい長方形があり、それぞれの長さはpieces[i]である。 この長方形を、幅の等しい、長さがLの長方形の中に入れる。 中の長方形は重なったり、外にはみでていたりしてはならない。 中の長方形を、「他の使っていない長方形をどこにも追加する…

問題 n個の仕事があり、i番目の仕事はmoment[i]日目にあり、その報酬がearning[i]である。 報酬は、積算されていき、いつでも好きな日に銀行に振り込ませることができる。 ただし、振込みには一回につき、feeの手数料がかかる。 銀行にふりこまれたお金には…

問題 nマスが円状につながったすごろくがある。 通常の6面ダイスを振って、出た目だけ進んで、止まったマスに書かれた数字の点数を得る。 ゲームは（ダイスを振る前に）好きなタイミングで止めることができる。 最善の戦略を取るとき、ゲームで得られる点数…

問題 x,y平面上の原点に人がいる。 原点から、点(x,y)へ泳いで行きたい。 この人の泳ぐ速さは最大でVである。 水は、x軸の正の向きに、一様で速度Uで流れている。 この人が(x,y)まで着くのにかかる時間を求めよ。 (x,y)に辿り着けない場合は-1を返せ。 制約…

問題 n個の都市がn-1本の双方向に通行可能な道路によって結ばれている。 全ての都市のペアに対して、その都市同士を結ぶ道がただ一通りだけ存在する。 それぞれの道には、その道を破壊するコストが定められている。 occupiedTowns[]の都市を敵が占領した。 …

問題 長さLの丸太がある。 整数A,Kが与えられて、 この丸太を、 ( (A * i) mod (L - 1) ) + 1 （1≦i≦K）の位置で切ることができる。 丸太を最大でC回まで切ることができ、 丸太の最長の部分の長さを最小にするように切りたい。 最長の部分の長さの最小値およ…

問題 文字列の集合がprefix-freeであるとは、 どの文字列も、他の文字列の接頭辞となっていないことをいう。 空の文字列もprefix-freeである。 文字列の集合が与えられる。 この集合の部分集合（空集合および、元の集合そのものも含む）のうち、prefix-free…

問題 n種類のコインがあり、それぞれの価値はvalues[i]である。 X以下の整数の値段を全ておつりなしで支払えるようにコインを持ちたい。 コインは最小で何枚持つ必要があるか、求めよ。 制約条件 n≦10 values[i]≦1000 X≦1000

問題 '0'または'1'からなる文字列P1,P2が与えられる。 文字列S(n)を、P1を100万回繰り返した後、P2をn回繰り返した文字列とする。 文字列Sを、S(1)+S(2)+……と無限につなげたものとする。 文字列Tを、Sの先頭から10^16文字を取った文字列とする。 Tにおいてゼ…

問題 Nに対してSk(N)を、 Σ(Nの各桁)^kと定義する。 Nに対して、Nの幸福度を、数列N,Sk(N),Sk(Sk(N)),...,の最小値とする。与えられた整数A,Bに対して、 A≦i≦Bなるすべてのに対するiの幸福度の和を求めよ。 制約条件 A,B≦1000000 k≦6

問題 hxwのグリッドが与えられる。 グリッドのそれぞれには1〜9の数字が書かれている。 このグリッドの(startRow,startCol)を出発して、(goalRow,goalCol)へ行きたい。 一回の移動では、上下左右に何回か動くことができる。 ただし、一回の移動中に通ったマ…

問題 文字列が辞書順に並んだ辞書dictionary[]が与えられる。 k文字からなる単語を一つ、ランダムに生成する。 ただし、dictionaryの要素に一致するような単語は生成されない。 一致しない単語はすべて等確率で生成される。 生成した単語を辞書に入れるとき…

問題 n本のビルがあり、それぞれのビルは幅1高さh[i]の長方形をしていて、 (i,0)を左下の頂点、(i+1,h[i])を右上の頂点としている。 このビルに収まる、軸に平行な長方形のうち、面積が最大のものの面積を求めよ。 制約条件 n≦100000 h[i]≦835454957

問題 n枚のカードがある。 これらのカードに対して、2枚のカードをランダムに選び、その位置を交換するという操作をswapCount回行う。 操作前にa番目にあったカードが操作後にb番目にある確率を求めよ。 制約条件 n≦1000 swapCount≦100000

問題 nドルを賭け、勝つとnドルがもらえ、負けるとそのnドルを失うギャンブルがある。 次のような方針で賭けをする。 最初は1ドルを賭ける 負けた場合、前のラウンドの倍のお金を賭ける 勝った場合、前のラウンドの掛け金にかかわらず1ドルをかける 最初init…

問題 授業がn個ある。 それぞれ、三つの値theoreticalValue[i], practicalValue[i], expire[i]が定められている。 最初、theoretical, practicalの値は0で、 授業を取ると、theoreticalがtheoreticalValue[i]の値まで上がり、 theoreticalがpracticalValue[i…