| 590位 | 231.54pt | |
| 250 | Accepted | 231.54 |
|---|---|---|
| 500 | Opend | 0.0 |
| 1000 | WA | 0.0 |
| Hack | - |
1270→1318(+48)
ギリギリ進めた.
1000が明らかに間違っているのに, 誰も撃墜しようとしてこなくて怖かった.
1問ごとにrm *.exeしていたので, 今回は実行するファイル間違えたりしなくて済んだ.
一人明らかに250間違っている人が居たのに, 見逃してしまった辺りがクズい.
今更記事書いてるあたりもクズい.
更に250しか書いてないあたりもクズい.
大体やるだけ.
二度同じ物を使おうとしたりしないように注意する.
長さの最大値が小さいので, arr[長さ]=本数みたいに持ってもいいけれど,
本数が少ないので単純に2重ループにした.
二分探索もせずに, 100から下がっていく等という怠惰さ.
後から気付いたけど, map<int, int> arrにしてarr[-1]=100;とかやっておけば, YangとYinで場合分けする必要がなくなっておいしい.
こういう, オーダー的な制約がかなり甘い問題は, 速いアルゴリズム作るとかよりも, いかに場合分けが出ない, 実装しやすい, バグらせにくい物を書くかを考えた方が良い気がした.
int n; bool can(vector<int>& len, int k){ vector<bool> use(n); int cnt = 0; rep(i, n){ if(use[i]) continue; if(len[i] == k){ use[i] = true; ++cnt; continue; } for(int j=i+1; j<n; ++j){ if(!use[j] && len[i] + len[j] == k-1){ use[i] = use[j] = true; ++cnt; break; } } } return cnt >= k; } inline int FoxAndKgram::maxK(vector <int> len){ n = len.size(); for(int i=100; i>=1; --i){ if(can(len, i)) return i; } return 0; }