まともに書こうとしたが、諦めた p:10000

*./ 1+i.20

J言語使うと簡単 q:が素因数分解する動詞です。 {:q:600851475143

1000未満で且つ、3か5の倍数である自然数の和を求める全くJらしくないですが、Jです。 (+/ 5 * 1+ i.199) + (+/ 3 * 1 + i.333) - (+/ 15 * 1 + i.66)多少改善 +/ ~. (5 * i.200),(3 * i.334)

" 入力例 2 において，あなたには友達はいない．"単一始点最短路を求める問題。 普通にダイクストラ法やワーシャルフロイド法するのは面白くないので少しだけ違う解き方をしました。想定解法とあまり変わらないみたいです。 #include<iostream> #include<cstring> #include<algorithm> usin</algorithm></cstring></iostream>…

DFS(深さ優先探索)の典型問題。m+2 × n+2のマップを使うとマップ外に出なくなるのでオススメです。 #include<cstdio> #include<algorithm> using namespace std; int m,n,unused[90][90],dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; int dfs(int y, int x, int d){//座標と、今までに</algorithm></cstdio>…

実装。色の変え方が最大で2パターンあるので、両方とも試す。 #include<cstdio> #include<algorithm> using namespace std; int n,chain[10000]; int fig(int b){ int a = b-1,c = b+1,color,res = 0; if(a>=0){//b == 0のバターンを弾く int s = 1; color = chain[a]; while(a></algorithm></cstdio>…

動的計画法で解きました。INFで初期化する代わりに-1で初期化してます。 #include<cstdio> #include<algorithm> #include<cstring> using namespace std; int n,m,x[151][11],d[150][11],dp[150][10][77]; const int INF = 1000000000; int main(){ while(scanf("%d%d",&n,&m),n){ memset</cstring></algorithm></cstdio>…

共通部分文字列の長さの最大値を求める問題。 1文字後ろを調べ、同じ文字列を重複して調べないようにすると、TLEしないで解けます。 O(n^3)かO(n^2)です。 #include<iostream> #include<string> #include<algorithm> using namespace std; string s,t; int main(){ while(cin>>s>>t){ int </algorithm></string></iostream>…

辺が増えていく最短経路問題。増えた辺を使うと経路が短くなる場合があるので、それを調べます。(増えた辺を使わないで経路が短くなることはない) O(kn^2)です。AOJではギリギリ通せなかったのですが、ワーシャルフロイド法(や、その他の最短路のアルゴリズ…

最大値の伝播で解くのは難しそうだったから、累積和で解きました。 少し枝刈りしましたが遅いです。 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int g[10003][10003]; int n,r; int main(){ while(scanf("%d%d",&n,&r),n){ memset(g,0,sizeof(g)); in</algorithm></cstring></cstdio>…

Div1は550を誰かが解かないとノーコン(Div1)になるらしいです(2012/04/15 15:01) 問題見てみたいけど、Div2だと見れないみたいです。practiceに入りました。 Easy(174.03 / 250) 遺伝子の情報が与えられて、1つの家族として考えられるものの中で、最も人数の…

Rが小さいので、行単位でひっくり返すのは全て試します。 列は自由にひっくり返すことができるため、表になっているものの個数か裏になっているものの個数の内大きい方を使えば良いです。 数えるのにO(RC)かかるので、全体ではO(RC･2^R)になります。 #include<cstdio></cstdio>…

星座にある星(固定しておく)から写真にある星までのベクトルを考えれば、並行移動の仕方はn通り あることが分かります。n通り全て試すためには、1通り試すのにO(m+n)やO(mlogn)程度で良いです。辞書順にソートしておくことで、O(n^2+mn)で解くことができます…

文字列から"JOI"と"IOI"を検索する 2文字目と3文字めが共通しているので、1文字目は後で考えると少し速くなりそうです。 #include<iostream> #include<string> using namespace std; string s; int main(){ while(cin>>s){ int a=0,b=0; for(int i=1,l=s.size()-1;i</string></iostream>

太郎が持っている:1 花子が持っている:0 残ってない:-1のようにすると、配列1つと単純なループで解くことができます。(入出力も簡単) #include<iostream> #include<cstring> using namespace std; int card[200]; int main(){ int n; while(cin>>n,n){ memset(card,0,sizeof(car</cstring></iostream>…

A. 前から数える。本番ではstring s[3000]としてRE #include <iostream> #include <string> using namespace std; string s[30000]; int main(){ int n,ans = 0; cin>>n; for(int i = 0; i < n; i++)cin>>s[i]; int f = 1; for(int i = 0,l = s[0].size(); i < l && f; i++){ c</string></iostream>…

メモ化再帰で解きました。 順番にモビールを選び、そこから下のモビールの重さ(の最小値)を再帰的に求めます。 重さ * 長さ = モーメント なので、両方のモーメントを求めて、整数倍(最小公倍数を求める)し釣り合わせます。 重さ = モーメント / 長さ で、重…

点A(a,b)と点B(c,d)があるとき、a A,Bを探すときは、入力された順に辿って行き、正方形ができているか調べるときは、辿らずに直接調べることで、O(n^2)になります。(全部辿るとO(n^4)になる) #include<cstdio> #include<cstring> using namespace std; int x[3000],y[3000],n,</cstring></cstdio>…

しゃくとり法で数えます。 0 2 3...n のときに、変な動作をしますが、撃墜はされません(他にコーナーケースがあるかもしれないけど、ACはできました) #include <algorithm> #include <iostream> #include <cstdio> #include <cstring> using namespace std; bool card[100020]; int n,k; int main()</cstring></cstdio></iostream></algorithm>…

DPの基本的な問題。メモ化再帰でも、普通の再帰でも、全探索でも解けるらしい。 ある点に行くのに、左か下から行かなければならないというだけ。 #include<iostream> #include<cstring> using namespace std; int dp[16][16]; int main(){ int a,b,n; while(cin>>a>>b,a||b){ ci</cstring></iostream>…

普通に面白かったです。 http://codeforces.com/contest/171A サンプルから推測。 #include<iostream> #include<string> using namespace std; int a; string b; int main(){ cin>>a>>b; for(int i = 0,t = 1,l = b.size(); i < l; i++){ a += (b[i]-48)*t; t *= 10; } cout<<a<<endl; } B 問題文は絵で与えられます。 #include <iostream> u</a<<endl;></string></iostream>…

再帰する式を作れれば解けます。右シフトすると一番小さいカップが消えてくれて、他のカップが1つづつ小さくなります。 ステップをトレースする解法が想定解らしいですが、集合で解く方が楽です(トレースしようとして失敗しました) #include <algorithm> #include <iostream> usin</iostream></algorithm>…

ジャンル毎にx冊売った時の合計金額を前計算しておく。 普通にナップサック問題を解けば、解けます。実際には可能かもしれませんが、1次元配列ではDPできませんでした。 #include <algorithm> #include <cstdio> #include <vector> #include <functional> using namespace std; vector<int> books[10]; ve</int></functional></vector></cstdio></algorithm>…

vector を使い、ソートします。 vector<pair<string,vector<int> > > data; map<string,int> sf; int main(){ string s; int a,k = 0; while(cin>>s>>a){ if(!sf.count(s)){ sf[s] = k++; data.push_back(make_pair(s,vector<int> ())); } data[sf[s]].second.push_back(a); } sort(data.begin(),data.</int></string,int></pair<string,vector<int>…

"嘘枝刈り"+DFS 適当に次数の小さいものを採用するようにしたら、何故か通りました。 #include <algorithm> #include <cstdio> #include <vector> using namespace std; int v[100]; vector<int> g[100]; inline int dfs(int x){ int ans = 0; for(int i = 0,l = g[x].size(); i < l; i++){ i</int></vector></cstdio></algorithm>…

動的計画法を使ってときました。問題の設定では1以上のものだけがZig-Zag数になるらしいですが、0以上にしても同じです。 const int mod = 10000; int M,len,dp[510][510][10][2][3]; /*dp[a][b][c][d][e] a:左からa桁目 b:剰余 c:一番右の数字 d:与えられた…

A. 成績が良い順にソートして、上からk番目のチームと同じ成績のチームがいくつあるかを答える問題。 struct team{ int s,t; team(int s,int t) : s(s), t(t){} }; bool operator < (const team& a, const team& b) { return a.s < b.s || a.s == b.s && a.t…

問題文略模範解答では、再帰を使って解くらしいです。 最初に積み上げて置き、右側からブロックを一旦取り去って、次の状態にすることを繰り返してみました。 vectorを使ってるので(更に、push_back()とpop_back()を多用している)速くはないです。 #include <cstdio></cstdio>…

一回記事消してしまったので、適当Easy 「一番遠くに行くとき」 ⇔ 「一番左か右に行くとき(大きい方)」 なので、右に沢山いくパターンと左に沢山パターンに分けて考えれば良い。したがって、?を全てLと解釈したときの答えと、?を全てRと解釈したときの答えの…