深さ優先探索＋ダイクストラ幅優先探索使ったほうがいいことにACしたあと気がついた。 まあ通れば勝ちでしょ...（震え声 #include <bits/stdc++.h> using namespace std; const int INF = 1000000000; const int MAX_V = 5003; int cost[MAX_V][MAX_V]; int cosn[5003][5003</bits/stdc++.h>…

ひとつ前の「最悪の記者」のほうが少し難易度が高いきがする。部分点解法全く思いつきませんでしたすいません。 満点解法 深さ優先探索(DFS)をする. まず一番上にあるモビール（？）をもとめる。 そのモビールを関数dfsに投げる 関数dfsはそのモビールに必要…

部分点解法 N個のチームの順位のつけ方をすべて試し、適する順位を求める。計算量はO(N!)であり、これでは全体の30%しか得点を得られない。 満点解法 トポロジカルソートをする。 計算量はO(N + M).これについてはJOIの解説と全く同じなのでそちらを参照して…

満点解法より効率の悪い解法を考えるほうが難しいと感じた。 部分点解法 ４重ループで4本の柱を選び、それが正方形か調べその面積の最大値を求める。O(N).でもこんな解法を本気で考える人はいない気がするな・・・ 満点解法 bool型の配列などで、座標を指定…

ごり押しで何とかいけそうな問題。ソートをして少し考察しましょう。JOIの解説の通りにバケットソートを用いて解きました。問題文の言われたとおりにやっただけなので解説は省かせてもらいます。 #include <cstdio> #include <algorithm> using namespace std; int main(){ int </algorithm></cstdio>…

部分点解法についてのソースも乗のっけていこうと思いましたが、AOJで部分点採点してくれないことに気が付いたのでやめます。すいません。 部分点解法 a[i]からa[i+k-1]までの和をfor文で求め、これを0 オーダーはO(NK). 参考までに↓ int max = 0 for(int i …

エラトステネスの篩、生半可な知識で適当に実装してみたら一発で通ったのでらっきー。bool型の配列って全部初期化すること可能なんでしょうか。 #include <cstdio> #include <iostream> using namespace std; int main(){ int n; while(cin >> n){ bool d[1000000]; int ans = </iostream></cstdio>…

ちなみに問題はこちらです。 ぱっと見面倒くさそうだなぁと思ったけどそうでもなかった。 mapは便利。解法：幅優先探索 "01234567"から0を移動させた回数の最小を全部求めてバッと答えだす。（日本語苦手 #include <map> #include <string> #include <queue> #include <utility> #include <iostream></iostream></utility></queue></string></map>…

joi-yosen~DP~ #include <cstdio> #include <algorithm> using namespace std; int main(){ int d,n; int kion[203] = {0}; int huku[203][3] = {0}; int dp[203][203] = {0}; scanf("%d%d",&d,&n); for(int i = 0;i < d;i++){ scanf("%d",&kion[i]); } for(int i = 0;i < n;i++</algorithm></cstdio>…

致命的なミスをして一発ACできなかったから精進。解法：なし。 #include <cstdio> using namespace std; int dy[] = {-1,0,1,1,0,-1}; int dx0[] = {0,1,0,-1,-1,-1}; int dx1[] = {1,1,1,0,-1,0}; int w,h,ans = 0; int m[110][110] = {0}; void dfs(int y,int x){ </cstdio>…

これほど汚いソースを見たことがない。 戒めのためにはります。 #include <cstdio> #include <queue> #include <cstdlib> using namespace std; int h,w,n; int nx,ny; int dx[] = {0,1,0,-1}; int dy[] = {1,0,-1,0}; int ans = 0; char m[1003][1003]; void search(int ty,int tx,c</cstdlib></queue></cstdio>…

JOI予選問題解法:典型的なDP 問題しっかり読もうと思った #include <cstdio> using namespace std; int main(){ const int mod = 10000; int n,k; int yotei[102]={0}; int dp[102][4][2] = {0}; scanf("%d%d",&n,&k); for(int i = 0;i < k;i++){ int a,b; scanf("%d</cstdio>…

joi予選の問題。こういうのめっちゃ苦手だけど成長したのか瞬殺だった。 解法:線形探索 #include <cstdio> #include <cstring> using namespace std; int main(){ int n,ans=0; char name[27],s[102][102]; scanf("%d",&n); scanf("%s",&name); for(int i = 0;i < n;i++){ sca</cstring></cstdio>…

joi予選の問題。解法:ソートのみ一見難しそうに見えるが読んでみると解法が顕著で簡単な問題。(sortのgreater＜int＞()って#include ＜iostream＞必要だったんですね。。。) #include <cstdio> #include <algorithm> #include <iostream> using namespace std; int main(){ int n,a,b,c,d[</iostream></algorithm></cstdio>…

とりあえず二問。AOJ0595非常に汚い #include <cstdio> using namespace std; int main(){ int n; char s[1003]; int dp[1003][8] = {0}; scanf("%d",&n); scanf("%s",&s); if(s[0] == 'J'){ dp[1][0] = 1; dp[1][3] = 1; dp[1][5] = 1; dp[1][6] = 1; }else if(s[0]</cstdio>…

AOJ0173やるだけ #include <cstdio> #include <iostream> using namespace std; int main(){ char s[17]; int a,b; for (int i = 0;i < 9;i++){ cin >> s >> a >> b; cout << s << " "; cout << a + b << " "; cout << a * 200 + b * 300 << endl; } return 0; } AOJ0174yaruda</iostream></cstdio>…

進捗アリです。 めんどくさかった 予選でフィードバックないから死んじゃう 解法はjoi公式の奴と一緒です。はい。ちょっとおんなじことを繰り返している部分があるけど直すのめんどいんですいませぇん //こんな問題予選に出たら解きたくないわ～ #include <cstdio> #</cstdio>…

やるだけつらい #include <cstdio> using namespace std; int main(){ while(1){ int n; bool t[203],h[203]; scanf("%d",&n); if(n == 0) break; for(int i = 0;i <= n*2;i++){ t[i] = false; h[i] = false; } for(int i = 1;i <= n;i++){ int tmp; scanf("%d",&tmp</cstdio>…

ねむい。 #include <cstdio> #include <iostream> #include <cstring> using namespace std; int main(){ while(1){ int n; int ans = 1; int s[7] = {0,1,2,3,4,5,6}; scanf("%d",&n); if(n == 0) break; for(int i = 0;i < n;i++){ char sai[10]; cin >> sai; int t1=s[1],t2=s[2],t3=</cstring></iostream></cstdio>…

Nの範囲が記述されていないから、ちょっとダメな問題ではないか…まあいいや。 map使いたかったけどキーをcahrにしたら闇になるから闇。実行速度の関係から、あんまりiostream系を使うのはよくないと思います。 #include <iostream> using namespace std; int main(){ w</iostream>…

なんとか通りました。つかれた。問題文はこちら世界スパッゲッティソース大会で決勝にいけそうなソースです。joi本選の練習も兼ねて、mapとかvectorとかqueueとかpairとかいろんなの使ってみました。 なのでとても複雑になってしまった。。。実行時間もそこ…

問題分は「AOJ 0541」とでもググってください。 DPでやりました。 N-1回目までの散歩でそれぞれ何回その場所に通るか回数をdpに入れていき、その合計が偶数なら何もしない、奇数なら「南」「東」を反転させ、N回目をシミュレーションしていき感じです。 おそ…

問題はこちらなんかいろいろめんどくさかった。 メモリに気をつけよう（節約しました 細かいとこばぐんないようにしよう。 あとは気合 ソースとても汚いけどまわりと比較して実行時間そこまで遅くないので吉としよう。 #include <cstdio> #include <algorithm> #include <string.h> using </string.h></algorithm></cstdio>…

問題文はこちら。 瞬殺問題。 二分探索地味に初めてでした。 一発ACはたのしい。 #include <cstdio> #include <algorithm> #include <vector> using namespace std; int main(){ while(1){ long int d = 0; long int n = 0; int m = 0; long int ans = 0; vector<long> dat; vector<long>::iterator </long></long></vector></algorithm></cstdio>…

どう見ても解法わるい #include <cstdio> #include <algorithm> using namespace std; int alen = 0,blen = 0; short ans = 0; short a[5003] = {0}; short b[5003] = {0}; short dp[5003][5003] = {0}; int main(){ scanf("%d %d ",&alen,&blen); for(int i = 0;i < alen;i++){</algorithm></cstdio>…

問題文はこちら。たぶんやるだけ。もっともっといい解法がある気が... そーす汚すぎて何も言えないです。 #include <cstdio> using namespace std; int n = 0,m = 0; long k = 0; char tizu[1003][1003]; int dp[1003][1003][3] = {0}; int func(char sss){ int r = </cstdio>…

問題文はこちら 長年頭の中では解けていたけど、実装していなかった問題。解けて頭がすっきりした。 解説の効率のよい解法で計算量がO(n^2 log n)と書いていたのをみて、「これはO(n^2/2)でいけるのでは」と思って実装してみた。やるだけでとてもかんたんだ…

はい。おそらく誰でも解けるでしょう。 問題文はこちら。 #include <cstdio> #include <algorithm> #include <cstring> using namespace std; long n = 0; char s[1000003]; long int ans = 0; int main(){ scanf("%s",s); n = strlen(s); for(long i = 0;i < n;i++){ if(s[i] != 'J'){ c</cstring></algorithm></cstdio>…

なんかJOI前に簡単な問題解いて調子をあげるため、やるだけ問題をやっていた。

暇つぶし。JOI予選も近いんで、簡単な問題とかもやってみよう。※ソースきたないです。時間ないんで途中まで。