コンテスト中の流れのメモ 開始直後、izさんがEclise、vim、キーボードを設定 その後izさんが15分毎に時刻を表示するPerlスクリプトを記述 開始15分程度でJを読み終わり、三角形分割等のライブラリーを写せば行けると考え、izさんにライブラリの一部を写して…
序盤 問題を読みおわって5分立ったら終わる ライブラリを写した方が良い問題については写す（幾何、文字列、数学) 読み合わせ時間に問題について話し合うのを止める 読み合わせは解法について話さない（次回実験） 読み合わせは30分以内に収めたい 実装前に…
ICPCアジア地区予選に参加しました． チーム編成 チーム名：UselessUltimate & Escapist Coders メンバー：@todo314(todo), @k_operafan(k_operafan), @izuru_matsuura(iz) 結果 8問正解，ペナルティ1007で3位でした． 戦略 PCを占有する時間が出来るだけ短…
@hiyakashi_さんに「ICPCって1日目と3日目は何してるの」と聞かれたので，コンテストの参加記録とは別にそこらへんについて箇条書き形式で適当に書きます． 一日目 お昼御飯にうどんをたべた 参宮橋駅でしめじたんさんとしおしおたさんと合流．LiveArchiveに…
ICPC国内予選に参加しました。 チーム編成 チーム名：UselessUltimate & Escapist Coders メンバー：@todo314(todo), @k_operafan(k_operafan), @izuru_matsuura(iz) 結果 問題数 ペナルティ A問題 B問題 C問題 D問題 E問題 F問題 G問題 5 18197 17:25 23:53…
問題概要 バブルソートの交換の回数を求めよ
解法 青い玉の数:n 合計の玉の数:m n*(n-1)/m*(m-1)=1/2 2(n*n-n)=m*m-m 2((n-1/2)^2-1/4) = (m-1/2)^2-1/4 2((2n-1)^2-1) = (2m-1)^2-1 (2m-1)^2 - 2(2n-1)^2 = -1なのでベル方程式 x^2 - 2y^2 = -1 を解く解の１つはx=29,y=41であることから順次解を構成し…
過去に投げたソースを検索しやすくするためにRuby（特にフレームワークは使用せず）で書きました。 http://k8n.biz/aojsts/
問題概要 日本語なので略 解法 N回BFSを行なう 実装(Java) import java.util.*; public class Main { Scanner cin; class State{ int time,x,y; State(int time,int x,int y){ this.time=time; this.x=x; this.y=y; } } void run(){ cin=new Scanner(System.…
問題概要 マス目上に木となっている地図が与えられる。最大の距離となる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で求めよ
解法 左上を優先的に消していく、かなり怪しい貪欲法で解いた 実装(C++) #include <cstdio> #include <iostream> #include <algorithm> #include <iomanip> #include <vector> #include <valarray> #include <cstring> using namespace std; struct Remove{ int x,y,size; }; struct Board{ int W,H; int data[20]; int clear_s</cstring></valarray></vector></iomanip></algorithm></iostream></cstdio>…
問題概要 文字列集合に対して、マッチする辞書順最小の文字列を求める問題。ただしマッチする時に、|で区切られたどれかにマッチすれば良い。 マッチは、+が前に付いた文字を必ず含み、-が前に付いた文字は必ず含まず、さらにそれ以外の一文字以上を含むとい…
問題概要 数列をある条件でエンコードしたものが与えられる。デコードせよ。
問題概要 N個の点が与えられる。この中で3つの点を選んで三角形を作った時の面積の最大値を求めよ。
問題概要 NxNの配列が与えられる。k個のクエリーに対して xi
問題概要 全て長さがF以上の区間について、平均値が最大のものを求めよ。
問題概要 凸多角形の頂点がランダムな順番で与えられる。 (0,0)にある頂点(かならず与えられる)から反時計周りの順番で頂点の座標を答えよ
