Codeforces Round #464 (Div. 2)
休みのうちはいいけど大学始まってからはどれくらいのペースでできるのだろうか.
A - Love Triangle
配列の中身を添え字にするのを3回繰り返して元に戻れば"Yes".
#include <bits/stdc++.h> using namespace std; int main(void) { int n; cin >> n; int f[n + 1]; for(int i = 1; i <= n; i++) { cin >> f[i]; } for(int i = 1; i <= n; i++) { if(i == f[f[f[i]]]) { cout << "YES" << endl; return 0; } } cout << "NO" << endl; }
B - Hamster Farm
余りが最小になる箱の種類を求めればよい.
#include <bits/stdc++.h> using namespace std; int main(void) { long long n; int k; cin >> n >> k; long long a[k + 1]; for(int i = 1; i <= k; i++) { cin >> a[i]; } long long min = n; int ans = 0; for(int i = 1; i <= k; i++) { if(min >= n % a[i]) { min = n % a[i]; ans = i; } } cout << ans << " " << (long long)n / a[ans] << endl; }
C - Convenient For Everybody
#include <bits/stdc++.h> using namespace std; int main(void) { int n; cin >> n; int a[n]; for(int i = 0; i < n; i++) { cin >> a[i]; } int s, f; cin >> s >> f; int mx = 0; int ans = 1; // 先頭のタイムゾーンがi時 for(int i = 1; i <= n; i++) { int people = 0; // 全タイムゾーンの参加できる人数を求める for(int j = 0; j < n; j++) { int localstart = i + j; if(localstart > n) { localstart -= n; } int localfinish = localstart + 1; if(localfinish > n) { localfinish -= n; } // cout << "localstart: " << localstart << " " << "localfinish: " << localfinish << endl; if(s <= localstart && localfinish <= f && localstart < localfinish) { people += a[j]; } } // cout << "i: " << i << " " << "people: " << people << endl; if(mx < people) { mx = people; ans = i; } } cout << ans << endl; }
最初は上記のような全探索を書いたがWAだしO(n^2).
テストケースを試すうちに区間で区切った人数を足せばよいことに気づいたけど時間切れ.
Editorialが出てないっぽい(2018/02/20現在)けどタグにbinary_searchとあるので想定解はO(nlogn)とか?
らてさんの提出を解答代わりに読んだ.
http://codeforces.com/contest/939/submission/35403238
f - sの幅で人数を足した時の最大の場合が答え.
n番目のタイムゾーンと1番目のタイムゾーンをまたいだ場合も考えることに注意(上はこれでWAしている).