AtCoder Beginner Contest 205(Rated範囲外)

コンテスト前のレート：2074
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：262位（1600点、103分56秒）

A - kcal

問題

思考過程

1. とりあえずと実装しまってから、がmLあたりと書いてあるのを見てで割る。
2. 誤差がどうのこうのと書いてあるので、としてdouble型になるようにする。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        System.out.println(a * b / 100.0);
    }
}

ここまで0分31秒＋0ペナ。18位。

B - Permutation Check

問題

思考過程

1. ～が何回登場するかをカウントしておく。
2. 登場回数が回でない値が存在したら"No"。全て回なら"Yes"。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] c = new int[n + 1];
        for (int i = 0; i < n; i++) {
            c[sc.nextInt()]++;
        }
        sc.close();

        for (int i = 1; i <= n; i++) {
            if (c[i] != 1) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで1分35秒＋0ペナ。46位。

C - POW

問題

思考過程

1. 基本的にはとの大小を調べるだけだが、が偶数の場合は絶対値の大小を調べる必要がある。
2. が奇数の場合は本当にそのままでよいので、が偶数の場合だけとを絶対値に置き換えて大小を調べる。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        sc.close();

        if (c % 2 == 0) {
            a = Math.abs(a);
            b = Math.abs(b);
        }
        if (a < b) {
            System.out.println("<");
        } else if (a == b) {
            System.out.println("=");
        } else {
            System.out.println(">");
        }
    }
}

ここまで4分08秒＋0ペナ。48位。

D - Kth Excluded

問題

思考過程

1. より大きい値がいいか小さい値がいいかぱっとはよくわからないが、とりあえずとなる を見つけたい。
2. 適当に二分探索したら例１のつ目だけ合わなかったので、等号の有無を変えたりしてみる。
3. サンプルが全部合ったのでとりあえず提出してみてAC。
   　
4. 後からよく考えれば、例えばとなる場合は、からをスキップする分のを足してが答えでよく、となる場合は、さらにもスキップしてにしなければならないので、ソース内コメント部分の判定で問題なかった。

import java.io.PrintWriter;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int q = sc.nextInt();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            long k = sc.nextLong();

            int ok = a.length;
            int ng = -1;
            while (Math.abs(ok - ng) > 1) {
                int mid = (ok + ng) / 2;
                if (a[mid] > k + mid) { // 思考過程2
                    ok = mid;
                } else {
                    ng = mid;
                }
            }
            pw.println(k + ok);
        }
        pw.flush();
        sc.close();
    }
}

ここまで9分33秒＋0ペナ。47位。

E問題は解けず。
から上手く駄目な部分を引いていきたいとは思ったが、～をExcel上に書き並べて引くべきところに色を塗ってみてそれらしくやってみたりしても3割くらいしか通らず。

なお、上記のような嘘でもそれらしいやり方の方針が出てきたのが終了数分前で、提出したのは終了8分後とか。

F - Grid and Tokens

問題

思考過程

1. 行側と列側に分けた二部グラフの最大マッチングを求めるだけでは？と思ったが、以下のように辺を張っても、駒について張られた辺の内つしか使えないという制約を表せておらず、上手くいかない。
   • 始点→各行
   • 各行→各列　※駒について、通り。重複は排除
   • 各列→終点
     　
2. 以下のように、駒を表す点を、始点→各行の間と、各列→終点の間に入れてみると、今度は同じ行や列を複数回使ってしまう。
   • 始点→各駒
   • 各駒→各行
   • 各行→各列　※上記1.と同様
   • 各列→各駒
   • 各駒→終点
     　
3. ここまでもやり方で、駒数、行数、列数とのminを取ったりしてみるが、当然のようにWA。
   　
4. 各駒を、各行→各列の間に入れてやれば、「始点→各行」の部分で行数以内に制限でき、「各駒→各駒」の部分で駒数以内に制限でき、「各列→終点」の部分で列数以内に制限でき、これで各種制約を表すことができた。図は公式解説にもあるので略。
   • 始点→各行
   • 各行→各駒
   • 各駒→各駒
   • 各駒→各列
   • 各列→終点

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        int[] d = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt() - 1;
            b[i] = sc.nextInt() - 1 + h;
            c[i] = sc.nextInt();
            d[i] = sc.nextInt() + h;
        }
        sc.close();

        int hw = h + w;
        int n2 = n * 2;
        // 各行： 0～h-1
        // 各列： h～h+w-1
        // 各駒1：h+w～h+w+n-1
        // 各駒2：h+w+n～h+w+2n-1
        // 始点： h+w+2n
        // 終点： h+w+2n+1
        MaxFlow mf = new MaxFlow(hw + n2 + 2);
        for (int i = 0; i < n; i++) {
            for (int j = a[i]; j < c[i]; j++) {
                for (int j2 = b[i]; j2 < d[i]; j2++) {
                    mf.addEdge(j, hw + i, 1); // 各行→各駒1
                    mf.addEdge(hw + n + i, j2, 1); // 各駒2→各列
                }
            }
            mf.addEdge(hw + i, hw + n + i, 1); // 各駒1→各駒2
        }
        for (int j = 0; j < h; j++) {
            mf.addEdge(hw + n2, j, 1); // 始点→各行
        }
        for (int j2 = h; j2 < hw; j2++) {
            mf.addEdge(j2, hw + n2 + 1, 1); // 各列→終点
        }
        System.out.println(mf.flow(hw + n2, hw + n2 + 1));
    }
}

// 以下ACLを移植したMaxFlow

提出
ここまで87分05秒＋6ペナ。245位。

最終結果：ABCDFの5完1600点、117分05秒、270位、パフォーマンス2060相当
レート変動：2074（Unrated）

Dまではミス覚悟の速度重視がたまたま上手くいっていた。特にDは思考過程の通り結構雑なことをしていたので。

Fが解けたのがだいぶ満足度高い。もしかしたら、フローを使う問題の本番中ACが初だったかもしれない。

Eのようなこともあるので、Excelに数値を並べてエスパーを考えるだけでなく、グラフを描くことで見えてくるものがないか試すことを覚えておく。