書き方わからないんですが、お試しで書いてみよう というお気持ちです
何故か全問書いた上にコードも載せてるので1個1個がめっちゃ短いです
解答例のコードはC++です
ABC170
A問題 Five Variables
問題概要
1 2 3 4 5
という5つの数のうち、1つを0にしたものが与えられる。
どれが0に変わったのか
解法1
5回数字を受け取るなかで0を受け取ったら何回目だったのかを出力
#include <bits/stdc++.h> using namespace std; int main() { for(int i = 1; i <= 5; ++i){ int x; cin >> x; if(x == 0){ cout << i << endl; } } return 0; }
解法2
15-(受け取った数の合計) が答え
解説放送でsnukeさんに教わりました
発想としては、元々数字を持っていて、言われた数字を返していく感じでしょうか
#include <bits/stdc++.h> using namespace std; int main() { int ans = 15; for(int i = 0; i < 5; ++i){ int x; cin >> x; ans -= x; } cout << ans << endl; return 0; }
まぁA問題なのでいくらでもやりようはありますが、だいたいこのどちらかを思いつくのではないのでしょうか
B問題 Crane and Turtle
問題概要
鶴亀算を解いてください
解法1
〝プログラミング〟コンテストなのでね
鶴と亀の数を全探索 合う数がなかったらNo
制約にだいぶ余裕があるので1000^2くらい回したら安心？
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) int main() { int X,Y; cin >> X >> Y; REP(i,1000)REP(j,1000){ if(i+j == X){ if(2*i + 4*j == Y){ cout << "Yes" << endl; return 0; } } } cout << "No" << endl; return 0; }
解法2
算数もしてみましょう
O(1)でかっこよく解きたいあなたに
鶴がa匹 亀がb匹 だとすると
X = a + b
Y = 2a + 4b
よって
a = (4X-Y)/2
b = (Y - 2X)/2
Y が 2X 以上 4X 以下の偶数であれば、これを満たす非負整数a,bが存在する
#include <bits/stdc++.h> using namespace std; int main(){ int X,Y; cin >> X >> Y; if(2*X<=Y && Y<=4*X && Y%2==0){ cout << "Yes" << endl; }else{ cout << "No" << endl; } return 0; }
コンテスト中ならちゃっちゃと全探索するのが吉
C問題 Forbidden List
問題概要
N個の数以外で、一番Xに近い数を探す
解法
その数が数列に含まれているかどうか という情報を表すbool型の配列を用意します
もしその数が含まれていなかったら(答えになりうるのなら)Xとの差分が現状より小さかったら更新していきます(コードを見たほうが速い)
答えの初期値をXにしておく 小さい数から調べていく などの方法で、エッジケースに対応しています
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } int main() { int X,N; cin >> X >> N; vector<bool> b(1000,true); REP(i,N){ int p; cin >> p; b.at(p) = false; } int del = 1000, ans = X; REP(i,1000){ if(!b.at(i))continue; if(chmin(del,abs(X-i))) ans = i; } cout << ans << endl; return 0; }
D問題 Not Divisible
問題概要
長さNの数列が与えられる
他のどの数でも割り切れないような数はいくつあるか
解法
同じ数が複数あった場合、その数はダメです それはmapで管理します
エラトステネスの篩の要領で、それぞれの数についてその数の倍数をはじくような操作をします
そのまま実装すると O(N*A) ?くらいになってTLEしてしまいます
小さいほうの数から、同じ数を再探索しないように工夫すると O(AlogA) ?くらいまで落とすことができます
ソートに O(NlogN) かかるので、結果的に O(NlogN + AlogA) で解くことができます
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) int main(){ int N; cin >> N; int Amax = 1e6; vector<int> A(N); vector<bool> P(Amax+1,true); //倍数テーブル map<int,int> mp; REP(i,N) cin >> A.at(i); sort(A.begin(),A.end()); //エラトステネス的なやつ REP(i,N){ mp[A.at(i)]++; if(mp[A.at(i)]>1) continue; if(!P.at(A.at(i))) continue; int t = 2; while(A.at(i)*t<=Amax){ P.at(A.at(i)*t) = false; ++t; } } int ans=0; REP(i,N){ if(mp[A.at(i)]>1)continue; if(P.at(A.at(i)))ans++; } cout << ans << endl; return 0; }
E問題 Smart Infants
問題概要
幼稚園がたくさんあって、それぞれの園で最強の園児を選出します
その最強園児たちのなかで一番弱い園児の強さを「平等さ」とします
転園を行うクエリが与えられるので、それぞれのクエリのあとの平等さを出力
解法
毎回一から計算しなおしていては間に合わないので、ピンポイントに更新していきます。
脳死でセグ木を生やしてもできる...のかな？
C++のmultisetを使って言われたまま実装してみます(ほかの言語にも似たようなものはあるのでしょうか)
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) int main() { int N,Q; cin >> N >> Q; vector<int> A(N), B(N); int num = 200200; vector<multiset<int>> vm(num); multiset<int> ms; REP(i,N){ cin >> A.at(i) >> B.at(i); vm.at(B.at(i)).insert(A.at(i)); } REP(i,num){ if(!vm.at(i).empty()) ms.insert(*(vm.at(i).rbegin())); } REP(q,Q){ int C,D; cin >> C >> D; C--; //Cが所属している園のトップを一旦外す ms.erase(ms.find(*vm.at(B.at(C)).rbegin())); //Cを園から外す vm.at(B.at(C)).erase(vm.at(B.at(C)).find(A.at(C))); //Cがいた園の新しいトップを入れなおす if(!vm.at(B.at(C)).empty()) ms.insert(*vm.at(B.at(C)).rbegin()); //CはD園へ B.at(C) = D; //D園のトップを一旦外す if(!vm.at(D).empty()) ms.erase(ms.find(*vm.at(D).rbegin())); //Cを園に入れる vm.at(D).insert(A.at(C)); //D園のトップを入れなおす ms.insert(*vm.at(D).rbegin()); printf("%d\n",*ms.begin()); } return 0; }
>追記 2020-11-15
セグメントツリーとpriority_queueを使って解くこともできました
各園ごとにpriority_queueにレートを入れる、出ていくときに、出ていった人のレートを入れる用のものも用意しておく
二つのpriority_queueのtopが一致したら、両方を削除する
とすると常に各園のtopがわかります
その結果をセグ木に乗せることで、multisetのeraseなどを行わずにクエリを処理していくことができました
コード
atcoder.jp
F問題 Pond Skater
問題概要
障害物のあるグリッドで、snukeさんは一回ごとに直線でKマスまで進めます
スタートからゴールまでの最短を求める(到達不可能なら-1)
解法
editorialにはダイクストラ法が載っていました
実装がだるそうです...
実は、普通にBFSで間に合います
愚直に実装すると O(HWK) みたいな気持ちになりますが、
(i, j) から (x, y) に移動した際、もし(x, y)にもっと早く到達する方法があったとしたらその方向にもっと進む必要はありません (その方向に(x, y)から直接移動することが上位互換になります)
よって、それぞれのマスへの遷移回数は高々4回になります(同じ方向からくることはなくなるので、上下左右から高々一回ずつ)
したがって、計算量は O(HW) となり、むしろeditorialより速いです
グリッドの初期値をINF, 障害物の場所を-1にして実装を楽にしました(なってるのか?)
#include <bits/stdc++.h> using namespace std; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) FOR(i,0,n) const int INF = INT_MAX/2; template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } using P = pair<int,int>; vector<int> dx = {1,0,-1,0,1,1,-1,-1}; vector<int> dy = {0,1,0,-1,1,-1,1,-1}; int main() { int H,W,K; cin >> H >> W >> K; P s,g; cin >> s.first >> s.second >> g.first >> g.second; s.first--;s.second--;g.first--;g.second--; vector<string> C(H); REP(i,H) cin >> C.at(i); vector<vector<int>> len(H,vector<int>(W,INF)); REP(i,H)REP(j,W){ if(C.at(i).at(j)=='@')len.at(i).at(j)=-1; } len.at(s.first).at(s.second) = 0; queue<P> qu; qu.emplace(s.first,s.second); while(!qu.empty()){ P now = qu.front();qu.pop(); int a = now.first, b = now.second; int lengh = len.at(a).at(b); REP(i,4){ for(int t = 1;t<=K;t++){ int x = a + dx.at(i)*t, y = b + dy.at(i)*t; if(x<0||H<=x||y<0||W<=y)break; if(len.at(x).at(y)>lengh){ if(chmin(len.at(x).at(y),lengh+1)) qu.emplace(x,y); }else{ break; } } } } int ans = len.at(g.first).at(g.second); if(ans==INF) ans=-1; cout << ans << endl; return 0; }
疲れていろいろ省いたので解説全然書いてない気がします
はてぶの記法も全然わかっていないので、気になる点などあったらください めっちゃ直します
