ダメ。 1707->1661(-46)。
A. Joysticks
問題概要
2 つのジョイスティックと 1 つの充電器がある. それぞれのジョイスティックは充電器に接続されているとき, 1 分ごとに 1 % 充電され, 接続されていないとき, 1 分ごとに 2 % 放電する.
今, 2 つのジョイスティックは %,
% 充電されている. 充電器は, 各分の開始時に差し替えることができる. 両方のジィスティックが 1 %以上となる最大の時間を求めよ.
解法
なんか普通に書いたら pretest で落ちたのでよく分からない.
あまりにも分からないので DP を書いたらまた落ちた.
どうも, = 1 %,
= 1 % のときがコーナーケースらしい.このとき 1 ターンも行われずに終了する.
これだけ考慮していれば, 各分で貪欲に充電が小さい方を用いれば最大となる. 1 時間を溶かす.
ソース
#include<bits/stdc++.h> using namespace std; int v[300][300]; int rec(int x, int y) { if(x <= 0 || y <= 0) return(0); if(~v[x][y]) return(v[x][y]); return(v[x][y] = max(rec(x + 1, y - 2), rec(x - 2, y + 1)) + 1); } int main() { int X, Y; cin >> X >> Y; memset(v, -1, sizeof(v)); if(X == 1 && Y == 1) cout << 0 << endl; else cout << rec(X, Y) << endl; }
B. Beautiful Paintings
問題概要
数列 a がある. 任意の順に並べ替えて, が現れる数を最大化せよ.
解法
よくありそうな問題. 基本的には昇順が良いのは自明.
但し昇順にして, となるものは, 使っても意味がないので後で使う.
ソース
#include<bits/stdc++.h> using namespace std; int main() { int N, A[1000]; cin >> N; multiset< int > vv; for(int i = 0; i < N; i++) { int K; cin >> K; vv.insert(K); } int ret = 0, now = *vv.begin(); vv.erase(vv.begin()); while(!vv.empty()) { bool f = false; for(auto v : vv) { if(now < v) { now = v; vv.erase(vv.find(v)); ++ret; f = true; break; } } if(!f) { now = *vv.begin(); vv.erase(vv.begin()); } } cout << ret << endl; }
C. Watchmen
問題概要
二次元平面上に, N 個の整数座標の点がある. 但し, 点の位置は重複することがある. マンハッタン距離とユークリッド距離が等しくなるような点の組み合わせの個数を求めよ.
解法
x 軸か y 軸どちらかが同じであれば, マンハッタン距離とユークリッド距離は等しくなり, 逆にそれ以外は等しくならない.
なので, 軸別に現れた回数を数える.
重複する点があるので, その個数も数えておいて, あとから引く.
ソース
#include<bits/stdc++.h> using namespace std; int main() { int N; cin >> N; map< int, long long > row, col; map< pair< int, int >, long long > sss; for(int i = 0; i < N; i++) { int x, y; cin >> x >> y; row[x]++; col[y]++; sss[{x, y}]++; } long long ret = 0; for(auto v : row) { ret += 1LL * v.second * (v.second - 1) / 2; } for(auto v: col) { ret += 1LL * v.second * (v.second - 1) / 2; } for(auto v: sss) { ret -= 1LL * v.second * (v.second - 1) / 2; } cout << ret << endl; }
D. Image Preview
問題概要
スマホの中に写真が N(1 ≦ N ≦ 5 × 10^5) 枚ある. 1 番目の写真が現在表示されている.
a 秒かけて, 左フリップか右フリップをすることができる. フリップすると隣接した写真が表示される(但し 1 枚目の左隣は N 枚目, N 枚目の右隣は 1 枚目とする).
初めて表示される写真なら必ず, 1 秒かけて見る. 二度目以降は見ずにスキップ出来る.
また, それぞれの写真は, 縦向きか横向きである. 横向きの写真は見る前に b 秒かけて, 写真を回転しなければならない(二度目以降は不要).
T 秒の間に見れる写真の最大数を求めよ.
解法
ちょっと問題を整理.
1) 縦向きの写真は 1 秒, 横向きの写真は (b + 1) 秒かかる.
2) 左右に何度も往復することは無駄. 最大で 1 回.
3) 2) より, フリップする順番は, ←のみ(以降←), →のみ(以降→), ←をやって→(以降←→), →をやって←(以降→←)
←, ←→はなんか尺取りできそう. まずできる限り←. そして, 1 個ずつ → の回数を増やしていくことを考える. → を 1 個増やせば, ← の回数はちょっと減る(これは広義単調減少). よってやっぱり尺取りできる. →, →←も同じっぽいけど, 実装が面倒. 写真の左右を入れ替えることで ←, ←→と同様の問題となる.
円環や尺取りが闇で無限にバグって, 5 WA してた. 結局, pretest 残り 2 分位で通って熱かったけど, これが TLE で落ちてダメ. if(ret >= N) return(N); をどうせいつか終わるだろうと, while 抜けてからやってた. T ≦ 10^9 だからダメだよね. もうちょっと詰めをしっかりやります.
ソース
#include<bits/stdc++.h> using namespace std; #define int long long int N, A, B, T; string S; long long Solve() { int Cost[500000] = {}; for(int i = 0; i < S.size(); i++) { if(S[i] == 'w') Cost[i] = B + 1; else Cost[i] = 1; } if(T - Cost[0] < 0) { return(0); } T -= Cost[0]; int RightIdx = 0, ret = 1; #define Prev(k) (k - 1 + S.size()) % S.size() #define Next(k) (k + 1) % S.size() int best = ret; while(T - A - Cost[Prev(RightIdx)] >= 0) { RightIdx = Prev(RightIdx); T -= A + Cost[RightIdx]; ++ret; if(ret >= N) return(N); } best = max(best, ret); for(int i = 1; i < N; i++) { while(RightIdx != 0 && T - Cost[i] - (N - RightIdx + 1) * A < 0) { T += A + Cost[RightIdx]; RightIdx = Next(RightIdx); --ret; } if(T - Cost[i] - (N - RightIdx + 1) * A < 0) break; T -= A; T -= Cost[i]; ++ret; best = max(best, ret); } return(best); } signed main() { cin >> N >> A >> B >> T; int Buffer = T; cin >> S; int res = Solve(); T = Buffer; reverse(S.begin() + 1, S.end()); cout << max(res, Solve()) << endl; }
