2016-10-22

ACM-ICPC 2016 アジア地区つくば大会参加記

参加記

明治大学のチームHutari.として参加しました。
去年は初出場かつ国内予選で敗退してしまったので、初めてのアジア地区大会でした。

前日

緊張というよりはわくわく。
準備はとりあえず、ライブラリと学生証だけ忘れなければどうとでもなりそう。

ライブラリは枚数制限が無かったのでとくに何も考えずに持っていたものを全部印刷した。↓の記事通りに印刷するといい感じだった。

ICPCのライブラリの印刷手順 - くじらにっき++

クリアファイルに突っ込んでいったが、ファイルバインダーとかに入れると見やすくて良かったかもしれない。

1日目

kog(工学院大学)の人たちと秋葉原で待ち合わせをして、つくばエクスプレスでつくば駅へ。つくばエクスプレスは新幹線ではない。
コーチは2日間とも会場には来ない予定だったが、運営側に伝えそびれてしまっていたようで、register時にスタッフの人たちをざわつかせてしまった。ごめんなさい。

practiceは何事もなく終了。普段とは違う環境だが、そんなにやりづらいという感じもしなかった。ここでいろんなコードを投げてジャッジサーバーの様子をよく見ておくとよかったらしい。

その後は筑波大学にバスで移動して歓迎会。移動中ずっと「こういうとこに住みたい」って連呼してた。

歓迎会のチーム紹介はチームメイトに丸投げした。Hutari.というチーム名で、前に出たのが3人だったのでそれだけで笑いがとれた。(何故Hutari.なのかは秘密)。

歓迎会後はホテルに移動。一人一部屋ですごく良いホテルだった。 ry0u_ydくんとスーパーに行ったりだべったりしてから寝る。 0時には横になったのに眠りにつけたのは3時とかだった。

2日目

朝。最大の事件が起きる。

めがああああああああ
— t8m8 (@teight_meight) 2016年10月15日

コンタクトレンズの消毒液を目に入れてしまって激痛が走る。目が焼けるように熱い。そして悶えてたらコンタクトが何処かへ消える。踏んだり蹴ったり。

いつも使っている物はそのままコンタクトレンズを濯いでも大丈夫なのだが、今回は小さいサイズのものを選んで買ったために違う種類(中和剤入れないとダメ)だったのが原因。

結局探し回っていたらコンタクトは発見できて、目薬で洗って無理やり装着していった。朝食は食べ損ねた。

コンテスト

コンテスト問題

うちのチームでは問題や作業を分担するということはできなくて、全員で同じ問題を進めていく。
A問題はとくに問題なくAC。
B問題は隣り合う数字をswapするときに、同じ数字をswapするパターンで少しハマった。
C問題は同じレーンに戻ってくる数を引き忘れて1WA。その後AC。
D問題は各文字の出現回数を部分文字列ごとにハッシュ値として保持しておいてhogehoge、みたいなことをやったがACがとれないままコンテスト終了。
E問題を早く読んでこちらに手をつけておけば良かったかもしれない...。

結果は3完39位。
反省点もあって悔しかったが、やっぱりオンサイトで強豪チームたちと競うのは楽しい。

表彰式

歓迎会の時のチーム紹介でも思ったが、順位発表にあの方(筑波大の教授?)を抜擢したのは大正解だと思う。
上海交通大のNew Metaと東大のCxiv-Dxivの1位争いはアツかった。

懇親会

いろんな企業がブースを構えていて、グッズを配ったりクイズと景品を用意したりしていた。競技プログラマーにクイズを与えると飯が減らなくなることがよくわかる。
Googleのクイズはかなり面白かった。社員さんにヒント(ほぼ答え)を貰いながら進めた。
ドワンゴは、WA投げという本番中のWAの回数に応じて輪投げをして景品を貰えるというのをやっていた。D問題でクソほどWAを出していたので最大回数なげることができた。嬉しいのか悲しいのか複雑な気分になる。
あと、PFNのブースで思ったのは秋葉さんは人に説明をするのが本当に上手い。

懇親会の後は解散だったが、何人かの人たちと飲みにいった。普段話せない人たちと話せて楽しかった。後泊組ではないので途中で帰らないといけなかったのが残念。

おわり

明大生として出場することはおそらく無いですが、来年も頑張ります。
一緒に出場してくれたチームメイト、準備運営してくれた関係者の皆さんありがとうございました。

f:id:t8m8:20161022152525j:plain

2016-06-25

ICPC 2016 国内予選参加記

参加記

Hutari. というチームで出場した。結果は4完で38位。
うちのチームは問題を分担せずにAから順番に解いていく方針をとった。

問題↓
http://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.html

A

ソートして隣同士を全部見ていく。

B

適当に数をカウントしていく。

C

mからエラトステネスの篩をする。
バグらせて時間を持っていかれた。しかも1WAでペナルティ。

D

区間DP。twitterを見る限り2回に分けてDPをした人が多いっぽい。僕は1回のDPで解く解法をとった。

dp[l][r] = [l, r]で取り除ける最大のブロック数とすると、ある区間[l, r]について
abs(w[l] - w[r]) <= 1 かつ [l+1, r-1]のブロックが全て取り除ける(dp[l+1][r-1] = r - l -1)とき、[l, r]のブロックは全て取り除けるのでdp[l][r] = r - l + 1。
そうでないとき、l<=i<=rなiについて[l, i]と[i+1, r]の2つの区間に分割して和をとった値の最大値となるので、dp[l][r] = max(dp[l][i] + dp[i+1][r])。
最終的に求めるべき答えはdp[0][n-1]。

import java.util.*;

public class D {

    static final Scanner in = new Scanner(System.in);

    static int[][] dp;
    static int[] w;
    static int n;

    static int rec(int l , int r) {
        if (dp[l][r] != -1) return dp[l][r];
        if (l+1 == r) {
            if (Math.abs(w[l] - w[r]) <= 1) return 2;
            else return 0;
        }
        if (l >= r) {
            return 0;
        }

        if (Math.abs(w[l] - w[r]) <= 1) {
            int len = rec(l+1, r-1);
            if (len == r - l -1) {
                return dp[l][r] = r - l + 1;
            }
        }

        int res = 0;

        for (int i=l; i<r; i++) {
            res = Math.max(res, rec(l, i) + rec(i+1, r));
        }

        return dp[l][r] = res;
    }

    static boolean solve() {
        n = in.nextInt();
        if (n == 0) return false;

        w = new int[n];
        for (int i=0; i<n; i++) {
            w[i] = in.nextInt();
        }

        dp = new int[n][n];
        for (int i=0; i<n; i++) {
            Arrays.fill(dp[i], -1);
        }

        System.out.println(rec(0, n-1));
        return true;
    }

    public static void main(String[] args) {
        while(solve());
        in.close();
    }
}

緊張した〜...。

2016-04-26

AOJ 1181: Biased Dice

問題

Biased Dice | Aizu Online Judge

解法

問題の通りにシミュレーション。
nが100までなので、適当にリストでも作っておいてサイコロを投げ入れていけば良い。
バグらせることなく実装できてよかった。

import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class AOJ1181 {

    static final Scanner in = new Scanner(System.in);
    static final PrintWriter out = new PrintWriter(System.out,false);
    static boolean debug = false;

    static int[] dx = { 0, 1, 0,-1};
    static int[] dy = { 1, 0,-1, 0};
    
    @SuppressWarnings("unchecked")
    static void rec(ArrayList[][] list, Dice d, int y, int x) {
        int dir = -1, max = 0;
        for (int k=0; k<4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];
            if (d.face[k] >= 4 && list[ny][nx].size() < list[y][x].size() && max < d.face[k]) {
                max = d.face[k];
                dir = k;
            }
        }
        if (dir == -1) {
            list[y][x].add(d);
        } else {
            d.rotate(dir);
            rec(list, d, y + dy[dir], x + dx[dir]);
        }
    }

    @SuppressWarnings("unchecked")
    static boolean solve() {
        int n = in.nextInt();
        if (n == 0) return false;

        ArrayList<Dice>[][] list = new ArrayList[100][100];

        for (int i=0; i<100; i++) {
            for (int j=0; j<100; j++) {
                list[i][j] = new ArrayList<Dice>();
            }
        }

        for (int i=0; i<n; i++) {
            int t = in.nextInt();
            int f = in.nextInt();
            rec(list, new Dice(t, f), 50, 50);
        }

        int[] cnt = new int[6];

        for (int i=0; i<100; i++) {
            for (int j=0; j<100; j++) {
                if (list[i][j].size() > 0) {
                    Dice d = list[i][j].get(list[i][j].size()-1);
                    cnt[d.face[Dice.TOP] - 1]++;
                }
            }
        }

        for (int i=0; i<5; i++) {
            out.print(cnt[i] + " ");
        }
        out.println(cnt[5]);

        return true;
    }

    public static void main(String[] args) {
        debug = args.length > 0;
        long start = System.currentTimeMillis();

        while(solve());
        out.flush();

        long end = System.currentTimeMillis();
        dump((end-start) + "ms");
        in.close();
        out.close();
    }

    static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

class Dice implements Cloneable{

    public static final int TOP = 4;
    public static final int BOTTOM = 5;
    public static final int FRONT = 2;
    public static final int BACK = 0;
    public static final int LEFT = 3;
    public static final int RIGHT = 1;

    public static final int[][] roll = {
        {TOP,FRONT,BOTTOM,BACK},//+y
        {TOP,LEFT,BOTTOM,RIGHT},//+x
        {TOP,BACK,BOTTOM,FRONT},//-y
        {TOP,RIGHT,BOTTOM,LEFT},//-x

        {FRONT,RIGHT,BACK,LEFT},//cw
        {FRONT,LEFT,BACK,RIGHT},//ccw
    };

    public static final int[] dx = {1,0,-1,0};
    public static final int[] dy = {0,1,0,-1};

    final int[] face;

    public Dice() {
        this.face = new int[6];
        this.face[TOP] = 1; this.face[BOTTOM] = 6; this.face[FRONT] = 2;
        this.face[BACK] = 5; this.face[LEFT] = 4; this.face[RIGHT] = 3;
    }
    public Dice(int top, int front) {
        this.face = new int[6];
        this.face[TOP] = top; this.face[FRONT] = front;
        this.face[BOTTOM] = 7 - top; this.face[BACK] = 7 - front;

        if (top == 1 && front == 2) {
            this.face[LEFT] = 4; this.face[RIGHT] = 3;
        } else if (top == 1 && front == 3) {
            this.face[LEFT] = 2; this.face[RIGHT] = 5;
        } else if (top == 1 && front == 4) {
            this.face[LEFT] = 5; this.face[RIGHT] = 2;
        } else if (top == 1 && front == 5) {
            this.face[LEFT] = 3; this.face[RIGHT] = 4;
        } else if (top == 2 && front == 1) {
            this.face[LEFT] = 3; this.face[RIGHT] = 4;
        } else if (top == 2 && front == 3) {
            this.face[LEFT] = 6; this.face[RIGHT] = 1;
        } else if (top == 2 && front == 4) {
            this.face[LEFT] = 1; this.face[RIGHT] = 6;
        } else if (top == 2 && front == 6) {
            this.face[LEFT] = 4; this.face[RIGHT] = 3;
        } else if (top == 3 && front == 1) {
            this.face[LEFT] = 5; this.face[RIGHT] = 2;
        } else if (top == 3 && front == 2) {
            this.face[LEFT] = 1; this.face[RIGHT] = 6;
        } else if (top == 3 && front == 5) {
            this.face[LEFT] = 6; this.face[RIGHT] = 1;
        } else if (top == 3 && front == 6) {
            this.face[LEFT] = 2; this.face[RIGHT] = 5;
        } else if (top == 4 && front == 1) {
            this.face[LEFT] = 2; this.face[RIGHT] = 5;
        } else if (top == 4 && front == 2) {
            this.face[LEFT] = 6; this.face[RIGHT] = 1;
        } else if (top == 4 && front == 5) {
            this.face[LEFT] = 1; this.face[RIGHT] = 6;
        } else if (top == 4 && front == 6) {
            this.face[LEFT] = 5; this.face[RIGHT] = 2;
        } else if (top == 5 && front == 1) {
            this.face[LEFT] = 4; this.face[RIGHT] = 3;
        } else if (top == 5 && front == 3) {
            this.face[LEFT] = 1; this.face[RIGHT] = 6;
        } else if (top == 5 && front == 4) {
            this.face[LEFT] = 6; this.face[RIGHT] = 1;
        } else if (top == 5 && front == 6) {
            this.face[LEFT] = 3; this.face[RIGHT] = 4;
        } else if (top == 6 && front == 2) {
            this.face[LEFT] = 3; this.face[RIGHT] = 4;
        } else if (top == 6 && front == 3) {
            this.face[LEFT] = 5; this.face[RIGHT] = 2;
        } else if (top == 6 && front == 4) {
            this.face[LEFT] = 2; this.face[RIGHT] = 5;
        } else if (top == 6 && front == 5) {
            this.face[LEFT] = 4; this.face[RIGHT] = 3;
        }
    }
    public Dice(int[] nums) {
        this.face = nums.clone();
    }

    public void rotate(int dir) {
        int temp = face[roll[dir][0]];
        for (int i=0; i<3; i++) {
            face[roll[dir][i]] = face[roll[dir][i+1]];
        }
        face[roll[dir][3]] = temp;
    }

    static void swap(Dice d1, Dice d2) {
        for (int i=0; i<6; i++) {
            int temp = d1.face[i];
            d1.face[i] = d2.face[i];
            d2.face[i] = temp;
        }
    }

    public boolean equals(Dice d) {
        return  this.face[TOP] == d.face[TOP] && this.face[BOTTOM] == d.face[BOTTOM]
            && this.face[FRONT] == d.face[FRONT] && this.face[BACK] == d.face[BACK]
            && this.face[LEFT] == d.face[LEFT] && this.face[RIGHT] == d.face[RIGHT];
    }

    public String toString() {
        return Arrays.toString(face);
    }

    @Override
    public Dice clone() {
        return new Dice(this.face);
    }
}

2016-04-25

AOJ 2005: Water Pipe Construction

AOJ

問題

Water Pipe Construction | Aizu Online Judge

解法

ある点tについて、min{(sからtまでの最短距離) + (tからg1までの最短距離) + (tからg2までの最短距離)}が求めるべき答えなので、tを全探索。
全点対最短距離を求めるのはワーシャルフロイドでもなんでもいい。

import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class AOJ2005 {

    static final Scanner in = new Scanner(System.in);
    static final PrintWriter out = new PrintWriter(System.out,false);
    static boolean debug = false;

    public static int[][][] directedGraph(int n, int[] s, int[] t, int[] cost) {
        int[] cnt = new int[n];
        for (int i : s) cnt[i]++;

        int[][][] g = new int[n][][];
        for (int i=0; i<n; i++) g[i] = new int[cnt[i]][2];
        for (int i=0; i<s.length; i++) {
            int from = s[i];
            int to = t[i];

            g[from][--cnt[from]][0] = to;
            g[from][cnt[from]][1] = cost[i];
        }

        return g;
    }

    public static long[] dijkstra(int[][][] g, int source) {
        int n = g.length;

        final long[] d = new long[n];
        Arrays.fill(d, Integer.MAX_VALUE/2);
        d[source] = 0;

        TreeSet<Integer> pQ = new TreeSet<Integer>(new Comparator<Integer>(){
            public int compare(Integer a, Integer b) {
                if (d[a] != d[b]) return d[a] > d[b] ? 1 : -1;
                return a > b ? 1 : -1;
            }
        });
        pQ.add(source);

        while (!pQ.isEmpty()) {
            int cur = pQ.pollFirst();

            for (int i=0; i<g[cur].length; i++) {
                int next = g[cur][i][0];
                long dist = d[cur] + g[cur][i][1];
                if (dist < d[next]) {
                    pQ.remove(next);
                    d[next] = dist;
                    pQ.add(next);
                }
            }
        }

        return d;
    }

    static boolean solve() {
        int n = in.nextInt();
        int m = in.nextInt();
        int s = in.nextInt() - 1;
        int g1 = in.nextInt() - 1;
        int g2 = in.nextInt() - 1;
        if (n + m == 0) return false;

        int[] v1 = new int[m];
        int[] v2 = new int[m];
        int[] c = new int[m];
        for (int i=0; i<m; i++) {
            v1[i] = in.nextInt() - 1;
            v2[i] = in.nextInt() - 1;
            c[i] = in.nextInt();
        }

        int[][][] g = directedGraph(n, v1, v2, c);
        long[] ds = dijkstra(g, s);

        long ans = ds[g1] + ds[g2];

        for (int i=0; i<n; i++) {
            if (i == s) continue;
            long[] d = dijkstra(g, i);
            ans = Math.min(ans, ds[i] + d[g1] + d[g2]);
        }

        out.println(ans);

        return true;
    }



    public static void main(String[] args) {
        debug = args.length > 0;
        long start = System.currentTimeMillis();

        while(solve());
        out.flush();

        long end = System.currentTimeMillis();
        dump((end-start) + "ms");
        in.close();
        out.close();
    }

    static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

2016-04-25

AOJ 1174: Identically Colored Panels Connection

AOJ

AOJ-ICPCの350を埋めようと思う。

問題

Identically Colored Panels Connection | Aizu Online Judge

解法

パネルの変更の仕方を全探索する。実装でハマらなければ簡単。
DFSでカウントしていったけどBFSのほうが楽だった気がする。

import java.util.*;
import java.io.*;
import java.awt.geom.*;
import java.math.*;

public class AOJ1174 {

    static final Scanner in = new Scanner(System.in);
    static final PrintWriter out = new PrintWriter(System.out,false);
    static boolean debug = false;

    static int h, w, c;
    static int[] change;
    static int[][] p, stamp;

    static int[] dx = { 0, 1, 0,-1};
    static int[] dy = { 1, 0,-1, 0};

    static int rec(int y, int x, int pos) {
        int res = stamp[y][x] == 6 ? 1 : 0;
        stamp[y][x] = pos;
        for (int k=0; k<4; k++) {
            int ny = y + dy[k];
            int nx = x + dx[k];
            if (ny < 0 || nx < 0 || h <= ny || w <= nx) continue;
            int ptmp = pos;
            while (ptmp < 6 && change[ptmp] != p[ny][nx]) ptmp++;
            if (stamp[ny][nx] <= ptmp) continue;
            res += rec(ny, nx, ptmp);
        }
        return res;
    }

    static boolean solve() {
        h = in.nextInt();
        w = in.nextInt();
        c = in.nextInt();
        if (h + w + c == 0) return false;

        p = new int[h][w];

        for (int i=0; i<h; i++) {
            for (int j=0; j<w; j++) {
                p[i][j] = in.nextInt();
            }
        }

        int ans = 0;

        for (int i=1; i<=6; i++) {
            for (int j=1; j<=6; j++) {
                for (int k=1; k<=6; k++) {
                    for (int l=1; l<=6; l++) {
                        change = new int[]{p[0][0], i, j, k, l, c};

                        stamp = new int[h][w];
                        for (int m=0; m<h; m++) {
                            Arrays.fill(stamp[m],6);
                        }
                        ans = Math.max(ans, rec(0, 0, 0));
                    }
                }
            }
        }

        out.println(ans);

        return true;
    }

    public static void main(String[] args) {
        debug = args.length > 0;
        long start = System.currentTimeMillis();

        while(solve());
        out.flush();

        long end = System.currentTimeMillis();
        dump((end-start) + "ms");
        in.close();
        out.close();
    }

    static void dump(Object... o) { if (debug) System.err.println(Arrays.deepToString(o)); }
}

2016-02-20

iTerm2 v3 BetaにしたらSublime Terminalから開けなくなった

Sublime Text

ずっとターミナル.appを使ってきたんだけれど、iTermが良いと聞くので移行してみた。
せっかくなのでversion 3のBeta版にしてみたが、Sublime TextのTerminalパッケージから開けなくて少し困った。

公式によるとUser Settingsに

{
  "terminal": "iTerm.sh"
}

を追加するだけで起動できるとのことなんだけれどもうまくいかない(version 3より前では正しく動作するらしい)。
このままだと不便だしversion 3をやめようかと思ったら、この問題を解決した人を発見した。

iTerm.sh · GitHub

このコードをcloneなり何なりしてきて~/Library/Application Support/Sublime Text 3/Packages/Terminal/iTerm.shと置き換えれば問題なく起動できるようになる。
上記のUser Settingsも忘れないようにする。

よかったよかった。

2015-12-24

競プロ&CTFを同時にする！YEHD2015を開催した。

先日、Year End's HackDay 2015 というイベントを開催した。

YEHD2015は競プロとCTFを同時に行って得点を競うコンテストで、たくさんの方が参加してくれた。
運営委員長兼サーバ担当は3846masaくん、CTF担当はkkrntくん、競プロ担当は僕だった。

ルールはざっくりこんな感じ。

競プロとCTFの問題が一気にでるから好きな順番で解く。
5時間で競プロとCTFの合計得点が最も高い人が優勝。
個人で参加しても、3人までのチームを組んでもok。
各問題ごとにFirst Acceptの人にはその問題の得点が1割増しで与えられる。

競プロの問題は計11問で、今回の作問はすべて僕が行った(テスターもいなかった)。
作問は1人でやるべきではないけれど、サークル内で競プロをやっているのが僕だけだったので許してください＞＜(みんな競プロやろう)。
作った問題は↓に置いてある(Mathjaxが効かないのでTeX記法になっているところは読みづらいかも)。

github.com

普段競プロのみをしている人、普段CTFのみをしている人、どちらもしている人、どちらもしていない人、というように来てくれる方の経験がバラバラだったので問題の難易度をどうするかだいぶ悩んだ。
問題の半分いかないくらいから解いた人数が2人とかになってしまったので、簡単な問題(ABCのAやBくらい)をもっと増やしたほうがよかったかなーって思ってる。

問題

Problem A: クリスマス

全員が解けるような問題として出題した。
${\lceil \frac{N}{M} \rceil}$ を出力してくれれば通る。

Problem B: Cryptographic Message

ヴィジュネル暗号を復号するプログラムを作ってね、という問題。
問題に与えられている定義どおりに文字列を辿りながら変換していくと解が求まる。

当日は暗号化されたPDFのみを与えて、解読しないと問題文が読めないようにしていた。
中身をエディタとかで見て、末尾のほうにある文字列をBase64としてデコードすると問題文が現れる。

Problem C: 優勝者

連想配列などの文字列に数値を対応付けられるデータ構造を使ってカウントしていけば良い。

Problem D: ナイト

わいわい話し合いながら考えてもらえるといいかなと思って出題した問題(残念ながらほとんどの人がチームではなく個人でやっていたのでそうはならなかった)。
実は ${N \geq 5}$ の ${N \times N}$ のマスではナイトは各マスを1度しか訪れずに全てのマスに訪れることができる。
${N = 4}$ のときは16手ですべてのマスに訪れることができ、 ${N = 2,3}$ のときはどうしてもたどり着けないマスが存在する。
Knight's tourとかを聞いたことのある人は瞬殺だったかもしれない。

Problem E: 1cm = 1cm

${a=30,b=24}$ を例にして説明する。
其々を素因数分解すると、 ${a=2 \cdot 3 \cdot 5, b=2^{3} \cdot 3 }$ となる。
${lcm(x,y)=lcm(a,b)=2^{3} \cdot 3^{1} \cdot 5^{1}}$ となる ${(x,y)}$ を求めれば良いとわかるので、
${x=2^{sx} \cdot 3^{tx} \cdot 5^{ux}}$ , ${y=2^{sy} \cdot 3^{ty} \cdot 5^{uy}}$ と表した時に、 ${max(sx,sy)=3 \land max(tx,ty)=1 \land max(ux,uy)=1}$ を満たすような ${(x,y)}$ の個数が解となる。
${(sx,sy)=(3,0),(3,1),(3,2),(3,3),(2,3),(1,3),(0,3)}$ の7通り。
${(tx,ty)=(1,0),(1,1),(0,1)}$ の3通り。
${(ux,uy)=(1,0),(1,1),(0,1)}$ の3通りとなるので、 ${7 \times 3 \times 3 = 63}$ 通りとなる。
あとはこれを実装すればok。

Problem F: 友利奈緒

CTF勢から友利奈緒問を作れという圧力を受けた気がしたので作った問題。
木を全探索をすれば通る。

これもPDFが渡されて、そのままだと問題文が読めないようになっていた。
読めない部分をコピーしてエディタとかに貼り付けると読めるようになる。

Problem G: RGB-Query

画像の特徴色抽出をするコードを書いている時に思いついた問題。
累積和と包除原理を使う、のはずがよく考えたら与えられたものを素直に持っておけば愚直にやって通ってしまう...。制約をもっと厳しくするべきだったと反省。

Problem H: 逆転時計

元ネタはハリーポッターのtime turner(逆転時計)。
情報学を学ぶグレンジャーが留年の危機なので研究費で逆転時計を買ってもらう話。
二分探索+貪欲って感じの問題のつもりでいたら、これも貪欲だけで良いことを指摘されてしまった。区間スケジューリングを知っていれば解ける。

Problem I: ナイト再び

隣接行列を作ってM乗すると解が求まる。繰り返し二乗法を使わないと落ちる。

Problem J: 気まぐれ勇者

終了後の投票では競プロで一番好評だった問題。
想定解法は逆向きにダイクストラ。これは制約を緩くしてあるので、他にもいろいろやりようがあると思う。

Problem K: Non-decreasing Sequence of Longest Increasing Subsequence

ソート過程の最長増加部分列(LIS)の長さを求めていく問題。
愚直に毎回LISを求めようとすると、O(NlogN)のDPでも間に合わない。
まず一回、O(NlogN)のDPでソート前のLISを求める。
このDPは蟻本に載っているように、
dp[i]:=長さがi+1であるような増加部分列における最終要素の最小値
とする。
ソート途中、ソートを行った後半部分は増加列になっているので、(前半部分の非ソート済みのLISの長さ)+(後半部分のソート済みの列の長さ)が各ステップで求めるべきLISの長さになる。

非ソート済みの数の中での最大値(そのステップでソート済みにする数)をxとすると、xを越えない最大の数をDPテーブルから二分探索することで、その値が見つかったインデックス+1が非ソート済みの列でのLISの長さとなる。

反省

解読しないと競プロの問題が読めなかったりと、同時開催ならではの問題もいれることができて良かった。
競プロとCTFの合計得点を同じにしようとしたのは失敗だった。競プロの1問1問に対する得点が大きいので、競プロができる人が無双する感じになってしまった。
たくさんの問題を作るのは良い経験になった。
もっと良い問題を作れるように精進したい。

おわり

参加してくれた皆さんありがとうございました。
運営の皆さんお疲れ様でした。

他の運営者の記事

3846masa.hatenablog.jp

kkrnt.hatenablog.com

t8m8-mem8

競プロとか、学んだことを書いていきます。