Chokudai Contest 001
- 問題
30x30のマスに1以上100以下の値がランダムに与えられて、マスを選択して1づつ減らしていく。
全部のマスを0にしたら終わりで手数が少ないと良いスコアがもらえる。
減らしたマスの上下左右の同じ値のマスの値を減らすときは手数は数えない。
(日本語下手)
最初に「全探索して一番つなげて消せるラインを減らしていけばいける？」って思って書いた。。。
普通にTLE(当たり前)。
そのあと「一番大きな値から減らしていけばいいんでは？？」ってなって最大のスコア-2までのマスを全探索して一番長いルートになるやつを消していくやつを書いた。
それでスコアは、83万弱で43位だった(2ページ目に載りたかった)。
自分はマラソン系の方が好きかも。。。
ダイコンが定期的になったらすっっっごい嬉しいです＞＜
- コード
#include <bits/stdc++.h> using namespace std; const int DIRX[4] = {0,0,1,-1}; const int DIRY[4] = {1,-1,0,0}; class banmen{ public: int point[40][40]; int nx,ny; }; int hyo[40][40] = {}; int main() { for(int i = 0;i < 30;i++){ for(int j = 0;j < 30;j++){ cin >> hyo[j][i]; } } bool all_not_zero = true; while(all_not_zero){ all_not_zero = false; int max_p = 0,max_x = 0,max_y = 0; for(int i = 0;i < 30;i++){ for(int j = 0;j < 30;j++){ if(hyo[j][i] != 0) all_not_zero = true; if(max_p < hyo[j][i]){ max_p = hyo[j][i]; max_x = j; max_y = i; } } } queue<pair<int,int> > que; for(int i = 0;i < 30;i++){ for(int j = 0;j < 30;j++){ if(hyo[j][i] >= max_p - 2){ que.push(make_pair(j,i)); } } } vector<pair<int,int> > best_ans; while(que.size()){ banmen hyo2; for(int i = 0;i < 30;i++){ for(int j = 0;j < 30;j++){ hyo2.point[j][i] = hyo[j][i]; } } hyo2.nx = que.front().first; hyo2.ny = que.front().second; vector<pair<int,int> > ans; que.pop(); queue<pair<banmen,vector<pair<int,int> > > > que2; que2.push(make_pair(hyo2,ans)); while(que2.size()){ banmen hyo_now = que2.front().first; vector<pair<int,int> > ans_now = que2.front().second; que2.pop(); int dx = hyo_now.nx; int dy = hyo_now.ny; if(hyo_now.point[dx][dy] == 0) continue; hyo_now.point[dx][dy]--; ans_now.push_back(make_pair(dy,dx)); if(ans_now.size() > best_ans.size()){ best_ans = ans_now; } if(hyo_now.point[dx][dy] == 0) continue; for(int i = 0;i < 4;i++){ if(dx + DIRX[i] < 0 || dx + DIRX[i] >= 30 || dy + DIRY[i] < 0 || dy + DIRY[i] >= 30) continue; if(hyo_now.point[dx][dy] == hyo_now.point[dx + DIRX[i]][dy + DIRY[i]]){ hyo_now.nx = dx + DIRX[i]; hyo_now.ny = dy + DIRY[i]; que2.push(make_pair(hyo_now,ans_now)); hyo_now.nx = dx; hyo_now.ny = dy; } } } } for(int i = 0;i < best_ans.size();i++){ cout << best_ans[i].first + 1 << " " << best_ans[i].second + 1 << endl; hyo[best_ans[i].second][best_ans[i].first]--; } } return 0; }
マラソン系も頑張るぞい
JOI本選参加記
JOI予選でギリギリAランク取れて本選行けたのでその時のことをメモ。
1日目
- プラクティス
控室に行き周りを見る。
完璧に自分はぼっちだった。
何すればいいかわからずそのままプラクティスへ。
設定とかいじる。
マウスのホイールを下にやってるとたまに上にいきなり飛ぶ、多分Virtual Boxでマウス統合をしてないから。
スタッフの人にマウス統合していいか聞くがすぐにノーの返事。。。
矢印キーでの移動で我慢。
↓
- 夜ご飯
バイキング形式で食べ放題だった。
自分はこのままぼっちかと思ったら話しかけてくれた人がいたので助かった(すごい感謝)。
自己紹介の時にたくさんのプロを見た。
↓
- 宿舎へ
お風呂入るのぼっちは怖いからTwitterで誰か行こうといったら行ってくれた人がいた(圧倒的感謝)。
その後プロの部屋にお邪魔した。
あみだくじを見た瞬間やるだけと言って30分くらいで解いてて差を感じる＞＜
そして就寝。
2日目
- 朝
朝に早起きしてJOI饅頭を解いた(2回目)。
30分くらいかけてしまった。
朝ごはんもTwitterのおかげでぼっちは回避。
そしてバスへ。
↓
- 会場
会場について緊張してくる。
とりあえずTwitterで知り合ったプロと一緒にいた。
席について待機。
周りはマスコットとかお菓子とか持ってきてたので持ってくればよかった＞＜
本選前の10分とかやることなくてすごいもどかしい。
↓
- 本選
まず1問目をみる。
ここで誤読、オレンジの順番を変えていいと思いソートをやりだす。
途中で気づいてやり直し。
1問目は1時間くらいかけてしまった。
クソ汚いコードを晒しあげておく(将来見た時に成長を感じそう？)。
1問目
とりあえず再帰を書いてメモ化。
#include <bits/stdc++.h> using namespace std; #define INF (1 << 30) #define INFLL (1LL << 60) #define ll long long ll n,m,k; ll a[20010] = {}; ll memo[20010]; ll rui[20010] = {}; int mina_s[20010][1010] = {}; int maxa_s[20010][1010] = {}; ll saiki(int now){ if(memo[now] != INFLL) return memo[now]; ll sum_mi = INFLL; for(int i = 1;i <= m;i++){ if(now + i > n) break; ll b = 0,c = 0; ll maxa = 0,minb = INF; minb = a[mina_s[now+1][i-1]]; maxa = a[maxa_s[now+1][i-1]]; c = rui[now + i] - rui[now]; b = saiki(now + i) + k + (i * (maxa - minb)); sum_mi = min(sum_mi,b); } if(sum_mi == INFLL) sum_mi = 0; return memo[now] = sum_mi; } int main(){ cin >> n >> m >> k; for(int i = 0;i < 20010;i++){ memo[i] = INFLL; } for(int i = 1;i <= n;i++){ cin >> a[i]; } for(int i = 1;i <= n;i++){ rui[i] = rui[i - 1] + a[i]; } //a個からb個選んだ時の最小の大きさと最大の大きさを前処理 for(int i = 1;i <= n;i++){ int min_now = i; int max_now = i; for(int j = 0;j <= m;j++){ if(i + j > 20010) break; if(a[min_now] > a[i + j]) min_now = i + j; mina_s[i][j] = min_now; if(a[max_now] < a[i + j]) max_now = i + j; maxa_s[i][j] = max_now; } } cout << saiki(0) << endl; return 0; }
二問目(50点)
JとIは前後におくのが最適なのは自明、Oは全通り試した。
小問題3でTLEを出してしまい部分点だけ。
文字列からJOIの数を再帰で求めてたのが☓。
#include <bits/stdc++.h> using namespace std; #define INF (1 << 30) #define INFLL (1LL << 60) #define ll long long int n; string str; ll memo[100010][4]; ll saiki(int now,int how){ ll a = 0; if(now == n) return 0; if(memo[now][how] != INF) return memo[now][how]; if(how == 0){ if(str[now] == 'J') a += saiki(now + 1,how + 1); a += saiki(now + 1,how); }else if(how == 1){ if(str[now] == 'O') a += saiki(now + 1,how + 1); a += saiki(now + 1,how); }else if(how == 2){ if(str[now] == 'I') a += 1; a += saiki(now + 1,how); } return memo[now][how] = a; } void init(){ for(int i = 0;i < 100010;i++){ for(int j = 0;j < 4;j++){ memo[i][j] = INF; } } } int main(){ cin >> n >> str; ll ans = 0,num; string str2 = str; n++; str = "J" + str2; init(); num = saiki(0,0); ans = max(ans,num); str = str2 + "I"; init(); num = saiki(0,0); ans = max(ans,num); init(); str = ""; for(int i = 0;i < str2.size();i++){ for(int j = 0;j < i;j++){ str += str2[j]; } str += "O"; for(int j = i;j < str2.size();j++){ str += str2[j]; } init(); num = saiki(0,0); ans = max(num,ans); str = ""; } cout << ans << endl; return 0; }
1問と部分点しか出来なかった。。。
結構つらい。。。
2問目は家に帰ってから解き直してACした。
150点は流石にまずいと思ったのでこれから勉強の量も増やす。
来年こそ合宿に行ってやる！！
