Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

JOI 予選 2014-2015


JOI 予選2013 - 2014 参加記 - Lilliput Steps

懲りずに今年も 6 色に挑戦しました. 結論から言うと 1 / 6 です Ω\ζ°)チーン. 俺が J 言語だ!!
答えとひとことコメンツも書いておきます.
kagamiz 解が一応書かれているので, 良ければ使って下さい :)

1 水道料金 (Water Rate)

[感想] J 言語って素敵だと思う.

[コード]

OUT =: 'C:\joi2015\out.txt'
 
joi_2015_yo1 =: 3 : 0
    data =. ".' '(I.1-CR I.t)}t=.1!:1<'C:\joi2015\in.txt'
    a=.(<./>(*/4 0{data);1{data+>./>0;(-/4 2{data)*3{data)
    a=. ; ":&.> '' ; a
    a 1!:3 <OUT
)
 
solve =: 3 : 0
 '' 1!:2 <OUT
 joi_2015_yo1 'input.txt'
)
 
solve''

[解答]

1 : 179204
2 : 5415
3 : 293725
4 : 6000
5 : 474688

↑ 本番はここまでで 1 時間 20 分を使いました. コード中の

    a=. ; ":&.> '' ; a
    a 1!:3 <OUT

にたどり着くのに 1 時間かかった. これからも J 言語の勉強を続けたいです.

↓ ここから予選後に解いた問題 (2 問目は Scratch で解くつもりだったが File IO が出来ないのでそれ以降を諦めた)

2 クリスマスパーティー (Christmas Party)

[感想] 今年は JOI くんに 3 人は友だちがいるらしく JOI くん嬉しそう.
3 年前から 2 問目は 2 次元っぽい配列の処理問題が続いていますね.

[コード] (6 色とは概念)

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int N, M;
    int A[128];
    int sc[128] = {0};
    
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < M; i++) scanf("%d", A + i);
    
    for (int i = 0; i < M; i++){
        int wa = 0;
        for (int j = 0; j < N; j++){
            int x;
            scanf("%d", &x);
            sc[j + 1] += A[i] == x;
            wa += A[i] != x;
        }
        sc[A[i]] += wa;
    }
    
    for (int i = 1; i <= N; i++) printf("%d\n", sc[i]);
    
    return (0);
}

[解答] (長いので 最初の 3 つの数字 Only)

1 : 7, 26, 33
2 : 8, 47, 72
3 : 70, 70, 143
4 : 24, 27, 62
5 : 95, 95, 28

3 気象予報士 (Weather Forecaster)

[感想] 模擬予選の 3 よりは簡単だったみたいですね. ただ, OJ に慣れていない組が末尾空白をつけたという事例が何件か報告されていてつらそう.

出力の各行の行頭と行末には余計な空白を入れないこと.

と明言されているので問題文はちゃんと読みましょう.

diff をとる癖を付けないといけないですね.

[コード]

#include <bits/stdc++.h>

const int INF = 1001001001;

using namespace std;

int main()
{
    int w, h;
    
    scanf("%d %d", &h, &w);
    
    for (int i = 0; i < h; i++){
        int ctr = INF;
        for (int j = 0; j < w; j++){
            char c;
            scanf(" %c", &c);
            ctr = (c == 'c' ? 0 : ctr + 1);
            printf("%d%c", ctr >= INF ? -1 : ctr, " \n"[j + 1 == w]);
        }
    }
    
    return (0);
}

[解答] (長いので最初の 5 つの数字だけ)

1 : -1 0 1 2 0
2 : -1 -1 -1 0 1
3 : -1 0 1 0 0
4 : -1 -1 0 0 0
5 : 0 1 2 0 1

4 シルクロード (Silk Road)

[感想] 4 番はちょっと易化してる印象を受けた. JOI の "予選 4 は DP" が今年もまた崩れなかった.
軽く解説をすると, dp[j] := 町j にくるまでの疲労度の min, で DP をするといいです.
最初無限大で初期化しないといけませんが, 最大で 10^3 * 10^3 * 10^3 = 10^9 になることはきちんと見積もりましょう. (C++ などの言語なら int に収まります.)

[コード]
実は 4 は後で答え合わせを後輩としようと思ってコードを競技中に書いていました.こいつは Java で解いてやろうと思って Java を使っていました(当時は意欲があり 6 色を意識していた). 提出はしていないけど.
あと入力は uwi さんのものを使いました.

import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Collections;
import java.util.BitSet;
import java.util.InputMismatchException;

public class t4 {
	static InputStream is;
	static PrintWriter out;
	static String INPUT = "";
	
	static void solve()
	{
		int n = ni(), m = ni();
		int [] D = na(n), C = na(m);
		int [] dp = new int[n + 1];
		
		for (int i = 1; i <= n; i++) dp[i] = 1001001001;
		dp[0] = 0;
		
		for (int i = 0; i < m; i++){
			for (int j = n; j >= 1; j--){
				dp[j] = Math.min(dp[j], dp[j - 1] + D[j - 1] * C[i]);
			}
		}
		
		System.out.println(dp[n]);
	}
        //後略

[解答]

1 : 1242866
2 : 2377989
3 : 51767722
4 : 9684358
5 : 144764153

↑来年以降は 5 は Java で解きたいし競プロで Java を使いこなせるようになりたいなあ.

5 砂の城 (Sandcastle)

[感想] JOI らしい問題だと思った.
まず, 波は $O(WH)$ 回くらい押し寄せる可能性があるので, 波が来るごとに盤面を $O(WH)$ で更新すると計算量が $O(W^2H^2)$ になってコンテスト中には間に合わない.
そこで, 倒壊した箇所の近辺のみが局所的な影響を受けることを活かして盤面の更新を $O(1)$ に抑えると, 計算量が $O(WH)$ となる.
多項式で TLE にさせるにしてもこれくらいの制約が必要なんですね... (勉強になった)

[コード]

#include <bits/stdc++.h>

using namespace std;

int broken[1024][1024];
bool vis[1024][1024];
char board[1024][1024];

int countBroken(int y, int x, int lev)
{
    int ret = 0;
    
    for (int i = -1; i <= 1; i++){
        for (int j = -1; j <= 1; j++){
            if (i == 0 && j == 0) continue;
            ret += (~broken[y + i][x + j] && broken[y + i][x + j] <= lev);
        }
    }
    
    return (ret);
}

int main()
{
    int w, h;
    
    scanf("%d %d", &h, &w);
    
    memset(broken, -1, sizeof(broken));
    memset(board, '.', sizeof(board));
    
    int ans = 0;
    queue<pair<int, int> > q;
    
    for (int i = 1; i <= h; i++){
        scanf("%s", board[i] + 1);
        for (int j = 1; j <= w; j++){
            if (board[i][j] == '.'){
                broken[i][j] = 0;
                vis[i][j] = true;
                q.push(make_pair(i, j));
            }
            else board[i][j] -= '0';
        }
    }
    
    while (q.size()){
        pair<int, int> x = q.front(); q.pop();
        
        int Y = x.first, X = x.second;
        ans = max(ans, broken[Y][X]);
        
        for (int i = -1; i <= 1; i++){
            for (int j = -1; j <= 1; j++){
                if (i == 0 && j == 0) continue;
                if (!vis[Y + i][X + j] && countBroken(Y + i, X + j, broken[Y][X]) >= board[Y + i][X + j]){
                    broken[Y + i][X + j] = broken[Y][X] + 1;
                    vis[Y + i][X + j] = true;
                    q.push(make_pair(Y + i, X + j));
                }
            }
        }
    }
    
    printf("%d\n", ans);
    
    return (0);
}

[解答]

1 : 1735
2 : 993949
3 : 994510
4 : 343350
5 : 442542

あとオタクなので 5-2 と 5-3 の出力をみてアレを思い浮かべました. アレが何を指しているかをわかった人はすごいと思います(こなみ)

6 財宝 (Treasures)

[感想] Anna は現金な人で, Bruno はロマンチストだった.
愚直に全探索をすると $3^{30}$ オーダーになってしまうが, 2 つの 15 個の集合に分けることを考えると, 片方の集合での取り方を決めたときに, もう片方の集合からどれを取るかは, もう片方の集合での市場価値の差が一定の区間になることから, セグメント木で貴重度の最大値の位置を求めてしまえば良い.
一定の区間にたいする処理はセグメント木でなくともスライド最小値などをしても良いが, この開放で行くと時間計算量は $10^8$ オーダー, 空間計算量も $10^7$ オーダーとなるので焼け石に水.
かなり定数が重いので 1 ケース 90 ~ 120 秒とかかかったけど, こういう問題が出題できるのが JOI の予選形式の醍醐味な気もしますね.

[コード]

#include <bits/stdc++.h>

#define MAX_C (14348907) // 3^15
#define MAX_S (16777216) // 2^24
typedef long long Int;

const Int INFLL = 1001001001001001001ll;

using namespace std;

pair<Int, Int> c[MAX_C];
Int diff[MAX_C];
Int seg[2 * MAX_S - 1];

Int getMax(int a, int b, int k = 0, int l = 0, int r = MAX_S)
{
    if (b <= l || r <= a) return (-INFLL);
    if (a <= l && r <= b) return (seg[k]);
    Int lch = getMax(a, b, k * 2 + 1, l, l + r >> 1),
        rch = getMax(a, b, k * 2 + 2, l + r >> 1, r);
    
    return (max(lch, rch));
}

int main()
{
    int N;
    Int D, A[32], B[32];
    Int ans = 0;
    
    scanf("%d %lld", &N, &D);
    
    for (int i = 0; i < N; i++){
        scanf("%lld %lld", A + i, B + i);
    }
    
    int mul = 1;
    for (int i = N / 2; i < N; i++) mul *= 3;
    for (int i = 0; i < mul; i++){
        int tmp = i;
        Int x = 0, y = 0;
        for (int j = N / 2; j < N; j++){
            if (tmp % 3 == 1){
                x += A[j];
                y += B[j];
            }
            else if (tmp % 3 == 2){
                x -= A[j]; y -= B[j];
            }
            tmp /= 3;
        }
        if (-D <= x && x <= D) ans = max(ans, y);
        c[i] = make_pair(x, y);
    }
    
    sort(c, c + mul);
    
    for (int i = 0; i < mul; i++){
        seg[i + MAX_S - 1] = c[i].second;
        diff[i] = c[i].first;
    }
    
    for (int i = MAX_S - 2; i >= 0; i--) seg[i] = max(seg[i * 2 + 1], seg[i * 2 + 2]);
    
    int mul2 = 1;
    for (int i = 0; i < N / 2; i++) mul2 *= 3;
    for (int i = 0; i < mul2; i++){
        int tmp = i;
        Int x = 0, y = 0;
        for (int j = 0; j < N / 2; j++){
            if (tmp % 3 == 1){
                x += A[j];
                y += B[j];
            }
            else if (tmp % 3 == 2){
                x -= A[j]; y -= B[j];
            }
            tmp /= 3;
        }
        int lb = lower_bound(diff, diff + mul, -D - x) - diff,
            ub = upper_bound(diff, diff + mul, D - x) - diff;
        ans = max(ans, y + getMax(lb, ub));
    }
    
    printf("%lld\n", ans);
    
    return (0);
}

[解答]

1 : 2816001618489474
2 : 5075857577829288
3 : 8496991294205703
4 : 9999083047722563
5 : 14621549922920084

まとめ

  • J 言語は素晴らしい
  • 出力には注意しよう
  • 問 4 に 5 年連続 DP