余談
PCの電源が立ち上がらず21:08から参戦。
unrated。
A - Full Moon
O(1)
N-M>=0であるか
(N-M)/P
で解答を求める事ができます。
C++
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
int N, M, P;
cin >> N >> M >> P;
int ans = 0;
if(N-M>=0) ans++;
N = max(0, N - M);
cout << max(0, ans + (N / P)) << endl;
return 0;
}
B - Overlapping sheets
O(NNN)
100×100×100=1000000
なので間に合いますね。
全探索をしましょう。
C++
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
bool graph[100][100];
int main() {
int N;
cin >> N;
rep(i, N){
int a, b, c, d;
cin >> a >> b >> c >> d;
for(int y=c; y<d; y++){
for(int x=a; x<b; x++){
graph[y][x] = true;
}
}
}
int ans=0;
for(int y=0; y<=100; y++){
for(int x=0; x<100; x++){
if(graph[y][x]) ans++;
}
}
cout << ans << endl;
return 0;
}
C - Blue Spring
O(N)
ソートと貪欲法
配列Fを大きい順に並べます。
D=2, P=10としたとき、
1145141919 ⇨ 9954411111
を並び替える。
上からD個の要素を取り出して判定する。
1, 54411111
9+9=18なのでPの値を換算する
2, 411111
5+4=9なので9の値を換算する
3, 1111
4+1=5なので5の値を換算する
と判定するとできますね。
C++
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
ll N, D, P;
cin >> N >> D >> P;
vector<ll> F(N);
rep(i, N) cin >> F[i];
sort(F.begin(), F.end());
reverse(F.begin(), F.end());
ll cnt = 0;
ll ans = 0;
while(cnt<N){
ll sum = 0;
rep(i, D){
if(cnt+i<N) sum += F[cnt+i];
}
if(sum>P) ans += P;
else ans += sum;
cnt += D;
}
cout << ans << endl;
return 0;
}
D - General Weighted Max Matching
2≤N≤16の制約を見てbitDPだと分かりますね。
この時点で離脱しようかなと考えました。
順位表を確認すると、２５分の経過で2500人が正解していました。
bitDPで２５００ACってまずないです。
順位表から別解答が存在する事がわかりました。
1 2 3 4
の地点があり、
1,2を組み合わせた後に3,4を組み合わせます。
1,3を組み合わせた後に2,4を組み合わせます。
1,4を組み合わせた後に2,3を組み合わせます。
N個の任意の地点に、この動かし方ができる方法はメモ化再帰ですね。
別解答が判明しました。
C++
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
ll N;
ll D[17][17];
ll ans=0;
bool used[17];
void dfs(ll p, ll sum){
if(p>=N){
ans = max(ans, sum);
return;
}
dfs(p+1, sum);
if(used[p]) return;
used[p] = true;
for(int i=p+1; i<=N; i++){
if(used[i]) continue;
used[i] = true;
dfs(p+1, sum + D[p][i]);
used[i] = false;
}
used[p] = false;
}
int main() {
cin >> N;
repx(i, 1, N+1){
repx(j, i+1, N+1){
cin >> D[i][j];
}
}
dfs(1, 0);
cout << ans << endl;
return 0;
}
E - Sandwiches
制約を見てDPっぽいです。
順位表を確認すると、60分の経過で2600人が正解していました。
複雑なDPで2600ACはないですね。
順位表から別解答が存在する事がわかりました。
13
9 7 11 7 3 8 1 13 11 11 11 6 13
のACする解答は20です。
7,11,7
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
13,11,13
13,11,13
13,11,13
13,6,13
規則性がありますね。
11という同じ数字がある場合は、
11の間の数字の数x(11の数-1)
の掛け算になっています。
もう少し詳しく見てみましょう。
13
9 7 11 7 3 8 1 13 11 6 11 11 13
とした時、
7,11,7
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,６,11
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,6,11
11,6,11
11,6,11
13,11,13
13,6,13
13,11,13
13,11,13
の24の解答になります。
規則性がありますね。
11,7,11
11,3,11
11,8,11
11,1,11
11,13,11
11,6,11
を計算式で求める事ができれば良さそうです。
最初の１１の要素のインデックスをi
次の１１の要素のインデックスをj
jが示す11はk個目の11である
配列のサイズをsize
として、
(j-i-1) * (size-k) * k
となりました。
コーディングをします。
C++
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }
int main() {
ll N;
cin >> N;
vector<ll> A(N);
rep(i, N) cin >> A[i];
map<ll, vector<ll>> mp;
rep(i, N){
mp[A[i]].push_back(i);
}
ll sum = 0;
for(auto m:mp){
ll size = m.second.size();
for(ll i = 1; i<size; i++){
sum += (m.second[i] - m.second[i-1] - 1) * (size-i) * i;
}
}
cout << sum << endl;
return 0;
}
余談
コンテスト中の順位表によって、
使用されるアルゴリズムが予測できるという話でした。