はやし屋

競技プログラミングのメモ きたない

ICPC 2015 アジア地区予選参加記

課題に追われてるのでまともに推敲していません. いつか添削します.この記事はTUT Advent Calendar 10日目の記事です. 前日12/9はayafmyさんの他系の単位の食べ方、そして他系の単位を食べることによるその効果。です. はやしやと言います.現在はTUTのB…

AOJ 0215: Pachimon Creature

約二年ぶりに解きなおした.懐かしい. 属性ごとの座標を配列に保存して, dp[今の属性][今の属性から伸びてる辺が何番目のものか] = 最短路; みたいな感じでやりました. きれいに書きたい. #include<iostream> #include<algorithm> #include<cstdlib> #include<vector> #include<map> #include<cstring> using </cstring></map></vector></cstdlib></algorithm></iostream>…

AOJ 2585: 1 Day Passport

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2585ICPCに出ることになったので,久々に競プロしました. dijkstraは忘れていなかったのでよかった. 問題が長かった.構造体の使い方忘れてた. 徹夜明けでもありバグがひどく出た.1月半後のIC…

pku : 3252 Round Numbers

pkuかpojかどっちなんですかね... http://poj.org/problem?id=3252問題は整数S,F(1 ≤ S S以上F以下の Round Number の個数を求める問題です。Round Numberというものは、 整数を二進数に直したときに、"たっているビット数" であるような数です。具体的には …

AOJ 2022: Princess, a Cryptanalyst

後ろにつなげていくイメージのbitdp INF足りなくてWAした~~~~~~~~~~~ ""でもよかったような #include<iostream> #include<algorithm> using namespace std ; int n ; string s[11]; string G[11][11]; string dp[11][1<<11]; const string INF = "~~~~~~~~~~~~~~~~~~~~</algorithm></iostream>…

AOJ 0570: Zig-Zag Numbers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0570下手の横好きを参考にやりました。 こんなの初めてだq 頭いいなあ(感動のあまり死亡) dp[今の桁][前の桁の数字][前の桁のupdown][前までのmod][今すべての数字を使えるか]; でやった本番でと…

AOJ 0540: Amidakuji

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0540辿るとできる 面倒だった 無駄なくやるとよい #include<algorithm> #include<iostream> #include<vector> #include<map> using namespace std; int main(){ int n , m , h , k; while(cin >> n >> m >> h >> k &&(n|m|h|k)){ vec</map></vector></iostream></algorithm>…

AOJ 1156: Twirling Robot

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1156やるだけです #include<iostream> #include<map> #include<algorithm> #include<cstring> #include<queue> #include<vector> #include<cstdlib> using namespace std; #define fr first #define sc second typedef pair < int , int > Pi; typedef pair < </cstdlib></vector></queue></cstring></algorithm></map></iostream>…

AOJ 1150: Cliff Climbing

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1150&lang=jpDijkstraっぽい移動できるマスのおおまかな条件は、 "十字方向に移動すると考えた時3歩以内で行けるところ"でかつ"足の内側" なのでテーブル使わなくても適当にforを回すとできる。三…

PCK 2013 本選 4,6

ウッ頭が...巨樹の刻み手 再帰でやると無限にやる場合の場合わけとかめんどくさそうdpる #include<iostream> #include<map> #include<algorithm> #include<cstring> #include<vector> using namespace std; #define ALL(a) a.begin() , a.end() #define chmin(a,b) a=min(a,b) int main(){ int d , n; wh</vector></cstring></algorithm></map></iostream>…

AOJ 0581: Gifts

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0581逆にしてdpするのが良いと思って実装したが、既に訪れたとこどう管理するかわからなかったので、公式解説を見た。 http://www.ioi-jp.org/joi/2012/2013-yo/2013-yo-t6/review/2013-yo-t6-rev…

パソコン甲子園(PCK) 2013 (もうひとつの)本選 参加記

予選落ちの悲しみを引きずって参加 AC:1,2,3,5 0WA で多分2,3位っぽい(?)。 本選行ってたら一桁ワンチャンあったかもしれない 1:相方が適当に書く2:O(N*M*L)とかどんなアルゴリズム使うのと思ったらvectorで書いたソースが通ってしまった よくよんだらこなし…

パソコン甲子園2013 予選8問目 (AOJ 0283: Study Session)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0283二分探索の添え字がずっとバグってて触れてなかった データ多いからstaticしないとだめです 結局ソースみてしまったのでじぶんでバグらず速く実装したい... #include<vector> #include<set> #include<cstdio> #incl</cstdio></set></vector>…

AOJ1320: City Merger

bitdp 遷移ちがってんのかなあって思ったら、 データが完全に含まれている場合とか見落としていた #include<iostream> #include<algorithm> #include<vector> using namespace std; const int mx = 15*22; int main(){ int n ; while(cin >> n && n) { vector < string > data(n); for(int</vector></algorithm></iostream>…

AOJ 0266: Aka-beko and 40 Thieves

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0266辺を張ってぐるぐるやる #include<iostream> using namespace std; int edges[7][2] = {{1,2},{6,3},{1,6},{4,5},{5,2},{2,1},{6,6}}; int main(){ string s; while(cin >> s && s != "#"){ int v = 0; </iostream>…

KUPC 2013 F - 7歳教

http://kupc2013.contest.atcoder.jp/tasks/kupc2013_fワーシャルフロイドやってやるのはわかった。ダイクストラで TLE になってしまったので priorityけして幅優先にしたら AC した。ノードをソートするときにおもくなるのかな... #include<cstdio> #include<queue> #inclu</queue></cstdio>…

AOJ 2013: Osaki

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=605772 入るときと出るときっぽいものをぶち込んで、 ソートして最大値取るいも #include<cstdio> #include<vector> #include<algorithm> #include<map> using namespace std; int main(){ int n; while(scanf("%d",&n) && n){ vector </map></algorithm></vector></cstdio>…

AOJ 0234: Aizu Buried Treasure

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0234いったとこビットで保存しておいて適当に再帰する。 階層が変わる(y座標+1になる)ごとにbitを0にします。 #include<iostream> #include<algorithm> #include<map> using namespace std; int w , h; int stage[11][11]; i</map></algorithm></iostream>…

AOJ 2011: Gather the Maps!

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011めっちゃ時間かけた... long long やらんとダメです ビットでやると楽 #include<iostream> using namespace std; int main(){ int n ; while(cin >> n && n){ bool isok[33][55] = {}; // day , hito lo</iostream>…

AOJ 0263: Beat Panel

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0263消える処理考えるのに時間がかかったbitdpメモ化 #include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; int n ,c ; int dp[1<<16][33]; vector < int > pat , can; int in(){ int ret =</algorithm></vector></cstring></cstdio>…

AOJ 1045: Split Up!

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045 ビットでやると楽だった #include<cstdlib> #include<iostream> #include<cstdio> #include<vector> using namespace std; int main(){ int n; while(cin >> n && n){ int ret = 1<<28 , sum = 0; vector < int > v(n); for(int </vector></cstdio></iostream></cstdlib>…

AOJ 0094 0095 0096 0097 0098 0099

AOJ 0094 坪面積の計算 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=00941坪のをコピペする #include<cstdio> int main(){ double a,b; scanf("%lf%lf",&a,&b); printf("%.6lf\n",a*b/3.305785); return 0; } AOJ 0095 ワカサギ釣り大会 http://judge</cstdio>…

JOI予選2006やってみた

C縛り1.得点 AOJ0510 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0510やる #include<stdio.h> int i,in,a,b; int main(){ for(;i++<4;b+=in)scanf("%d",&in); for(;i++<4;a+=in)scanf("%d",&in); printf("%d\n",a>b?a:b); return 0; } 2.未提出者は誰</stdio.h>…

AtCoder Beginner Contest #002

あ^~いいっすね^~A.正直者 http://abc002.contest.atcoder.jp/tasks/abc002_1めっちゃむずい #include<iostream> using namespace std; int main(){ long long a , b ;cin >> a >> b; cout << (a>b?a:b) << endl; return 0; } B.罠 http://abc002.contest.atcoder.</iostream>…

AOJ 1056: Ben Toh

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1056&lang=jpつかいまわしたかった #include<cstdio> #include<algorithm> using namespace std; double dp[2][15]; double res[111111]; int main(){ dp[0][0] = 1; double cur = 0; for(int i = 0 ; i < 111111 ; +</algorithm></cstdio>…

AOJ 2117: Connect Line Segments

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2117一筆書きしろという問題 TSPでやったけど 繋ぎ方が綺麗にかけなくて解答を見た 点線出して最後に繋ぐイメージでやった #include<iostream> #include<string> #include<bitset> #include<cctype> #include<cstdlib> #include<set> #include<map> #inc</map></set></cstdlib></cctype></bitset></string></iostream>…

AOJ 0116 : Area of Polygon

大小比較だけなのでsinの値だけでOK EQ判定のみ誤差った(謎) #include<stdio.h> #include<math.h> #include<stdlib.h> #define EPS 1e-6 #define rep(i,n) for(i = 0 ; i < n ; ++i) #define EQ(a,b) (fabs(a - b)</stdlib.h></math.h></stdio.h>

JOI予選2009やってみた

ばぐるやばぐる1.レシート AOJ 0543 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0543 なにして汚したんだろ #include<cstdio> int main(){ for(int n;scanf("%d",&n)&&n;printf("%d\n",n)) for(int t,i=9;i--;n-=t)scanf("%d",&t); } 2.すごろく AOJ</cstdio>…

JOI予選2007やってみた

勝 利1.おつり AOJ0521 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0521 テーブル作らずできないかなーでやったら出来た #include<cstdio> int main(){ int n; while(scanf("%d",&n)&&n){ int ch = 1000-n,ret = 0; for(int i = 1 ; i < 1000 ; i*=1</cstdio>…

JOI予選2013の復習

ぼちぼち色々埋めていきます1.宿題 (Homework) AOJ0576 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0576 切り上げる。 #include<iostream> using namespace std; int main(){ int l , a , b , c , d; cin >> l >> a >> b >> c >> d; cout << (l-max((a</iostream>…

パソコン甲子園(PCK) 2013 予選 参加記

後輩と出場して 予選落ちしました。 問題は良問ばかりでしたが、緊張と困惑で 6AC + 4WAしました。 ソースは後から書き直したものです(考え方自体は変わってない)方針は1~6が後輩が解いてその間に自分が後半を読むとかしてたけど、 お互い緊張しててgdgdだっ…

SRM 588 div2

初するめ。250 KeyDungeonDiv2鍵は消え去らないので普通に左から見ていく。 足りない分は白鍵で補充してやる。 class KeyDungeonDiv2 { public: int countDoors(vector <int> doorR, vector <int> doorG, vector <int> keys) { int n = sz(doorR) ; int ret = 0; rep(i,n){ </int></int></int>…

0106: Discounts of Buckwheat

悪問と聞いたがなんとなくやったら出来た 最近dpの理解が深まります int w[] = {200 , 300 , 500 , 1000 , 1200 , 1500}; int p[] = {380 , 550 , 850, 380*5*0.8 , 550*4*0.85 , 850*3*0.88}; vector < int > dp(5555,INF);// weight void init(){ dp[0] = …

抱負

コツコツとやってきます 夏休みにvol5をやる コンテストに出る 様々な過去のコンテストを復習する アルゴリズムの幅を広げる 落ち着いて問題をよく読む 先輩の足を引っ張らない pck、joi頑張る ゲーム作り 勉強も頑張る 後輩にも目を配る などどうしても解け…

aoj 0244: Hot Spring Trip

さっきからちょっと休憩してやった二個飛ばしはすぐ浮かんだ #include<iostream> #include<vector> #include<algorithm> #include<queue> #include<cstring> using namespace std; #define rep(i,n) for(int i = 0 ; i < n ; ++i) struct edge { int t , c; edge(int t , int c): t(t) , c(c){}; }; struct</cstring></queue></algorithm></vector></iostream>…

aoj 2021: Princess in Danger

やっとできた... 変なテンションで書いたわけわかんないコメントは無視 #include<iostream> #include<vector> #include<map> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; int n , m, l , k , a ,h; // to cost struct edge{ int t , c; edge(int t , int c):t(t),c(c</algorithm></cstring></queue></vector></map></vector></iostream>…

aoj 1030: Cubes Without Holes

n*n*nの配列より、 全体から引くことのほうが早く浮かんだ #include<iostream> #include<set> #include<map> using namespace std; #define mp(a,b) make_pair(a,b) int n, h; int main(){ while(cin >> n >> h && (n|h)){ set < pair < int , pair < int , int > > > st; for(in</map></set></iostream>…

aoj 2153: Mirror Cave

ボカロだ~タイピング遅いなあ...解法は愚直に幅優先やって 00.53 sec 10096 KB 77 lines 1418 bytes だった一位の人 00.23 s ってどんな方法でやったのだろうか #include<iostream> #include<queue> #include<algorithm> #include<cstring> using namespace std; #define rep(i,n) for(int i = 0 </cstring></algorithm></queue></iostream>…

aoj 0114: Electro-Fly

lcmとってやる #include<iostream> #include<algorithm> using namespace std; #define lcm(a,b) ((a)/(__gcd(a,b))*(b)) long long calc(long long a , long long b){ long long ret = 1; long long c = a%b; while(c != 1){c = (a*c)%b;ret++;} return ret ; } int main(){ long</algorithm></iostream>…

aoj 0230: Ninja Climbing

まともな初投稿(?) めんどくさそうだったけどそうでもなかった 幅優先 #include<iostream> #include<queue> using namespace std; struct P{ int ch,cost,h; P(int ch,int h,int cost):ch(ch),h(h),cost(cost) {} }; int n; int stage[2][11111]; int calc(){ bool used[2][11</queue></iostream>…

pre

a #include<stdio.h> int main(){ printf("Hello World\n"); return(0); }</stdio.h>

はじめました

競技プログラミングのことを書きたいと思います。