ドミノ敷き詰め問題。 完全マッチングの個数を数える問題ともいうのかな。 bitDPでときました。 #include <cstdio> #include <algorithm> #include <string.h> using namespace std; int w,h; long long int dp[2][1 << 11]; int main(){ while(1){ scanf("%d%d",&h,&w); if(h == 0 && w =</string.h></algorithm></cstdio>…

こんな簡単なDPが眠っていたとは。。。 #include <cstdio> #include <algorithm> using namespace std; int p; int s[150002]; int dp[150002][2]; int main(){ scanf("%d",&p); for(int i = 1;i <= p;i++)scanf("%d",&s[i]); for(int i = 1;i <= p;i++){ dp[i][0] = max(dp[i-1</algorithm></cstdio>…

一応といてみた（n回目） 解説はJOI 2007-2008 予選 問題・データにあるのでそっちを見てください。サンプルソースだけﾄﾞﾃﾞﾝとはっておきます。 続きを読むでよめる・このぐらいのセットは30分で全完しないとだめだよな・・・

予選で落ちたらshare（洒落）にならないので予選対策は怠りません。

当たり前だけど一年前と比べて格段に能力があっぷしててうれしい。

そろそろ色々なものを禁止しないとやっばい

精進が足りない。 この低意識のままじゃ、本選はおろか予選落ち不可避勢になってまうぞ

バケット法を使うという解法もあるけど実は使わなくても可能という問題。探索＆再帰＆枝刈り #include <bits/stdc++.h> using namespace std; typedef pair<int,int> P; int n,m,d,k; bool used[100002]; int ch[1002][1002]; int z[100002][2]; vector<int> e[100002]; int ans = 0; int </int></int,int></bits/stdc++.h>…

トポロジカルソートやるだけ。 JOI本選過去問の「最悪の記者」に類似している。→リンク bool used[1002];//使ったかどうか int n,w,h; int s[1002][4];//0,1:左上、2,3:右下 int ans[1002];//答え逆順 int m[102][102];//map int inn[4] = {100,100,0,0}; in…

mapを使うことが出きるかを問うている問題。 実はa,b,の値は必要ない。 テストケース9が謎に最強だった。 typedef pair<int,int> P; int main(){ int n,a,b; scanf("%d%d%d",&n,&a,&b); map<P,int> m; int ans1=0,ans2=0; for(int g = 0;g < n;g++){ int p,q,r,s; scanf("%d%</p,int></int,int>…

問題文を読んで3秒で二分探索だと悟った。 こういう解法の決めつけはよくないと思うけど顕著すぎるんじゃ～ int n,m; int x[100003]; int y[100003]; bool ch(int d){ int co = 0; int h = x[0] + d; co++; for(int i = 1;i < m;i++){ if(x[i] > h){ co++; h…

典型DP 予選で出てもおかしくないレベルなので解説は割愛。#include や、using namespace std;は省略することにしました。 const int INF = 1000000000; int n,d; int dp[400][3002][3]; int p[400][3002]; int main(){ scanf("%d%d",&n,&d); for(int i = 0;…

木の深いところから順に見ていく。すべての人のやる気が負の時のコーナーケースに注意計算量O(N). int n; int d[100003][2]; int ans[100003]; int ho=0; int main(){ scanf("%d",&n); ho = 0; int m = -100000000; for(int i = 1;i <= n;i++){ scanf("%d%d"…

現実に吐きそうだから音楽を爆音で聞く

chromebook、買わないけれども値段が安いしいいね。これに影響されて他のメーカーのパソコンももっと安くなって欲しいと思う。 でもchromebookにlinuxいれていい感じになるなら買うかもしれない。あまりスペックにはこだわりがないし。

ただのDPのはずかstrlen()多用しすぎててTLEにになっていた。 気をつけよう。 #include <cstdio> #include <string.h> #include <iostream> using namespace std; char a[202],b[202],c[404]; bool dp[202][202]; int main(){ int n; cin >> n; int co = 1; while(n--){ memset(dp, 0, si</iostream></string.h></cstdio>…

某テキストエディタで:set smartindentというのを今更見つけた。 今まで:set autoindentを使っていたのが。。。

二次元累積和やるだけ。 #include <utility> #include <sstream> #include <cstdio> #include <string> #include <set> #include <iostream> using namespace std; char s[1002][1002]; int dp[1002][1002][3]; int main(){ int m,n,k; scanf("%d%d%d",&m,&n,&k); for(int i = 0;i < m;i++){ scanf("%s",s[i]);</iostream></set></string></cstdio></sstream></utility>…

進捗ﾀﾞﾒ 明日模試ﾀﾞﾒ

とても頭のわるいソースになった。英語読めな過ぎて「最初のところから25以上離れない」みたいな重要なところを読み飛ばしており仕方なくsetを使っていた。解き終えてからほかの人のブログで知った。 set＜string＞にしたらTLEになったので仕方なくpair使い…

くっそ頭悪い 戒め #include <set> #include <algorithm> #include <string> #include <queue> #include <iostream> #include <utility> #include <cstdio> #include <string.h> #include <vector> using namespace std; long long int d[10010]; long long int tmp[10010]; int main(){ long long int n; scanf("%lld",&n); for(in…</vector></string.h></cstdio></utility></iostream></queue></string></algorithm></set>

問題文典型DP。やるだけ。頭悪い。 #include <set> #include <algorithm> #include <queue> #include <utility> #include <cstdio> #include <string.h> #include <vector> using namespace std; typedef pair<int,int> P; P dp[5003]; int a[5003]; int main(){ int n; for(int i = 0;i <= 5000;i++){ dp[i].first = 1; } scanf(</int,int></vector></string.h></cstdio></utility></queue></algorithm></set>…

今後このブログに載せるソースは基本的にCode Lengthが1000Bを越えたものにする。 もちろん例外もあります

複数のテストデータがある場合など、どのくらいのテストケースがあるか明記されてないことがあって計算量を考えにくいからやめてほしい。。。

javaもそれなりに使えるようになっといたら便利じゃないかね、と思った。理由は BigIntegerででかい整数を扱える POJでC/C++でどうしてもTLEになってしまうムリゲーのときに抜け道として使用できる場合がある から。

今日から某テキストエディタを使い始めたけどめちゃくちゃいい。そのテキストエディタが何かについては言及しないようにします。

最近重い実装を一切していないのでそろそろ撃沈する。

個数制限付き部分和問題完全に蟻ゲー詳しくは蟻本p62参照 #include <algorithm> #include <string.h> #include <iostream> #include <cstdio> using namespace std; int a[11]; int m[11]; int dp[100003]; int main(){ int cash; while(cin >> cash){ int n; scanf("%d",&n); for(int i = 0;i < n;i</cstdio></iostream></string.h></algorithm>…

英語読めなさすぎ。冷える。 #include <cstdio> #include <algorithm> using namespace std; int d[30004]={0}; int main(){ int n; int ans = 100000000; int tmp = 0; scanf("%d",&n); for(int i = 1;i <= n;i++){ scanf("%d",&tmp); d[i] = d[i-1]; if(tmp==1)d[i]++; } int </algorithm></cstdio>…