5完＋部分点20でした
追記:予選通過,本戦出場者各位よろしくね
- 団体受験なので、家を出て学校の部室へ向かう
- 無事学校に到着
- 僕のバッグが廊下の壁に掲示してあるポスターを2分して、1つは「落ち」る。
- 予選「落ち」というフラグを回収したかと絶望
- 実はこれは、二分探索あるいは半分全列挙だったことを疑う
- 知らない
- だいぶ緊張している
- 10分前くらいだったけど、よくわからない格ゲーを友達とやる
- 2連敗
- 1時間で3完してればいいか位の目処をたてる
- はじまった
- とりあえず1分くらいで6問分流し読み
- 4問目簡単そう、文字なマップ系が2問あって強そうくらいな感想を得る
- 1問目むずかしい
- 冒頭の通り緊張のせいで精神状態がよくなくて、うまくソースを書けない
- 思いついたことをそもままアウトプットしたソースがこちら
#include<bits/stdc++.h> using namespace std; template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; } template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; } template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; } template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; } #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++) #define ALL(v) (v).begin(), (v).end() #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());} #define fr first #define sc second typedef pair< int , int > Pi; typedef pair< int , Pi > Pii; typedef long long int64; const int INF = 1 << 30; int main(){ int A, B, C, D, P; cin >> A; cin >> B; cin >> C; cin >> D; cin >> P; int ret = 0; if(P <= C) ret = B; else{ ret = B; ret += D * (P - C); } cout << min( A * P, ret) << endl; }- 世界一汚いソースコード
- まあこんな問題でバグるはずがないということで、提出(13:05)
- 2問目
- 問題分がわかりにくそう
- 読解力のない僕を駆逐しようとしている感
- JOIくんがゲームを支配しているプロだと感じながら、適当に書く
- サンプル通った
- テンプレートに感謝、入出力が楽
- これもバグるはずがないだろうということで、提出(13:15)
#include<bits/stdc++.h> using namespace std; template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; } template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; } template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; } template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; } #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++) #define ALL(v) (v).begin(), (v).end() #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());} #define fr first #define sc second typedef pair< int , int > Pi; typedef pair< int , Pi > Pii; typedef long long int64; const int INF = 1 << 30; int main(){ int N, M; cin >> N; cin >> M; vector< int > A(M); cin >> A; vector< vector< int > > B( M, vector< int >(N)); cin >> B; vector< int > Point( N, 0); for(int i = 0; i < M; i++){ int hazure = 0; for(int j = 0; j < N; j++){ if(A[i] == B[i][j]){ Point[j]++; } else { hazure++; } } Point[A[i] - 1] += hazure; } cout << Point; }- 3問目
- 書いてみるととても簡単
- 極めてやるだけ
- 考えないといけない系を想定していたけどこれは驚いた
- 書けた
- 謎の値が出力される
- 配列外参照に違いないと疑うも、配列外参照する要素がない
- ここからintがいけない、long longだ！とかいう謎のデバッグを始める
- 出力するとおかしくなってる気がするしこれはコンパイラが悪い
- 変数の中身を丁寧に扱おうとする(以下ソースのgetの部分だね)
- 何故かおかしくなくなった
- gccからのハラスメント
- 別におかしくなさそうなので提出(13:30)
#include<bits/stdc++.h> using namespace std; template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; } template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; } template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; } template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; } #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++) #define ALL(v) (v).begin(), (v).end() #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());} #define fr first #define sc second typedef pair< int , int > Pi; typedef pair< int , Pi > Pii; typedef long long int64; const int INF = 1 << 28; int main(){ int H, W; string mas[100]; int num[150][150]; cin >> H >> W; for(int i = 0; i < H; i++){ cin >> mas[i]; } for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ num[i][j] = INF; } } for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ if(mas[i][j] == 'c') num[i][j] = 0; } } for(int i = 0; i < H; i++){ for(int j = 1; j < W; j++){ num[i][j] = min( num[i][j], num[i][j - 1] + 1); } } for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ if(j != 0) cout << " "; int get = num[i][j]; if(get == INF) cout << -1; else cout << get; } cout << endl; } }- 流れが悪いながらも4問目
- 何も考えずにDP書けそう
- 実際にも書けた
- 多分この問題のみが一発で書けたソースだと思う
- 去年のbitDPとかなんだったんだろう
- とか盛大にJOIを批評しつつも提出(13:47)
#include<bits/stdc++.h> using namespace std; template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; } template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; } template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; } template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; } #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++) #define ALL(v) (v).begin(), (v).end() #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());} #define fr first #define sc second typedef pair< int , int > Pi; typedef pair< int , Pi > Pii; typedef long long int64; const int64 INF = 1LL << 58; int main(){ int64 N, M; cin >> N >> M; vector< int64 > D(N); cin >> D; vector< int64 > C(M); cin >> C; // dp[i][j]: i日目に街jにいるときの疲労度の最小値 vector< vector< int64 > > dp( M + 1, vector< int64 >( N + 1, INF)); dp[0][0] = 0; for(int i = 0; i < M; i++){ //日数 for(int j = 0; j < N; j++){ // 今いる街 0 if(dp[i][j] == INF) continue; dp[i + 1][j] = min( dp[i + 1][j], dp[i][j]); dp[i + 1][j + 1] = min( dp[i + 1][j + 1], dp[i][j] + D[j] * C[i]); } } int64 ret = INF; for(int i = 0; i <= M; i++){ ret = min( ret, dp[i][N]); } cout << ret << endl; }- 精神状態がよくなる
- 顧問の先生と今年は多分、4完ボーダーより上だなあという話を入れる
- 顧問の先生が4.5完がボーダーという読みが入る
- とても焦る
- 精神状態がよくなくなった
- 5問目は実装ゲーっぽいので6問目を読む
- うーん
- 5問目を読む
- うーん
- どっちを解くべきか迷う
- 部分点が生死を極めると信じて、とりやすそうな6問目を書く
- 適当な末尾再帰
- 全探だね
- 適当すぎてバグったりしたけど、すぐ直った
- 入力ケース1だけ通った(14:22)
- 2を微妙に放置してみるもこれは天文的な時間がかかりそう
- (ソースコード紛失しました)
- 5問目を読む
- 5問目どうやって早くするんだろう
- 愚直な全探索を書く
- サンプル1だけ通った(14:30くらい)
- 2以降はやばそう
- トイレに行く
- 戻ってくる
- 終わってない(諦め
- (ここへんから理不尽なバグが続く)
- JOI紋章と似た感じのやり方かなあという考察をする
- 直近に'.'へと変化した数字の八方向以外は、盤面とは関係無いような気がする
- そこの八方向だけみるようにする
- 終わらない(謎)
- 見るべき座標たちの数が指数関数的に増加してる
- 見るべき座標はそこまで増加しないはずだろう！！とキレはじめる
- コンパイラによるハラスメントを疑う
- やめたい
- よくわからなくてつらい
- JOI予選落ち不可避
- 適当にデバッグも改善傾向が見られない
- やめよう
- 顧問の先生の名前が浮かぶ
- 関数の名前をそれにする
- セグメント例外(絶望
- 競プロ初心者にもなれなかった
- よくわからないけど、プログラムの流れ的に起こりえないはずの条件文をたくさん加える
- なぜか通った
- 条件無視とかつらみ
- 歓喜
- 入力ケース2
- 終わらないと思わせつつ、5秒位たって出力というプロな溜めが入る
- 全部の入力ケースが通った
- 時間がやばそうだけど、時間制限ない
- 提出(15:11)
#include<bits/stdc++.h> using namespace std; template<typename T1, typename T2> istream& operator>>(istream& is, pair<T1,T2>& a){ return is >> a.first >> a.second; } template<typename T1, typename T2> ostream& operator<<(ostream& os, pair<T1,T2>& a){ return os << a.first << " "<<a.second; } template<typename T> istream& operator>>(istream& is, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) is >> vc[i]; return is; } template<typename T> ostream& operator<<(ostream& os, vector< T >& vc){ for(int i = 0; i < vc.size(); i++) os << vc[i] << endl; return os; } #define ForEach(it,c) for(__typeof (c).begin() it = (c).begin(); it != (c).end(); it++) #define ALL(v) (v).begin(), (v).end() #define UNQ(s) { sort(ALL(s)); (s).erase( unique( ALL(s)), (s).end());} #define fr first #define sc second typedef pair< int , int > Pi; typedef pair< int , Pi > Pii; typedef long long int64; const int INF = 1 << 30; vector< string > str; int H, W; int dy[] = { -1, -1, -1, 0, 1, 1, 1, 0}, dx[] = { -1, 0, 1, 1, 1, 0, -1, -1}; queue< Pi > points; bool ended[1000][1000]; bool hori_sensei_love_function(){ bool flag = false; queue< Pi > buff_points; queue< Pi > que; while(!points.empty()){ Pi p = points.front(); points.pop(); int i = p.first, j = p.second; int get = 0; if(!ended[i][j] && isdigit(str[i][j])){ for(int k = 0; k < 8; k++){ int ny = i + dy[k], nx = j + dx[k]; get += str[ny][nx] == '.'; } if(str[i][j] - '0' <= get){ flag = true; ended[i][j] = true; que.push(Pi( i, j)); } } } while(!que.empty()){ Pi p = que.front(); que.pop(); int i = p.first, j = p.second; str[i][j] = '.'; for(int k = 0; k < 8; k++){ int ny = i + dy[k], nx = j + dx[k]; if(isdigit( str[ny][nx] ) && str[ny][nx] != '9' && !ended[ny][nx]){ buff_points.push( Pi( ny, nx)); } } } while(!buff_points.empty()){ points.push( buff_points.front()); buff_points.pop(); } return flag; } bool foo(){ bool flag = false; for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ if(isdigit(str[i][j])){ if(str[i][j] == '9') continue; int get = 0; for(int k = 0; k < 8; k++){ int ny = i + dy[k], nx = j + dx[k]; get += str[ny][nx] == '.'; } if(str[i][j] - '0' <= get){ flag = true; ended[i][j] = true; } } } } for(int i = 0; i < H; i++){ for(int j = 0; j < W; j++){ if(ended[i][j]){ str[i][j] = '.'; for(int k = 0; k < 8; k++){ int ny = i + dy[k], nx = j + dx[k]; if(isdigit( str[ny][nx] ) && str[ny][nx] != '9' && !ended[ny][nx]){ points.push( Pi( ny, nx)); } } } } } return flag; } int main(){ cin >> H >> W; str.resize(H); for(int i = 0; i < H; i++){ cin >> str[i]; } int ret = 0; bool changed = foo(); if(changed) ret++; while(changed){ changed = hori_sensei_love_function(); if(changed) ret++; } cout << ret << endl; }- 6問目を考え始める
- 朝のポスターの2分を思い出す
- 制約的に半分全列挙を疑う
- 書いてみる
- 書けた
- かけてなかった
- 死んだほうがいい
- 書けたみたい
- そこからどうするんだろう
- セグ木を疑う
- 必要なところだけ作る例のアレかな
- 時間がなさそう
- 時間が残されていない
- やめた
- 提出ミスでの死だけは勘弁ということで全てを確認
- 良さそうと思ったところで終了
問題1
179204 5415 293725 6000 474688問題4
1242866 2377989 51767722 9684358 144764153問題5
1735 993949 994510 343350 442542問題6(1だけよ)
2816001618489474
0 件のコメント:
コメントを投稿