最大値の伝播で解くのは難しそうだったから、累積和で解きました。 少し枝刈りしましたが遅いです。 #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>…

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(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>…

再帰する式を作れれば解けます。右シフトすると一番小さいカップが消えてくれて、他のカップが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:与えられた…

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

ソート。INFから引いていけば簡単になります。 int main(){ int n,m; while(cin>>n>>m,n||m){ pair<int,int> p[100]; for(int i = 0; i < m; i++){ p[i].first = 2000; p[i].second = i+1;//INF = 2000 } for(int i = 0 ; i < n; i++){ for(int j = 0; j < m; j++){ i</int,int>…

最大値の伝播です。正方形型にメモリを確保してしまうと、半分くらい無駄になってMLEしてしまうので、三角形にします。(こんな感じに) (-1, 0) ( 0, 0) ( 0, 1) ( 1, 0) ( 1, 1) ( 1, 2) ( 2, 0) ( 2, 1) ( 2, 2) ( 2, 3) ...この図で、輪ゴムにかかる可能性…

出力に気をつけるのと、前計算するだけ。少しだけ短く書く場合は、 if(!(i%400) || i%100 && !(i%4)) leap[i]++; とする。 int leap[3000]; int main(){ for(int i = 1; i < 3000; i++){ if(i%400 == 0) leap[i] = 1; if(i%100 == 0) leap[i] -= 1; if(i%4 =…

入力してDPをします。上・下から真ん中までそれぞれ計算していって、上下の和が最大になるものを出力します。分からない場合は、まずは上半分だけについて考えてみましょう。(Project Euler に上半分だけの問題があったと思います。) int data[110][60],dp1[…

next_permutation()使って、DP。 重複して数えてるから、重複した回数((10-n)!回)で割ってあげる。本当は重複しないで数えたいところだが、これでもそんなに遅くないので妥協した。 int num[10]; long fact[10],dp[10][331];//和が331以上になることはない。…

できるだけ、実行時間を短くしてみようとしました。コードも少しだけ短めにしました。 偶数を除いて普通にエラトステネスの篩を使って、(素数+素数)を全部計算しただけですが、可読性のことは全く考えていません。ごめんなさい。あと、if文って結構時間が掛…

愚直に(10倍するだけで剰余を取らなかったり、double型を使ったりして)解こうとすると、精度が足りなかったり、オーバーフローするから、10倍しながら関係無い部分(整数部)を捨てていく。 int main(){ int a,b,n; while(cin>>a>>b>>n){ int ans = 0; a %= b;…

適当にコードを短くしましょう。数字の並べ方：4!通り 演算子のつけ方：3(種類) ^ 3(場所) 通り 括弧のつけ方：5(4)通りで全部で9720(7776)通りなので、無駄が多いけど一瞬です。書くのは一瞬ではないですが、これで妥協しました。括弧のつけ方を1通り見落と…

Problem 3: 時空のスゴロク・ロード全てのマスに対して、暫定の最短距離を求めるのを繰り返した。蟻本でこんな感じのアルゴリズムを見た記憶がある。たどり着く場所と、そこへの最短距離だけ分かればいい気がするけど、これでも通った。 int p[100000],d[100…

つらら汚いです。 やるだけで、実装が(自分にとっては)難しい問題だと思ったけど、考える問題らしい。余裕があるときに解きなおしたい。 long使う必要なかったかも。面倒臭いから全部longにしちゃったけど。 long n,l,ice[100002],ict[100002],icf[100002],i…

やるだけ。入力の順番(ID)を覚えるだけ using namespace std; typedef long long ll; ll em[4000]; int flag[4000]; int main(){ int n; while(true){ int id,p,q; cin >> n; if(!n) return 0; for(int i = 0; i < n; i++){ cin>>id>>p>>q; em[id-1] += (ll)…

解けてないです1 == a^n mod m (^はXORじゃないほう)となる最小のnを求める問題だと思う。 このコードを提出してみたら、遅すぎって怒られた。1.18秒から0.18秒減らさないといけない。 *1もしかすると最小公倍数をもっと効率良く求められるのかもしれない。 …