JOI予選参加記
かなり遅くなってしまいましたが、12月11日の情報オリンピック予選の振り返り記事を書いていきます。某部活のアドベントカレンダーもかねて...
問題文はこちらからどうぞ→
JOI 2016/2017 予選 問題文・採点用入出力・解説
問1 電子レンジ
焦らず丁寧に...。0度より高いか低いかで解の導出方法が異なることに注意。
//ヘッダー等は省略 int a, b, c, d, e; signed main() { cin >> a >> b >> c >> d >> e; if(a > 0){ cout << e * (b - a) << endl; } else{ cout << c * (-a) + d + e * b << endl; } return 0; }
問2 ポイントカード
総和を求めてから、一番コストのかかるポイントカードを破棄すればよい。
//ヘッダー等は省略 int n, m; int a[1010], b[1010]; int ans = 0, mx = 0; signed main() { cin >> n >> m; for(int i = 1; i <= m; i++){ cin >> a[i] >> b[i]; } for(int i = 1; i <= m; i++){ if(a[i] < n){ ans += n - a[i]; mx = max(mx, n - a[i]); } } cout << ans - mx << endl; return 0; }
問3 休憩スペース
全通り調べる。具体的にはi行j列目において、ベンチをそこが左端または上端となるようにおけるか、を全通り調べる。
//ヘッダー等は省略 int n, m, d; char field[110][110]; int ans = 0; signed main() { cin >> n >> m >> d; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> field[i][j]; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ if(j <= m - (d - 1)){ bool flag = true; for(int k = 0; k < d; k++){ if(field[i][j + k] != '.'){ flag = false; } } if(flag){ ans++; } } if(i <= n - (d - 1)){ bool flag = true; for(int k = 0; k < d; k++){ if(field[i + k][j] != '.'){ flag = false; } } if(flag){ ans++; } } } } cout << ans << endl; return 0; }
少しバグらせてしまったのと、テストケースの表示がおかしかったのが災いして、少し時間を要してしまった。
問4 ぬいぐるみの整理
まさかの予選でのbitDP。過去に例を見ない問題構成で、かなり驚いた。
あらかじめ累積和をとっておき、任意の区間に任意のぬいぐるみが何個あるかをO(1)で求められるようにしておく。
連続してぬいぐるみを置くので、置き方はM!通り。
下からkビット目が1ならぬいぐるみkを置き終わっている、という記法*1を使うと、(これを「現在の状態」と呼ぶことにする。)
dp[i]=現在の状態がiの時のぬいぐるみの交換回数の最小値
と表せる。「現在の状態」の通り数はビットの立ち方の通り数、すなわち2^M通りである。
あとは動的計画法なりメモ化再帰なり好きなようにやってください。計算量はO(M*2^M)。
問5 尾根
今年の問題は参加者を落としにかかってきているな...
愚直に各々のマスから幅優先探索を行うと、O(H^2 W^2)となってしまい、これだと20点しか得られない。
何度も何度も同じ経路をたどっているので、ロスが発生している。
ここで、番号の小さい順に幅優先探索を行い、その結果を覚えておき、次回以降そこに到達したときは探索を打ち切る、という手法を使えば、O(HW)で解を導ける。
どうやって覚えておくかというと、1か所に流れるときは流れ着くマスの番号、2か所以上の時は0とでもしておけばよい。
2か所以上に流れるマス(尾根)に到達できるマスは尾根と確定するので、いちいち流れ着くすべてのマスを覚えておく必要はない。1か所の場合は複数のルートから最終的に1つのマスにたどり着くという可能性があるため、覚えておく必要がある。*2
問6 ヘビのJOI君
「部屋iで自分の現在の状態がj、温度変化に対応できるようになるまでにあとk分」の状態にたどり着くまでの最短時間を求める問題。
部屋が同じでも、現在の状態や温度変化に対応できるようになるまでの残り時間が違えば、違う頂点として扱うのがミソ。頂点数は多く見積もっても10000*3*201通りしかない。
ダイクストラで実装すればよい。
//ヘッダー等は省略 int n, m, x; int t[10010], a[20010], b[20010], d[20010]; vector<pair<int, int> > node[10010]; struct status { int time, place, t, remain; status(int _time, int _place, int _t, int _remain) { time = _time, place = _place, t = _t, remain = _remain; } bool operator<(const status another)const{ return time < another.time; } bool operator>(const status another)const{ return time > another.time; } }; priority_queue<status, vector<status>, greater<status> > pq; bool visited[10010][3][210]; int fast[10010][3][210]; void dijkstra() { for(int i = 1; i <= n; i++){ for(int j = 0; j <= 2; j++){ for(int k = 0; k <= x; k++){ fast[i][j][k] = INF; } } } { status in(0, 1, 0, x); pq.push(in); } while(!pq.empty()){ status now = pq.top(); pq.pop(); if(!visited[now.place][now.t][now.remain]){ visited[now.place][now.t][now.remain] = true; fast[now.place][now.t][now.remain] = now.time; for(auto pt:node[now.place]){ if(now.remain - pt.F <= 0){ status in(now.time + pt.F, pt.S, t[pt.S], t[pt.S] == 1 ? 0 : x); pq.push(in); } else{ if(t[pt.S] == 1 || t[pt.S] == now.t){ status in(now.time + pt.F, pt.S, now.t, t[pt.S] == 1 ? now.remain - pt.F : x); pq.push(in); } } } } } } int main() { scanf("%lld%lld%lld", &n, &m, &x); for(int i = 1; i <= n; i++){ scanf("%lld", &t[i]); } for(int i = 1; i <= m; i++){ scanf("%lld%lld%lld", &a[i], &b[i], &d[i]); } for(int i = 1; i <= m; i++){ node[a[i]].PB(MP(d[i], b[i])); node[b[i]].PB(MP(d[i], a[i])); } dijkstra(); int mn = INF; for(int j = 0; j <= 2; j++){ for(int k = 0; k <= x; k++){ mn = min(mn, fast[n][j][k]); } } printf("%lld\n", mn); return 0; }
結果等
全完(600点)でした。
今回は、過去の問題と傾向がかなり違っていたと思います。
本選では昨年のようにDPで殺されることなく、春合宿に進みたいと思います。
まだまだ精進がんばるぞい！
問題のWrite-upを書くのはかなり久々なので文章が拙いような気がする...。気まぐれで修正かけるかもしれません。
