4完0WAで4位でした
- ジョギングの疲れがとれない
- (体力が足りないといわれて毎日10km走ってるけどこれは逆効果だ)
- 疲れがとれなくて眠み生えてる
- 13:45
- 問題が先行公開されてたので開く
- 1問目だけ先に解いてしまおう
- 問題文を読む
- 面倒くさそう
- 読解力がない(1回目)
- やめたい
- 線上に点がなかったらなんかやればよさそう
- 10分くらいだっけな、もうひとつでFAとれたみたい(1問目AC)
int main(){ int N; cin >> N; for(int i = 0; i < N; i++){ int r, t; cin >> r >> t; int shift = (t / 30) * 5; //スタートの番号 int pos = r / 100; //場所 bool flag = (t % 30 == 0); //線状か vector< int > ret; ret.push_back(shift + pos); if(r % 100 != 0) ret.push_back(shift + pos + 1); if(!flag) ret.push_back(shift + pos + 5); if(!flag && r % 100 != 0) ret.push_back(shift + pos + 6); for(int j = 0; j < ret.size(); j++){ cout << (j == 0 ? "" : " ") << ret[j]; } cout << endl; } }- 予選の反省があるから問題にざっと目を通す
- 6問目と8問目は解けそう感
- まあいいや2問目
- やろうとする
- 誤読に気づく
- やろうとする
- 方針が違うことに気づく
- やろうとする
- まだ方針違うみたい
- 読解力がない(2回目)
- 文字列の長さの合計がどれくらいになるか求めようとする
- わかんない
- まあいいか
- なぜか我が校のサーバーが逝き始める
- これ顧問が会津いってるからだ
- 顧問がいないのをいいことに誰かが外部から攻撃してる説
- これはPCKのライバルからの陰謀だと確信
- さらに端末の動作が鈍くなってついには動かなくなった
- これは発狂不可避
- サーバーの再起動やらなにやらを繰り返す
- マジで誰だよ
- まともに問題読めないしコーディングができない
- ローカルのパソコンでやろう
- 端末が動かない間に色々整理できたし結果的にはよかったのかもしれない
- 2問目適当にバックトラックしてサンプル通って提出
- やったねAC(2問目AC)
int w; void rec(int sum, int idx, string emacs){ if(abs(sum) > w || pow( 3.0, idx - 2) > w){ return; } if(sum == w){ //できたー cout << emacs << endl; exit(0); } else { //できてないー rec( sum + (int)pow( 3.0, idx), idx + 1, "+" + emacs); rec( sum - (int)pow( 3.0, idx), idx + 1, "-" + emacs); rec( sum, idx + 1, "0" + emacs); } } int main() { cin >> w; rec( 0, 0, ""); }- あのプログラムオーダーどれくらいだろ
- 無駄な再帰を明確にしてるから、O(logn)より結構大きいくらい
- 変数名でvim勢を煽っていくスタイル(小声
- 提出状況を確認したら3問目複数提出あるけど0ACな模様
- 予選の5問目枠を確信
- 触れないことにしよう
- 次何解こう
- 6問目は僕の頭でも理解できる問題文っぽい
- O(n^4)の二次元累積和がぱっと見、浮かぶけどTLEだろうな
- 多少バグらせながらも解く
- WA(絶望)
- やっぱバグらせていた
- すぐ察して提出
- TLE(妥当)
int main() { int N, mas[302][302] = {{}}; cin >> N; for(int i = 1 ; i <= N ; i++ ){ for(int j = 1 ; j <= N ; j++ ){ cin >> mas[i][j]; mas[i][j] += mas[i-1][j] + mas[i][j-1] - mas[i-1][j-1]; } } int ret = -INF; for(int i = 1 ; i <= N ; i++ ){ for(int j = 1 ; j <= N ; j++ ){ for(int k = 1 ; k <= i ; k++ ){ for(int l = 1 ; l <= j ; l++ ){ int all = mas[i][j] - mas[k-1][j] - mas[i][l-1] + mas[k-1][l-1]; int blank = 0; if(abs(i - k) >= 2 && abs(j - l) >= 2){ blank += mas[i - 1][j - 1] - mas[k][j - 1] - mas[i - 1][l] + mas[k][l]; } ret = max( ret, all - blank); } } } } cout << ret << endl; }- こんなもので通る訳がない(自明
- きっとDPとかしてO(n^4)をO(n^3)にするんだろう(考察
- あーーー
- んーーー
- ・・・・・・
- あたまついてない
- INF個くらい必要そう
- これは敗北
- この辺から焦りはじめる
- 4問目のAC率が高そう、8問目がreal本選erに結構解かれている
- 8問目読む
- なんか2008年くらいのPCKにこんな問題あったけどにぶたんで解いたっけ
- 重さの要素が加わっただけだ
- とりあえず本を入れる位置を全探で決めてどれくらい入るかは貪欲で求める
- なぜかバグらせなかった
- にぶたんはこのときかかなかった
- 提出
- TLE
- 貪欲で求める部分をにぶたんに書き換える
- 多少バグらせたけどできた
- ACを確信
- TLE(困惑)
- やめた
- 4問目を読む
- 問題文ながぽよ
- 読解力がない(3回目)
- あーー
- なんでデッドロックでグラフを作れるんだろう
- そんなことはどうでもいいらしい
- 閉路検出してデッドロックが発生するか判定せよ的な感じの問題文になった
- 解法書いてあるじゃん
- 本当にそのままなのかな
- 適当にグラフ作って閉路検出しようとする
- 閉路検出のスキルが自分にはないことに気づく
- どうやるんだろう
- グラフ世界一扱えない
- こころが沈んできた
- 強連結成分分解でできる説
- 実装やだ
- DFSで試すだけでしょ
- すべての場合についてデッドロックが発生する
- 私の頭がデッドロックしそうとかよくわかんないことを考え始める
- 辺にも使用済かの情報が必要なのか
- あーこれ巡ったら頂点を使って内容に戻すべきだな
- なんかできてる
- つ計算量
- 大丈夫だろ、提出
- うっしゃ(4問目AC)
typedef vector< vector< Pi > > Graph; Graph g; int V; bool used[300]; int dfs(int idx){ if(used[idx]) return true; used[idx] = true; for(int i = 0; i < g[idx].size(); i++){ if(g[idx][i].second == 0){ g[idx][i].second = true; if(dfs(g[idx][i].first)) return true; } } used[idx] = false; return false; } int main() { cin >> V; g.resize(200); for(int i = 0; i < V; i++){ int u, d; string s; cin >> u >> s >> d; u--, d--; if(s == "lock"){ g[d + 100].push_back(Pi(u, false)); } else { g[u].push_back(Pi( d + 100, false)); } } for(int i = 0; i < 100; i++){ if(!used[i] && dfs(i)){ cout << 1 << endl; return(0); } } cout << 0 << endl; return(0); }- こころぴょんぴょんしてきた
- 3問目を読んでみる
- 読解力がない(N回目)
- なんかややこしい
- 問題文を誤読していることに複数回気づく
- 読解力がない(INF回目)
- シミュレーションやるだけ説
- まあ書く
- かけたと思ったらサンプル合わない
- 誤差る
- 問題文の誤読に気づく
- 読解力がない(∞回目)
- なおす
- でない
- 問題文の誤読に気づく
- 多分この問題誤読の回数の最大値を得れた気がする
- 誤読なくした
- ソース直した
- でた
- 提出
- うぇい(3問目AC)
typedef vector< vector< Pi > > Graph; int main(){ int N, R, T, p[100]; cin >> N >> R >> T; for(int i = 0; i < N; i++){ cin >> p[i]; } int stap[1001] = {}; int pos[100] = {}; int ret = 0; bool first = false; for(int i = 1; i <= T; i++){ for(int j = 0; j < N; j++){ pos[j] = (pos[j] + p[j]) % R; } for(int k = 0; k < N; k++){ if(stap[pos[k]] > 0){ stap[pos[k]]--; } else { ret++; } } if(first++){ for(int k = 0; k < N; k++){ stap[pos[k]]++; } } } cout << ret << endl; }- こんな簡単なシミュレーションで通るのにあの正答率は何(煽り
- 再び1位に浮上したらしい
- あと1時間30分くらいある
- 5問目を軽く読む
- 圧倒的木DP感
- 木DP書いたことない
- 書けそうもない
- 8問目再び
- 計算量O(2 ^ n log m)くらいだよな
- (後記: 実は大嘘 O(m・2^n log m)っぽい(やばい))
- メモ化した
- ACを確信
- TLE(困惑
- 気になるところを変えてn回出してみるもTLE×n回
- 高速化の余地なし
- これもうわかんねえな
- TLE(引退)
- たくさんTLE生える
- 方針は合ってそうだけどなんでだろ
- つらみがたくさん生える
- 8回目TLE
- やめた
- つかれた
- 4位だ
- 5問目解こうとするけど正直解いても順位変わんない
- 時間がない
- 本選行きたかったなあ
- 終了
5問目 木DPっぽい
int N;
vector< string > node;
vector< vector< int > > edges;
int dp[1000];
int rec(int idx){
if(dp[idx]) return dp[idx];
if(edges[idx].empty()) return(1 + (node[idx] == "E?"));
int64 ret = 0;
// 選択ノード //
if(node[idx][0] == 'R'){ /* OR */
for(int i = 1; i < (1 << edges[idx].size()); i++){
int64 ret1 = 1;
for(int j = 0; j < edges[idx].size(); j++){
if((i >> j) & 1){
(ret1 *= rec(edges[idx][j])) %= 1000000007;
}
}
ret += ret1;
}
if(node[idx] == "R?") ret++;
} else if(node[idx][0] == 'A'){ /* ALT */
for(int i = 0; i < edges[idx].size(); i++){
(ret += rec(edges[idx][i])) %= 1000000007;
}
if(node[idx] == "A?") ret++;
} else { // 物質ノード //
ret = 1;
for(int i = 0; i < edges[idx].size(); i++){
(ret *= rec(edges[idx][i])) %= 1000000007;
}
if(node[idx] == "E?") ret++;
}
return(dp[idx] = ret % 1000000007);
}
int main(){
cin >> N;
node.resize(N);
edges.resize(N);
for(int i = 0; i < N; i++){
cin >> node[i];
}
for(int i = 0; i < N - 1; i++){
int a, b;
cin >> a >> b;
a--, b--;
edges[a].push_back(b);
}
cout << rec(0) << endl;
}
8問目 メモ化じゃ解けないやこれ。DPしてにぶたんするだけ途中でint64生えてるのとかにぶたんがちょっとおかしかったりするのは頭悪いデバッグのおかげ
typedef long long int64;
int64 M, N;
int64 w[200004], t[200004];
int64 c[15], b[15];
int64 dp[1 << 15];
int64 get_sum_w(int64 a, int64 b){ // [a,b]
if(a == 0) return w[b];
return(w[b] - w[a - 1]);
}
int64 get_sum_t(int64 a, int64 b){
if(a == 0) return t[b];
return(t[b] - t[a - 1]);
}
int64 get_donyoku(int64 idx, int64 dan){
int64 max_weight = c[dan], max_width = b[dan];
int64 pos = INF;
int64 row = idx, high = M;
while(row + 1 < high){
int64 mid = (row + high) / 2;
if(get_sum_w( idx, mid) <= max_weight) {
row = mid + 1;
} else {
high = mid;
}
}
if(get_sum_w( idx, row) > max_weight) pos = min( pos, row);
else if(get_sum_w( idx, row + 1) > max_weight) pos = min( pos, row + 1);
else if(get_sum_w( idx, row + 2) > max_weight) pos = min( pos, row + 1);
row = idx, high = M;
while(row + 1 < high){
int64 mid = (row + high) / 2;
if(get_sum_t( idx, mid) > max_width) {
high = mid;
} else {
row = mid + 1;
}
}
if(get_sum_t( idx, row) > max_width) pos = min( pos, row);
else if(get_sum_t( idx, row + 1) > max_width) pos = min( pos, row + 1);
else if(get_sum_t( idx, row + 2) > max_width) pos = min( pos, row + 1);
if(pos == INF) return idx;
return pos;
}
int main(){
scanf("%d %d", &M, &N);
w[M] = INF, t[M] = INF;
w[M + 1] = INF, t[M + 1] = INF;
for(int i = 0; i < M; i++){
scanf("%d %d", &w[i], &t[i]);
if(i != 0){
w[i] += w[i - 1];
t[i] += t[i - 1];
}
}
for(int i = 0; i < N; i++){
scanf("%d %d", &c[i], &b[i]);
}
fill_n( dp, 1 << 15, -1);
dp[0] = 0;
for(int i = 0; i < (1 << 15); i++){
if(dp[i] == -1) continue;
for(int j = 0; j < N; j++){
if(!((i >> j) & 1)){
dp[i|(1 << j)] = max( dp[i|(1 << j)], get_donyoku(dp[i], j));
}
}
}
cout << *max_element( dp, dp + (1 << 15)) << endl;
}
次はJOIだJOI頑張りましょ
