AtCoder Regular Contest 126

コンテスト前のレート：2034
レート通りのパフォーマンスが得られる順位：330位（1300点、87分42秒）

A - Make 10

問題

思考過程

1. 、、、、の順に作れるだけ作る。
2. なお、については、でが個余った場合しかないため、最大でも個しかできない。

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            long n2 = Long.parseLong(sa[0]);
            long n3 = Long.parseLong(sa[1]);
            long n4 = Long.parseLong(sa[2]);

            long ans = 0;
            // 3+3+4
            long a1 = n3 / 2;
            long a2 = Math.min(a1, n4);
            ans += a2;
            n3 -= a2 * 2;
            n4 -= a2;

            // 4+4+2
            long b1 = n4 / 2;
            long b2 = Math.min(b1, n2);
            ans += b2;
            n4 -= b2 * 2;
            n2 -= b2;

            // 3+3+2+2
            if (n3 >= 2 && n2 >= 2) {
                long c1 = n3 / 2;
                long c2 = n2 / 2;
                long c3 = Math.min(c1, c2);
                ans += c3;
                n2 -= c3 * 2;
            }

            // 4+2+2+2
            if (n4 >= 1 && n2 >= 3) {
                ans++;
                n2 -= 3;
            }

            // 2+2+2+2+2
            ans += n2 / 5;
            System.out.println(ans);
        }
        br.close();
    }
}

ここまで10分57秒＋0ペナ。321位。

B - Cross-free Matching

問題

思考過程

1. 要するに線が交わらないように線分を個選びたいので、線分～を選んだとき、～と～がどちらも狭義単調増加になっている必要がある。
   　
2. 線分をの昇順にソートし、前から順に調べていくことを考える。
3. 「までで線分を個選んだときまで使っている」という状態をと表すと、これは最長増加部分列（LIS）と同じ構造をしている。
   　
4. 同じを複数回使わないように、が同じならの降順でソートする。
5. あらかじめ用意しているLISを貼り付け、のLISになるように手直しする。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        int n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        Obj[] arr = new Obj[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[0]);
            o.b = Integer.parseInt(sa[1]);
            arr[i] = o;
        }
        br.close();

        // aの昇順→bの降順
        Arrays.sort(arr, (o1, o2) -> {
            if (o1.a != o2.a) {
                return o1.a - o2.a;
            }
            return o2.b - o1.b;
        });

        // 以下ほぼライブラリ（int配列向けだったので★の行を手直し）

        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        for (Obj o : arr) { // ★
            int idx = Arrays.binarySearch(dp, o.b); // ★
            if (idx < 0) idx = ~idx;
            dp[idx] = o.b; // ★
        }

        int lis = Arrays.binarySearch(dp, Integer.MAX_VALUE - 1);
        if (lis < 0) {
            lis = ~lis;
            lis--;
        }
        System.out.println(lis);
    }

    static class Obj {
        int a, b;
    }
}

ここまで28分00秒＋0ペナ。259位。

この先は、Cに30分、Dに1時間くらい費やしたがいずれも解けず。

最終結果：ABの2完700点、28分00秒、580位、パフォーマンス1699
レート変動：2034→2005（-29）

最近はもう考えるのを面倒くさがってるからどうしようもない。
C飛ばさなければ解けた可能性がどれくらいあったか・・・。