JOI本選2018
JOI本選2018(オープン)
参加しました。252点でした。3問目の全探索が通らず。
備忘録のため、コードを貼ります。
1問目
問題：1次元上に$N$個の点が与えられます。$K$個の区間で, 全ての点を覆います。「各区間のmax - min」の和を最小化してください。(最小値 + Kを出力します)
解法：$K=1$の答えからいくつ減らせるかを考えます. これは「隣接する2点の距離」を大きい方から$K-1$個取ったときの和と同じです。$O(NlogN)$
#include
#include
#include
using namespace std;
int n, k;
int t[100000];
int kt[100000];
int main() {
int i;
cin >> n >> k;
for (i = 0; i < n; i++) cin >> t[i];
for (i = 0; i < n - 1; i++) {
kt[i] = t[i + 1] - t[i];
}
sort(kt, kt + n - 1, greater());
int ans = t[n - 1] - t[0];
for (i = 0; i < k - 1; i++) {
ans -= kt[i];
}
ans += k;
cout << ans << endl;
return 0;
}
2問目
問題：大きさと価値がある商品がN個あります。いくつか選んで、価値の和 - (大きさの最大値 - 大きさの最小値)を最大化してください。
解法：
・$O(N^3)$：大きさの最大値と最小値の組み合わせは$O(N^2)$あります。これを固定すると、取ることができる商品が定まります。
・$O(N^2)$：商品を大きさ昇順でソートしておくと、取ることができる商品は一つの区間で表せます。よって、価値の累積和を用いると、先ほどの解法が$O(N^2)$に落ちます。
・$O(NlogN)$：上記の解法を改善します。商品L～Rを取る場合のスコアf(L, R)は、g(L) + h(R)の形に変形できるので、Rを動かしながらg(L)の最大値を求める感じでできます。
#include
#include
#include
#define int long long
using namespace std;
typedef pair<int, int> P;
int n;
P p[500000];
int a[500000], b[500000];
int rb[500001];
int fl[500001]; //fl[l] = a[l] - rb[l]
int fr[500001]; //fr[r] = rb[r + 1] - a[r]
//fr[r] + fl[l] = 区間[l, r]を選んだときのスコア
signed main() {
int i;
cin >> n;
for (i = 0; i < n; i++) cin >> p[i].first >> p[i].second;
sort(p, p + n);
for (i = 0; i < n; i++) { a[i] = p[i].first; b[i] = p[i].second; }
for (i = 1; i <= n; i++) { rb[i] = rb[i - 1] + b[i - 1]; }
for (i = 0; i < n; i++) fl[i] = a[i] - rb[i];
for (i = 0; i < n; i++) fr[i] = rb[i + 1] - a[i];
int maxL = fl[0];
int ans = -1;
for (i = 0; i < n; i++) {
maxL = max(maxL, fl[i]);
ans = max(ans, fr[i] + maxL);
}
cout << ans << endl;
return 0;
}
3問目
一言：これはリーディングハードです。誤読しなかった方はプロですね。
問題(間違いの可能性があります)：
n行m列のR,G,Bからなる文字列が与えられます。連続する3行または3列を, 互いに重ならないように, かつ上または右から読んだときに"RGB"の順になるように取ります。最大で何組取れるでしょうか。
解法(n,m≦4)：取り方を全探索します。なぜか通りませんでした(0点) . 残念.
解法以前の問題ですね。全探索の練習をしてきます。
//縦3マス, または, 横3マスでペアを作る
//上から読んだとき or 左から読んだときに、"RGW"になっているペアの個数を最大化せよ -> ではなくて、"RGW"の順で刺さないとダメらしい。
//という問題。ペアが交差したらNG, 内側から刺してもOKな点に注意.（この誤読で1時間以上溶かした）
#include
#include
#include
#include
using namespace std;
int h, w;
string s[10];
int dfs(int used) {
int r, c, res, ret = 0;
for (r = 0; r < h; r++) {
for (c = 0; c + 2 < w; c++) {
if ((used >> (r * w + c)) % 8) continue;
if (s[r][c] != 'R' || s[r][c + 1] != 'G' || s[r][c + 2] != 'W') continue;
res = dfs(used + (7 << (r * w + c)));
ret = max(res + 1, ret);
}
}
for (c = 0; c < w; c++) {
for (r = 0; r + 2 < h; r++) {
if ((used >> (r * w + c)) & 1) continue;
if ((used >> ((r + 1) * w + c)) & 1) continue;
if ((used >> ((r + 2) * w + c)) & 1) continue;
if (s[r][c] != 'R' || s[r + 1][c] != 'G' || s[r + 2][c] != 'W') continue;
res = dfs(used + (1 << (r * w + c)) + (1 << ((r + 1) * w + c)) + (1 << ((r + 2) * w + c)));
ret = max(res + 1, ret);
}
}
return ret;
}
int main() {
int i;
cin >> h >> w;
// if (h > 4 || w > 4) return 0;
for (i = 0; i < h; i++) cin >> s[i];
cout << dfs(0) << endl;
return 0;
}
4問目
問題：N頂点M辺の連結で自己ループや多重辺がない無向グラフが与えられます. $S$->$T$最短路を一つ選び, 経路上の辺のコストを全て0にできるとき, $U$->$V$最短路の長さの最小値を求めてください.
解法(S = U)：S = Uの場合, S->V->TがS->Tの最短経路の一つであれば0, そうでなければS->Vの距離が答えです。
解法(M = N - 1)：S->T間の最短路が1通りなので, S->T最短路に含まれる辺のコストを0にして, U->V最短路を求めればよいです。
自分の解法(31点)：S->T最短路に使われうる辺の集合について, 辺のコストを0にし, U->V最短路を求めました。嘘解法なので、満点は取れません。
//S->T最短経路に使われうる辺をコスト0に置き換えたのち, U->V最短路を求める.
#include
#include
#include
#include
#include
#define int long long
using namespace std;
typedef pair<int, int> P;
int INF = 1e+15;
int n, m, s, t, u, v;
int a[200000], b[200000], c[200000];
vector et[100000];
vector ec[100000];
int minCost[3][100000];
priority_queue<P, vector, greater> que; void dijkstra(int minCost[], int start) { int i; for (i = 0; i < n; i++) minCost[i] = INF; que.push(P(0, start)); minCost[start] = 0; while (!que.empty()) { P now = que.top(); que.pop(); int cst = now.first; int pos = now.second; for (i = 0; i < et[pos].size(); i++) { int npos = et[pos][i]; int ncst = cst + ec[pos][i]; if (minCost[npos] > ncst) { minCost[npos] = ncst; que.push(P(ncst, npos)); } } } } signed main() { int i; cin >> n >> m >> s >> t >> u >> v; s--; t--; u--; v--; for (i = 0; i < m; i++) { cin >> a[i] >> b[i] >> c[i]; a[i]--; b[i]--; et[a[i]].push_back(b[i]); et[b[i]].push_back(a[i]); ec[a[i]].push_back(c[i]); ec[b[i]].push_back(c[i]); } dijkstra(minCost[0], s); dijkstra(minCost[1], t); for (i = 0; i < m; i++) { if (minCost[0][a[i]] + c[i] + minCost[1][b[i]] == minCost[0][t]) { c[i] = 0; } else if (minCost[0][b[i]] + c[i] + minCost[1][a[i]] == minCost[0][t]) { c[i] = 0; } } for (i = 0; i < n; i++) { ec[i].clear(); } for (i = 0; i < m; i++) { ec[a[i]].push_back(c[i]); ec[b[i]].push_back(c[i]); } dijkstra(minCost[2], u); cout << minCost[2][v] << endl; return 0; }
5問目
問題：長さ2^Lの配列と, Q個の質問が与えられます. 各質問では0,1,?を用いて該当する要素の番号を指定しています. 該当する要素の和を各質問について答えてください.
制約：L≦20 , Q ≦ 10^6
解法(22点)：
「先頭が0の質問, 1の質問, ?の質問」を順に処理することを考えると、?の質問以降では、配列を真ん中で分けて前半i番目と後半i番目を足したものをi番目の要素とした配列に縮約して処理できることが分かります.
よって、これを再帰的に実装します。（計算量は$O(3^L + QL)$くらい）
75点狙えると思いきや、意外とメモリ計算量が多いらしく、通せませんでした。
#include
#include
#include
#include
using namespace std;
typedef pair<string, int> P;
int l, q;
string s;
vector pre;
void dfs(int cnt, vector v) {
if (cnt == 0) {
//cout << v[0] << endl;
pre.push_back(v[0]);
return;
}
int i;
//0
vector nv;
for (i = 0; i < v.size() / 2; i++) {
nv.push_back(v[i]);
}
dfs(cnt - 1, nv);
nv.clear();
//1
for (i = v.size() / 2; i < v.size(); i++) {
nv.push_back(v[i]);
}
dfs(cnt - 1, nv);
nv.clear();
//?
for (i = 0; i < v.size() / 2; i++) {
nv.push_back(v[i] + v[i + v.size() / 2]);
}
dfs(cnt - 1, nv);
nv.clear();
}
int getId(string query) {
int i, ret = 0;
for (i = 0; i < query.size(); i++) {
ret *= 3;
int val;
if (query[i] == '0') val = 0;
else if (query[i] == '1') val = 1;
else val = 2;
ret += val;
}
return ret;
}
int main() {
int i;
cin >> l >> q;
cin >> s;
vector v;
for (i = 0; i < (1 << l); i++) v.push_back(s[i] - '0');
dfs(l, v);
for (i = 0; i < q; i++) {
string query;
cin >> query;
cout << pre[getId(query)] << endl;
}
return 0;
}
感想
3問目で嵌ってしまいました. 全探索は書けるようにしたいですね.
最近は, 些細なミス（誤読、変数名間違えなど）が目立っているので, 注意力を鍛えたい.
