2013-01-01から1年間の記事一覧
今日もcombinatorics埋めていきます。319A - Malek Dance Club 難しそうだが考えたら独立だった。 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; char str[128]; int main(){ scanf("%s",str); int mod=1000000007; int n=strlen(str); int ret=0; for(i</string.h></algorithm></stdio.h>…
敗北しました。250:きつね やるだけ。 public class FoxAndChess{ public String ableToMove(String a,String b){ int s[]=new int[100]; int S[]=new int[100]; int t[]=new int[100]; int T[]=new int[100]; int m=0; int n=0; for(int i=0;i
つづきです。Solvedがだんだん減っていきます。84B - Magical Array 数えるだけ。オーバーフローした。 #include<stdio.h> int a[100000]; int main(){ int b; scanf("%d",&b); for(int i=0;i</stdio.h>
今日は簡単な順にcombinatoricsを埋めています。Solvedの多い問題からCombinatoricsを埋めていきます。131C - The World is a Theatre コンビネーションの掛け算やるだけ。 #include<stdio.h> long long C[61][61]; int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c);</stdio.h>…
せっかくの機会なので、CFの過去問をガチで埋めていこうと思います。しばらく経つ頃にはきっと私はレッドコーダーになっていることでしょう。(現在Div1底辺)昨日といた問題103D こういう手の問題で平方分割をするのは典型ですが、この問題はクエリ先読みが大…
writerやってました。講評を書くことにします。Day 1 川越市街 初日にレアンと会う約束をしていたものの、道に迷ってしまい気がついたら家の方向への道をあるいていた、というのが元ネタの出題です。 川越駅と本川越駅と川越市駅は密集しています。三つとも…
左右をもつタイプのDP。 結構大変ですが、なんとかはなります。 #include<stdio.h> #include<algorithm> using namespace std; pair<int,int> p[1000]; int t[1001]; int dp[1001][1001][2]; int ABS(int a){return max(a,-a);} int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); for(int</int,int></algorithm></stdio.h>…
KMP.久しぶりにオンラインジャッジをやるにはいい問題だと思います。これでPKUのUSACO Unsolvedは16→13に。 #include<stdio.h> #include<algorithm> using namespace std; char str[10000][76]; int fail[10001]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i</algorithm></stdio.h>
7問残っています。 3667 Hotel 2042 USACO 2008 February Gold 2185 Milking Grid 1279 USACO 2003 Fall 3613 Cow Relays 1053 USACO 2007 November Gold 3167 Cow Patterns 536 USACO 2005 December Gold 3168 Barn Expansion 311 USACO 2005 December Gold…
①するめの話題SRM585に参加しました。久しぶりの参加です。250:数える問題。 DPする。 public class TrafficCongestion{ public int theMinCars(int a){ int MOD=1000000007; int dp[]=new int[1000001]; dp[0]=dp[1]=1; int val=0; for(int i=2;i<=a;i++){ …
Graph Construction。かなり一般化された問題。平方分割とUnionFindまでは自明に思い浮かぶとして、実装も軽いので投げれば通る。ちなみにUnionFindのオーダーはランクのほうをつかってO(log n)にしないといけないと思います。経路圧縮をするともとに戻せな…
たまにはパソコン甲子園の過去問でもやることにしました。0209 回転とかやれば楽。 #include<stdio.h> #include<algorithm> using namespace std; int M[100][100]; int v[100][100]; int x[100][100]; int main(){ int a,b; while(scanf("%d%d",&a,&b),a){ for(int i=0;i</algorithm></stdio.h>
今日はあまり難しい問題が解けなかった…あさって模擬国内なのに……(絶望)2446 罠が多い。へんなDPでほうじょ原理をする。これLCMがlong longに収まらないの大迷惑なんだが… #include<stdio.h> #include<algorithm> using namespace std; long long dp[1<<20]; long long c[20]; </algorithm></stdio.h>…
経路復元的なアレがあるフロー。フロー部分は簡単です。 #include <vector> #include <algorithm> #include <iostream> #include <queue> #include <cstdio> using namespace std; typedef int Weight; const Weight INF=99999999; struct Edge{ int dst,cap;Weight cost,rev; }; typedef vector<Edge> Node; ty</edge></cstdio></queue></iostream></algorithm></vector>…
TransfurTrain.配列のサイズを間違えてTrainがねこBusになりました。 #include<stdio.h> #include<algorithm> #include<queue> #include<map> #include<vector> #include<string> using namespace std; char str[16]; map<string,int> m; vector<pair<int,int> >g[100000]; vector<pair<int,int> >ijk[50000]; pair<int,int> IJK[100000]; vector…</int,int></pair<int,int></pair<int,int></string,int></string></vector></map></queue></algorithm></stdio.h>
500 点を埋める1311: Dijkstraするだけ。 #include<stdio.h> #include<algorithm> #include<vector> #include<queue> using namespace std; int ijk[100][100]; bool v[100][100]; vector<pair<int,int> >g[100]; int main(){ int a,b,c; while(scanf("%d%d%d",&a,&b,&c),a){ for(int i=0;i</pair<int,int></queue></vector></algorithm></stdio.h>
探索。答えはn-1以下であることとか、半分全列挙系を使えばいいとかを考えればいける。手元でテストするのが重過ぎる。 #include<stdio.h> #include<algorithm> using namespace std; int b[10]; long long c[5][4200000]; long long d[5][4200000]; int C[5]; int D[5]; long lo</algorithm></stdio.h>…
bitDP。面倒な形してるよね。 #include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int len[128]; int dp[2][1<<16]; char str[128][17]; int L[16][1<<16]; int R[16][1<<16]; int main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i</string.h></algorithm></stdio.h>
ようやくVolume 5が全部埋まりました。まだ増えるだろうけど、せいぜい8個。0508 枝かりゲーだと思っていたら枝かりの必要すらなかった。 #include<stdio.h> #include<vector> #include<algorithm> using namespace std; vector<int>g[100]; int used[100]; int solve(int a){ used[a]=1; int</int></algorithm></vector></stdio.h>…
残り少ないVolume 5。一応JOIのチューターなのでソースを書いてみたりするなど。 0509: O(N^2)をかけば通る。それより速い解法もあるんじゃないかなあ。どうなんだろう #include<stdio.h> #include<algorithm> using namespace std; int dp[2][10000]; pair<pair<int,int>,pair<int,int> >event[20000]; </int,int></pair<int,int></algorithm></stdio.h>…
A-Large,B-Largeで通過ですA:座標圧縮とか、変な計算とか、面倒なことが多いだけ。 #include<stdio.h> #include<algorithm> using namespace std; int d[1000]; int e[1000]; int f[1000]; int zahyou[2000]; long long v[2000]; int mod=1000002013; int main(){ int T; scanf("</algorithm></stdio.h>…
なんか今日はAOJのサーバーが落ちているのでかわりにLiveArchiveに登録してそこで通しておきました。テストケース数がおおいらしい。 #include<stdio.h> #include<algorithm> #include<math.h> #include<complex> #include<vector> #include<stdlib.h> #define curr(P, i) P[i] #define next(P, i) P[(i+1)%P.size()]</stdlib.h></vector></complex></math.h></algorithm></stdio.h>…
そろそろ幾何をやろうと思っていますが、幾何ってライブラリ全部打ち込むんですか?それとももっと簡略にしたりするんですか? #include<stdio.h> #include<algorithm> #include<vector> #include<math.h> #include<complex> using namespace std; double x[100][5]; double y[100][5]; double abs(double </complex></math.h></vector></algorithm></stdio.h>…
たぶんwriterはsnuke。250:うなぎとうさぎ これはやるだけです。 public class EelAndRabbit{ public int getmax(int a[],int []b){ int n=a.length; int []c=new int[n*2]; for(int i=0;i
とりあえず難易度表の500を埋めていくことにする。2200: 適宜最短路を求めたらDPするだけ。どこに500要素があるのかわからない。数が中途半端に大きく迷惑。 #include<stdio.h> #include<algorithm> using namespace std; int dp[1001][200]; int L[200][200]; int S[200][200]; </algorithm></stdio.h>…
Number Sorting. 辞書順は小数にするとそのままソートできて楽です。 後はBITでDPするだけなので何も言うことはない。 #include<stdio.h> #include<algorithm> using namespace std; int mod; pair<double,int> v[131072]; int bit[131072]; int sum(int a,int b){ if(a==0){ int ret=0; for(</double,int></algorithm></stdio.h>…
いつもwriterをするときにろくでもない文章を書いてmisofさんを困らせていたので、仕返しされました。250: TheEnglishReadingDivOne 英語を読むだけ。(Mediumのコード書くより難しい。てか結局問題の意味わからなかったし) public class UndoHistory{ public…
半日間で気がついたら結構解いていました。2383 逆辺っぽいものを考えるとどこから来れるか、みたいなものをしゃくとりでもとめていけばかけ算するだけになることがわかります。 #include<stdio.h> #include<algorithm> using namespace std; int v[100000]; int main(){ int a,b</algorithm></stdio.h>…
4日間で気がついたら結構解いていました。2372 紙に書いて法則を発見するとか。フィボナッチ数列で行列累乗もするし、いろいろと面倒な問題。 #include<stdio.h> #include<algorithm> using namespace std; long long mat[2][2]; long long now[2][2]; long long tmp[2][2]; int </algorithm></stdio.h>…
ざんねん! tozangezanの TCO2013は おわってしまった! おや、 tozangezanの ようすが…?デッデッデッデッデッデー デッデッデッデッデッデー(ピコーン) デッデッデッデッデッデー デッデッデッデッデッデー(ピコーン) デッデッデッデッデッデー デッデッデ…