TopCoder初参戦に向けて - SRM 698

いよいよ9/18のSRM 698にてTopCoderに初参戦する予定です。 ここでは初参戦に向けた目標と現状、参戦までに取り組むことをまとめておきます。

目標

  • Coding Phase：SRM 698 DIV2のEasy問題を正答すること
  • Challenge Phase：今回は特に目標を設けない

現状

最強最速アルゴリズマー養成講座に沿って、TopCoderの問題を回答するにあたって必要な知識やテクニックを学習中。 DIV2 Easy問題であれば時間が多少かかったとしても解けてはいるので、本番でも落ち着いて解ければ問題ないのではないかなという印象。 一方で、DIV2 Medium問題はこれまでに1問しか解けていないが、プログラムの方針立ての時点でどのように進めていけばよいのかすらわからず、こちらは解けるようになるにはもう少々時間がかかりそうな見込み。

参戦までに取り組むこと

引き続き最強最速アルゴリズマー養成講座を教本にして、TopCoderの問題を回答するために必要な知識やテクニックの学習をすすめる。特に全探索にかかる解説は一通り問題を解き、内容を理解しておく。

SRM 436 DIV2 Easy(250) - FriendScore

解くには解けたが、かなり遠回りなコードを書いてしまった。 考えた全探索のロジックは以下の通り。

  1. 探索対象を1人決める（= friends[i]）
  2. 探索対象の友達を検索（= friends[i].charAt(j)がYとなる人）
  3. 探索対象の2で抽出した友達以外の友達を検索（= friends[i].charAt(k) ただし、k > j）
  4. 2, 3で抽出された人をそれぞれ友人に設定

Problem Statement

You want to determine the most popular person in a social network. To do this, you will count the number of "2-friends" that each person has. Person A is called a 2-friend of another person B if they are friends with each other or if there exists some person C who is a friend of both A and B. The most popular person is the person with the highest number of 2-friends. (There might be more than one if multiple people all have the maximal number of 2-friends.)

You are given a String friends, where the j-th character of the i-th element is 'Y' if person i and person j are friends, and 'N' otherwise. Return the number of 2-friends of the most popular person in this social network.

Definition

  • Class: FriendScore
  • Method: highestScore
  • Parameters: String
  • Returns: int
  • Method signature: int highestScore(String[] friends) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Constraints

  • friends will contain between 1 and 50 elements, inclusive.
  • Each element of friends will contain exactly N characters 'Y' or 'N', where N is the number of elements in friends.
  • For each i and j, friends[i][j] will be equal to friends[j][i].
  • For each i, friends[i][i] will be equal to 'N'. 

public class FriendScore {

    public int highestScore(String[] friends) {
        String[] ret = new String[friends.length];
        for (int i = 0; i < friends.length; i++) {
            ret[i] = friends[i];
        }

        for (int i = 0; i < friends.length; i++) {
            for (int j = 0; j < friends[i].length(); j++) {
                if (friends[i].charAt(j) == 'Y') {
                    for(int k = j + 1; k < friends[i].length(); k++) {
                        if (friends[i].charAt(k) == 'Y') {
                            ret[j] = ret[j].substring(0, k) + "Y" + ret[j].substring(k + 1, ret[j].length());
                            ret[k] = ret[k].substring(0,  j) + "Y" + ret[k].substring(j + 1, ret[k].length());
                        }
                    }
                }
            }
        }

        int max = 0;
        for (int i = 0; i < friends.length; i++) {
            int count = 0;
            for (int j = 0; j < friends[i].length(); j++) {
                if (ret[i].charAt(j) == 'Y') {
                    count++;
                }
            }
            max = Math.max(max, count);
        }
        return max;
    }

}

SRM 428 DIV2 Easy(250) - ThePalindrome

回文を作る最小の文字列長を求める問題。

Problem Statement

John and Brus are studying string theory at the university. Brus likes palindromes very much. A palindrome is a word that reads the same forward and backward. John would like to surprise Brus by taking a String s, and appending 0 or more characters to the end of s to obtain a palindrome. He wants that palindrome to be as short as possible. Return the shortest possible length of a palindrome that John can generate.

Definition

  • Class: ThePalindrome
  • Method: find
  • Parameters: String
  • Returns: int
  • Method signature: int find(String s) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Constraints

  • s will contain between 1 and 50 characters, inclusive.
  • Each character of s will be a lowercase letter ('a' - 'z').

Solution

public class ThePalindrome {

    public int find(String s) {
        for (int i = s.length(); i < 2 * s.length(); i++) {
            boolean isPalidromes = true;
            for (int j = 0; j < s.length(); j++) {
                if ((i - j - 1) < s.length() && s.charAt(j) != s.charAt(i - j - 1)) {
                    isPalidromes = false;
                    break;
                }
            }
            if (isPalidromes) return i;
        }
        return -1;
    }

}

SRM 150 DIV2 Easy(250) - WidgetRepairs

SRM 150 DIV2 Medium(500) - InterestingDigitsを解いたので、ついでにEasy問題も解いてみた。 この問題は、前日までの積み残し（rest）と当日到着分(arrivals[i]）の合計が当日処理可能分（numPerDay）を超えるかどうかを考慮すればOK。 前日までの積み残しと当日到着分の合計が当日処理可能分よりも多い場合は、積み残しが0より大きくなる。 また、前日までの積み残しと当日到着分の合計が当日処理可能分よりも小さい場合は、積み残しが0より小さくなる。この場合は、積み残しは0。 そのため、以下の式で当日の積み残しが計算可能。

rest = Math.max(rest + arrivals[i] - numPerDay, 0);

あとは、最終的に残った積み残し分が何日で処理可能かを計算して足してやればOK。 ただしここで、restもnumPerDayもともにint型であるため、小数点以下が切り捨てられてしまう。よって、そのままでは切り上げ処理ができない。 一度restまたはnumPerDayをdouble型にキャストする必要があることに注意。

operatedDays += Math.ceil((double)rest / numPerDay);

Problem Statement

When a widget breaks, it is sent to the widget repair shop, which is capable of repairing at most numPerDay widgets per day. Given a record of the number of widgets that arrive at the shop each morning, your task is to determine how many days the shop must operate to repair all the widgets, not counting any days the shop spends entirely idle.

For example, suppose the shop is capable of repairing at most 8 widgets per day, and over a stretch of 5 days, it receives 10, 0, 0, 4, and 20 widgets, respectively. The shop would operate on days 1 and 2, sit idle on day 3, and operate again on days 4 through 7. In total, the shop would operate for 6 days to repair all the widgets.

Create a class WidgetRepairs containing a method days that takes a sequence of arrival counts arrivals (of type int) and an int numPerDay, and calculates the number of days of operation.

Definition

  • Class: WidgetRepairs
  • Method: days
  • Parameters: int, int
  • Returns: int
  • Method signature: int days(int[] arrivals, int numPerDay) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Constraints

  • arrivals contains between 1 and 20 elements, inclusive.
  • Each element of arrivals is between 0 and 100, inclusive.
  • numPerDay is between 1 and 50, inclusive.

Solution

public class WidgetRepairs {

    public int days(int[] arrivals, int numPerDay) {
        int rest = 0;
        int operatedDays = 0;
        for (int i = 0; i < arrivals.length; i++) {
            if (rest == 0 && arrivals[i] == 0) continue;
            rest = Math.max(rest + arrivals[i] - numPerDay, 0);
            operatedDays++;

        }
        operatedDays += Math.ceil((double)rest / numPerDay);
        return operatedDays;
    }

}

SRM 150 DIV2 Midium(500) - InterestingDigits

初のMedium問題。さすがにこれまでの問題とは違って難しく感じた。4桁未満のチェックでOKという問題文の設定を見落としていて、実装の方針がたたずギブアップ。解説を読んで4桁未満でokということに気づき、何とか実装をこなした。

Problem Statement

The digits 3 and 9 share an interesting property. If you take any multiple of 3 and sum its digits, you get another multiple of 3. For example, 1183 = 354 and 3+5+4 = 12, which is a multiple of 3. Similarly, if you take any multiple of 9 and sum its digits, you get another multiple of 9. For example, 759 = 675 and 6+7+5 = 18, which is a multiple of 9. Call any digit for which this property holds interesting, except for 0 and 1, for which the property holds trivially.

A digit that is interesting in one base is not necessarily interesting in another base. For example, 3 is interesting in base 10 but uninteresting in base 5. Given an int base, your task is to return all the interesting digits for that base in increasing order. To determine whether a particular digit is interesting or not, you need not consider all multiples of the digit. You can be certain that, if the property holds for all multiples of the digit with fewer than four digits, then it also holds for multiples with more digits. For example, in base 10, you would not need to consider any multiples greater than 999.

Definition

  • Class: InterestingDigits
  • Method: digits
  • Parameters: int
  • Returns: int
  • Method signature: int digits(int base) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Notes

  • When base is greater than 10, digits may have a numeric value greater than 9. Because integers are displayed in base 10 by default, do not be alarmed when such digits appear on your screen as more than one decimal digit. For example, one of the interesting digits in base 16 is 15.

Constraints

  • base is between 3 and 30, inclusive.

Solution

import java.util.ArrayList;
import java.util.List;

public class InterestingDigits {

    public int[] digits(int base) {

        List<Integer> list = new ArrayList<Integer>();
        for (int n = 2; n < base; n++) {
            if (isMultipleOf(n, base)) {
                list.add(n);
            }
        }

        int[] ret = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ret[i] = list.get(i);
        }
        return ret;
    }

    private boolean isMultipleOf(int n, int base) {
        for (int i = 0; i < base; i++) {
            for (int j = 0; j < base; j++) {
                for (int k = 0; k < base; k++) {
                    if (((i * base * base + j * base + k) % n) == 0
                            && (i + j + k) % n != 0) {
                        return false;
                    }
                }
            }
        }
        return true;
    }

}

SRM 480 DIV2 Easy(250) - Cryptography

この問題は読んだ瞬間に一番小さい数を+1した場合は最大になることが直感的に分かった。
したがって、実装もそれに沿った形で行った。
これぐらいの難易度であれば解けそうな雰囲気。簡単そうな問題を選んでくれているのだろうけれど・・・。

Problem Statement

TopCoder Security Agency (TSA, established today) has just invented a new encryption system! This encryption system takes as its input a list of numbers to encrypt.

You work at TSA and your task is to implement a very important part of the encryption process. You are allowed to pick one number in the input list and increment its value by 1. This should be done in such way that the product of all numbers in the list after this change becomes as large as possible.

Given the list of numbers as int numbers, return the maximum product you can obtain. It is guaranteed that the return value will not exceed 262.

Definition

  • Class: Cryptography
  • Method: encrypt
  • Parameters: int
  • Returns: long
  • Method signature: long encrypt(int[] numbers) (be sure your method is public)

Limits

  • Time limit (s): 2.000
  • Memory limit (MB): 64

Constraints

  • numbers will contain between 2 and 50 elements, inclusive.
  • Each element of numbers will be between 1 and 1000, inclusive.
  • The return value will not exceed 2^62.

Solution

import java.util.Arrays;

public class Cryptography {

    public long encrypt(int[] numbers) {
        Arrays.sort(numbers);
        numbers[0] += 1;
        long product = 1;
        for (int i = 0; i < numbers.length; i++) {
            product *= numbers[i];
        }
        return product;
    }

}

【解決済】EclipseCoderからArenaが起動しない（sun.security.validator.ValidatorException: PKIX path building failed）

SRMで少しでも時間を有効に使うためにEclipseCoderというEclipseのSRM用Pluginを使用しています。 操作は非常に簡単で、クラス、メソッドのシグニチャからExampleのテストケースまで自動で生成してくれとても重宝しています。 が、本日このEclipseCoderからArenaを起動しようとすると、以下のエラーが発生しました。

sun.security.validator.ValidatorException: PKIX path building failed:
sun.security.provider.certpath.SunCertPathBuilderException: unable to find valid certification path to requested target

調べてみるとSSLの証明書に関するExceptionのようです。 こちらのブログエントリを参考に証明書を登録して対応したところ問題なく起動しました。 対応内容は以下の通りです。

1. TopCoderのサイトから証明書をダウンロード

ブラウザによって操作方法は異なりますが、Google Chromeの場合は、TopCoderのサイトへ行き、URL表示部の鍵マークをクリック＞詳細＞View certificate＞詳細＞ファイルにコピーで、 DER encoded binary X.509(.CER)を選択してダウンロードを実施する。

2. 証明書の登録

以下のコマンドを実施することで証明書を登録する。

[eclipseのホームディレクトリ]\jre\jre\bin\keytool.exe -import -keystore [eclipseのホームディレクトリ]\jre\jre\lib\security\jssecacerts -file [1でダウンロードしたパス]

3. EclipseからArenaを起動

1, 2を実施することで、TopCoderのサイトが信頼済みサイトとして登録されているので、Arenaが問題なく起動する。

そもそもなぜ急に・・・

上記を実施することで問題なく起動することができるようになったのですが、そもそもの問題としてなぜ急にExceptionを吐いてしまうようになったのでしょうか。信頼済みサイトとして登録しないとアクセスできないのであれば、当初からアクセスできないはずなのですが・・・。SSLや証明書周りはあまり詳しくないので、ここは不明なままです。機会があれば調査してみようと思います。