問題概要 バブルソートの交換の回数を求めよ

問題概要 マス目上に木となっている地図が与えられる。最大の距離となる2点の距離を求めよ。 解法 木の2点間最長距離を求めるには、任意の頂点から探索を行ない一番遠かった点から再度探索を行なう。 これをBFSで実装した。 実装(C++) #include <cstdio> #include <queue> #</queue></cstdio>…

問題概要 0 解法 nCk=n!/k!/(n-k)!なので、整数m!に含まれる素因数2の個数を求めることが出来れば簡単に判定出来る。 これは、mをどんどん2で割っていくことで求めることが出来る。 実装(C) #include <stdio.h> int calc_2(int a){ int res=0; a>>=1; while(a>0){ res</stdio.h>…

問題概要 長さが1〜Nの木がそれぞれあり、それを使って柵を作りたい。 ただし、柵はジグザグな形になるようにするようにしたい。 C番目の作り方を求めよ。 解法 dp[進行方向の残りの木の本数][全体の残りの木の本数]とすることで、O(N^2)でパターン数を求め…

問題概要 廊下を通って荷物を運ぶことを考える。それぞれの荷物運びに関しては独立に廊下を共有しないものに関しては同時に運ぶことが出来る。 何回運べば、全ての荷物を運び終えることが出来るか。 解法 ある廊下の前を通る最大の数を求める 実装(C) int ma…

問題概要 格子状のマス目があり、いくつかに障害物がおかれている。(0,0)から(x,y)への移動の最短距離を求めよ3 解法 BFS 実装(C++) #include <algorithm> #include <iostream> #include <queue> #include <cstring> using namespace std; typedef pair<int,int> P; queue<P> que; int MAP[1010][1010]; int co</p></int,int></cstring></queue></iostream></algorithm>…

問題概要 問題文にある図のようなスライドパズル（0の部分が空）を解け。

問題概要 N( 解法 BitDPする。（10！）なので全探索でも間に合うかも…？ 実装(C++) #include <iostream> #include <algorithm> using namespace std; #define chmin(a,b) a=min((a),(b)) int main(){ int T; cin>>T; while(T--){ int n,x[11],y[11],dp[11][1<<11]; cin>>x[0]>>y[0</algorithm></iostream>…

問題概要 N個の点が与えられる。点間に直線を引いて全ての点同士で移動が可能にする時に最小の線の長さの合計を求めよ。

問題概要 牛に部屋を与えたいが、牛はそれぞれ部屋の希望をいくつかもっており、さらに一つの部屋に一つの牛しか割り当てられない。希望の部屋に割り当てられる牛の数を求めよ。

問題概要 N個の町があり、それぞれを繋ぐ道路を建設するのにかかる費用が与えられる。全ての町が繋がるような最小のコストの木のうち、もっとも高いコストの辺を求めよ

問題概要 二つの文字列の編集距離を求めよ。複数ケースあるので注意 解法 編集距離をDPで求める。 詳しくはレーベンシュタイン距離 - Wikipediaを詳細。 実装(C++) #include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,m; int dp[1001][1001]; char x</cstring></iostream></cstdio>…

問題概要 4x4のスイッチがある.全てのスイッチをOFFにしろ。ただしあるスイッチをクリックするとその列とその行のスイッチ全てが反転される。 解法 単純に全探索だと間に合わないので半分全列挙する。 実装(C++) #include <iostream> #include <algorithm> using namespace std; s</algorithm></iostream>…

問題概要 NxMに単語を隣接するように取り出していくゲームがある。P個の単語が取り出された時、残りの文字を辞書順に求めよ。

問題概要 H,Mが与えられる。 Σ(i=1..H)Ai^BiをMod Mで求めよ

問題概要 文字列集合に対して、マッチする辞書順最小の文字列を求める問題。ただしマッチする時に、|で区切られたどれかにマッチすれば良い。 マッチは、+が前に付いた文字を必ず含み、-が前に付いた文字は必ず含まず、さらにそれ以外の一文字以上を含むとい…

問題概要 数列をある条件でエンコードしたものが与えられる。デコードせよ。

問題概要 N個の点が与えられる。この中で3つの点を選んで三角形を作った時の面積の最大値を求めよ。

問題概要 NxNの配列が与えられる。k個のクエリーに対して xi

問題概要 全て長さがF以上の区間について、平均値が最大のものを求めよ。

問題概要 凸多角形の頂点がランダムな順番で与えられる。 (0,0)にある頂点(かならず与えられる)から反時計周りの順番で頂点の座標を答えよ

問題概要 アルファベットからなる文字列を'A'→1、'B'→2、……、'Z'→26のように数字に置換し、それを並べてエンコードすることを考える。(例：BZ→226) 復号方法は何通りあるのか答えよ

問題概要 1〜Kの数字を含んだN項の数列が与えられる．数列の部分列とならないような最小の部分列の長さを求めてください．

問題概要 0と1からなる二つの画像A,Bが与えられる． Bの任意の行と列を消して画像Aが作り出せるかを求めよ．

問題概要 X0=S Xn=(A×Xn-1+B)%C で表わされる数列Xの各Bitについて，0しか取らない，1しか取れない，0と1のどちらも取り得るの3種類のうちどれに当て嵌まるか答えよ．

問題概要 赤，緑，黄色，青のブロックをN個並べたい． ただし，赤と緑は偶数個並べたい． この時並べ方は何通りあるか．

2138 -- Travel Games 問題概要 牛さんが "travel games"というゲームをして遊ぶことにした． "travel games"はある牛が作った単語に一文字足して次の単語を作るということを繰り返していくゲームだ． さて辞書が与えられた時に最も最終結果の単語がながくな…

2388 -- Who's in the Middle 問題概要 N個(奇数)の値が与えられるので中央値を求めよ

2389 -- Bull Math 問題概要 二つの巨大な数に対するかけ算を求めよ ただしライブラリを用いてはいけない

2247 -- Humble Numbers 問題概要 素因数として，2，3，5，7しか含まない数をhumble数という． n番目のhumble数を求めよ． ただし，出力時の数詞は"nd","st","rd","th"を正しく使いわけろ．