第二回全国統一プログラミング王決定戦予選
結果
問題 | ACまでに要した時間 | AC | WA | TLE |
---|---|---|---|---|
A | 12:23 | 1 | 0 | 0 |
B | - | 0 | 0 | 0 |
C | - | 0 | 0 | 0 |
D | - | 0 | 0 | 0 |
Rating | 順位 |
---|---|
486 (-30) | 2961 |
コメント
- 一問目もっと早く出すだけでもっと順位上げられたんじゃなかろうか..
- 最初naiveに二重ループで解こうとしたが,ワークロード見たら明らかにTLEするのでメモ化に変更した.そこに時間を取られた感..かなり無駄なことをした
- 解説PDF見るとループすら使わずに厳密解を求めているが,重複を許すのであれば
n-1
パターンの式が考えられるのだから,重複を排除するために2で割るというのは至極当然である(なぜこういう簡単なことに気づかないのか..) - レートが順調に下がっているのだが,今の環境だともしかして茶色ですらなく灰色適正である可能性すらある.スプラトゥーン2のようにレートが下がっていくのは中々に辛いが,自分の努力だけで上げられる点ではかなり楽っちゃ楽である
以下,後日解き直したレポート(A,Bのみ)
A
コンテスト参加時はかなり頭の悪い で解いているが,偶数と奇数に場合分けして解けば で解ける.
#include <bits/stdc++.h> #define REP(i, x) REPI(i, 0, x) #define REPI(i, a, b) for (int i = int(a); i < int(b); ++i) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; if (N % 2 == 0) { cout << (N - 1) / 2 << endl; } else { cout << N / 2 << endl; } return 0; }
B
「無向グラフが構成できる」条件は以下の通りである
- グラフの頂点が唯一一個存在する
- 各距離に対してとなる別のがどのに対しても存在する
あとはこの条件を満たすかどうかをチェックしながら存在しえるパターンのグラフを数え上げればよい. なんどかWA踏んだが,「頂点は1個だけ」という条件を忘れていたのと,オーバーフロー防止の除算の仕方を間違ってオーバーフローして0になっていたという間抜けなミスであった.
#include <iostream> int main() { int MOD = 1000000007; int a = 11111; int b = 123456; long long c = 987654; long long d = c; c *= a * b % MOD; d = d * a * b % MOD; std::cout << c << std::endl; std::cout << d << std::endl; return 0; }
上記のコードを実行すると以下のように結果が異なる.
367130358707286 356137376
一度代入演算子を使って実装してしまい,% MODされていない結果が累積されてオーバーフローが発生した.今後気をつけたい.
#include <bits/stdc++.h> #define REP(i, x) REPI(i, 0, x) #define REPI(i, a, b) for (int i = int(a); i < int(b); ++i) #define ALL(x) (x).begin(), (x).end() typedef long long ll; using namespace std; int const BASE = 998244353; ll f(int n, int m) { ll ans = 1; REP(i, m) { ans = ans * n % BASE; } return ans; } int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector<int> D(N); REP(i, N) { cin >> D[i]; } if (D[0] != 0) { cout << 0 << endl; return 0; } sort(D.begin(), D.end()); ll ans = 1; int parent_count = 1; int children_count = 1; REPI(i, 0, N - 1) { if (D[i] == 0 && i > 0) { cout << 0 << endl; return 0; } if (D[i] != D[i + 1]) { if (D[i + 1] != D[i] + 1) { cout << 0 << endl; return 0; } else { ans = ans * f(parent_count, children_count) % BASE; parent_count = children_count; } children_count = 1; } else { ++children_count; } } ans = ans * f(parent_count, children_count) % BASE; cout << ans % BASE << endl; return 0; }