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

久々にpracticeしました。Easy 229.95/250 正の整数が沢山あって、X+YとX-Yが含まれている。X*Yの最大値を求めよ。全探索で良い。AとB(A>B)の偶奇が一致するとき、整数X,Yは存在して、X=(A+B)/2,Y=(A-B)/2となる。 加法定理を逆向きに使うときにこんな感じの…

ソート。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>…

Easy 子音が6個で母音が2個で、母音が両方とも同じであれば"YES"でそうじゃなければ"NO"を出力する。 数えるだけ class KingXNewBaby{ public: string isValid(string s) { int len = s.size(); if(len!=8) return "NO"; int a = 0; for(int i = 0; i < len;…

A. Friends or Not 古い情報を上書きして行けば解けそうだけど、何故か解けない。B. Matchmaker yとbが同じになるところだけ考えれば良いです。一応コード載せておくけど、説明できない… int y[1001],b[1001],yx[1001][1001]; vector<int> ba[1001]; int main(){ </int>…

いつもより、読解が大変だった。あと、easyで中括弧忘れに気づくのに時間が掛かり過ぎたりしてたから、気を付けなければならないEasy 与えられた方程式にx=0,1を代入して、f(x)が偶数になるxの個数を求めます。 x=0の場合は、a[0]のみを考えればよく、x=1の…

A.Next Round 問題文読めてないけど、通ってた。 k番目の値以上で且つ0じゃないものの個数を出力する。数字が減っていくが、無視して普通に数えても良い。 int n,k,t,p[51],res; int main(){ cin>>n>>k; for(int i = 0; i < n; i++){ cin>>p[i]; if(i == k-1…

Easy 連立方程式を解く問題。 解が存在すると仮定して、それが整数になるかを判定するだけの人がまあまあいました。どう解いても、検算すればだいたい大丈夫だから、検算しましょう。 私は検算してませんが、challengeしてくる方は流石に居ませんでした。 cl…

A.Average "Yes","No"を"YES","NO"と書くと全部WAになる。 #include <iostream> #include <algorithm> using namespace std; int n,s,m; int main(){ for(int i = 0; i < 4; i++){ cin>>n; m = max(m,n); s += n; } s += m; if(s>=300)cout<<"Yes"<</algorithm></iostream>

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