Atcoder Biginner Contest 183 (ABC183)振り返り
Atcoder Biginner Contest 183に参加しました。
atcoder.jp
A問題
A - ReLU
定義通りxが0以上と0未満とで場合分けする。
またはxと0の大きいほうを出力してもよい。
#include <bits/stdc++.h> using namespace std; int main() { int x; cin >> x; cout << max(x, 0) << endl; }
B問題
B - Billiards
壁や鏡で反射したり、川で水を汲んで運ぶ最短距離を求めたりするときには通る点の一方を壁に対して折り返す。
内分点の公式を用いれば求める座標が出る(公式解説の方法)。
本番では図の点A、B、Cが一直線上にあるような条件を求めた。この場合0除算に注意が必要なので公式解説のほうがスマート。後は適当な精度で出力。
#include <bits/stdc++.h> using namespace std; int main() { double Sx, Sy, Gx, Gy, ans; cin >> Sx >> Sy >> Gx >> Gy; if(Gy==Sy)ans=(Gx-Sx)/2+Sx; else ans=Sx-(Gx-Sx)/(-Gy-Sy)*Sy; cout << std::fixed << std::setprecision(15) << ans << endl; }
C問題
C - Travel
すべての都市の順列を考える。C++ならnext_permutation。
最近知ったばかりで一度も使ったため動くコードを書くのに30分かかった。反省。都市1から出発してすべての都市を回り、都市1に戻るまでの時間を足してKと比較する。
#include <bits/stdc++.h> using namespace std; int main() { int N, K; cin >> N >> K; vector<vector<int>>T(N, vector<int>(N)); for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ cin >> T.at(i).at(j); } } int ans=0; long long time=0; int now=0; vector<int>B(N); for(int i=0; i<N; i++)B[i]=i; for(int i=0; i<N-1; i++){ time+=T.at(B[i]).at(B[i+1]); } time+=T.at(B[N-1]).at(0); if(time==K)ans++; while(next_permutation(B.begin()+1, B.end())){ time=0; for(int i=0; i<N-1; i++){ time+=T.at(B[i]).at(B[i+1]); } time+=T.at(B[N-1]).at(0); if(time==K)ans++; } cout << ans << endl; }
D問題
D - Water Heater
0から200000秒までの各秒数における使用水量を求めようとするとTLEする(最大でO(NT)~O(4×10^10))。素直に実装するだけでは間に合わないときには(私の少ない経験上)適当な配列にメモしておくか適当な累積和を用意すればよい。今回は前者
#include <bits/stdc++.h> using namespace std; int main() { int N, W; cin >> N >> W; vector<int>S(N); vector<int>T(N); vector<int>P(N); for(int i=0; i<N; i++)cin >> S[i] >> T[i] >> P[i]; vector<long long>up(200010); vector<long long>down(200010); //少し大きめに用意する for(int i=0; i<N; i++){ up.at(S[i])+=P[i]; down.at(T[i])+=P[i]; } //各時間における使用増加量と減少量// string ans="Yes"; long long now=0; //問題の解答ans、ある時間での使用量nowを用意して for(int i=0; i<200010; i++){ now +=up.at(i); now-=down.at(i); if(now>W){ ans="No"; break; } } /*0から200000+α秒までの使用増加量と減少量を計算し続ける now>Wとなればans=Noとして終了*/ cout << ans << endl; }
E問題
E - Queen on Grid
単純に考える。あるマスに移動するにはそのマスの縦横斜め(上、左、左上方向)のマスから一手かかるので、それらのマスに移動する方法の和をとればよい。
しかし、すべてのマス(HW個)について縦横斜めの和(H+W+α)回計算しようとするとO(HW(H+W))~O(10^10)程度の計算量となるため当然TLE。適当な累積和をとれば計算量を抑えられそう。
実際に、あるマスまでの縦横斜めについての累積和を用意しておけばO(HW)で計算できる。
公式解説ではDP(動的計画法)で解いている。考え方は同じはず。たぶん。近々勉強したい。
#include <bits/stdc++.h> using namespace std; int main() { int H, W; cin >> H >> W; vector<vector<char>>S(H, vector<char>(W)); for(int i=0; i<H; i++){ for(int j=0; j<W; j++)cin >> S.at(i).at(j); } vector<vector<int>>A(H, vector<int>(W)); A.at(0).at(0)=1; //あるマスに到達する方法の数、(1,1)は1通り vector<vector<int>>tate(H, vector<int>(W)); vector<vector<int>>yoko(H, vector<int>(W)); vector<vector<int>>naname(H, vector<int>(W)); //縦横斜めについてあるマスでの累積和用の配列 for(int i=0; i<H; i++){ for(int j=0; j<W; j++){ //すべてのマスについて if(i>0){ A.at(i).at(j)+=tate.at(i-1).at(j); tate.at(i).at(j)+=tate.at(i-1).at(j); A.at(i).at(j)%=1000000007; } //そのマスの上方向の和をとり if(j>0){ A.at(i).at(j)+=yoko.at(i).at(j-1); yoko.at(i).at(j)+=yoko.at(i).at(j-1); A.at(i).at(j)%=1000000007; } //左方向の和をとり if(i>0&&j>0){ A.at(i).at(j)+=naname.at(i-1).at(j-1); naname.at(i).at(j)+=naname.at(i-1).at(j-1); A.at(i).at(j)%=1000000007; } //斜め方向の和をとった tate.at(i).at(j)+=A.at(i).at(j); yoko.at(i).at(j)+=A.at(i).at(j); naname.at(i).at(j)+=A.at(i).at(j); tate.at(i).at(j)%=1000000007; yoko.at(i).at(j)%=1000000007; naname.at(i).at(j)%=1000000007; //累積和をとり、常に余りの計算を入れる if(S.at(i).at(j)=='#'){ A.at(i).at(j)=0; tate.at(i).at(j)=0; yoko.at(i).at(j)=0; naname.at(i).at(j)=0; } //ブロックマスでは0として計算する } } cout << A.at(H-1).at(W-1) << endl; //右下(H,W)マスでの値が答え }
F問題
まるで分らない。
感想
BCでつまづいて時間がかかったのが反省点。最近は時間内にD問題まで解けるようになった。E問題の解法を終盤で思いついたが間に合わず、力不足を否定できない。次回失敗しなければ緑になれそうだがフラグか?