SRM 494 DIV2 Easy(250) - InterestingParty

引き続き、最強最速アルゴリズマー養成講座から。
こちらの問題もMapを知っていれば簡単に実装が可能。このレベルならきっちり1問解くことができそう。

Problem Statement

Mr. White is a very versatile person - absolutely everything is interesting to him. Perhaps this is why he has many friends. Quite unfortunately, however, none of his friends are versatile at all. Each of them is interested only in two topics and refuses to talk about anything else. Therefore, each time Mr. White organizes a party, it's a big problem for him to decide whom to invite so that the party is interesting to everybody. Now that Mr. White has a lot of experience in organizing parties, he knows for sure that a party will be interesting if and only if there's a topic interesting to each of the invited friends. You will be given Strings first and second. The i-th friend of Mr. White is interested in topics first[i] and second[i]. Return the largest number of friends that Mr. White can invite to his party so that the party will be interesting.

Definition

  • Class: InterestingParty
  • Method: bestInvitation
  • Parameters: String, String
  • Returns: int
  • Method signature: int bestInvitation(String first, String[] second) (be sure your method is public)

Limits

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

Constraints

  • first will contain between 1 and 50 elements, inclusive.
  • second will contain the same number of elements as first.
  • Each element of first and second will contain between 1 and 15 characters, inclusive.
  • Each character in first and second will be a lowercase letter ('a'-'z').
  • For each valid i, first[i] will not be the same as second[i].

Solution

import java.util.HashMap;
import java.util.Map;

public class InterestingParty {

    public int bestInvitation(String[] first, String[] second) {
        Map<String, Integer> interests = new HashMap<String, Integer>();
        for (int i = 0; i < first.length; i++) {
            interests.put(first[i], 0);
            interests.put(second[i], 0);
        }

        for (int i = 0; i < first.length; i++) {
            interests.put(first[i], interests.get(first[i]) + 1);
            interests.put(second[i], interests.get(second[i]) + 1);
        }

        int max = 0;
        for (Map.Entry<String, Integer> i : interests.entrySet()) {
            max = Math.max(max, i.getValue());
        }
        return max;
    }

}

SRM 478 DIV2 Easy(250) - KiwiJuiceEasy

TopCoderに参戦するにあたって、まずは雰囲気をつかむため最強最速アルゴリズマー養成講座を読んで第4章の一番最初に取り上げられているSRM 478 DIV2 Easy(250)のコードを書いてみた。
この問題なら確かに著者の高橋直大さんが書いている通り、何か特別な知識がなくとも解ける。

Problem Statement

Taro has prepared delicious kiwi fruit juice. He poured it into N bottles numbered from 0 to N-1. The capacity of the i-th bottle is capacities[i] liters, and he poured bottles[i] liters of kiwi juice into this bottle. Now he wants to redistribute juice in the bottles. In order to do this, he will perform M operations numbered from 0 to M-1 in the order in which he will perform them. For the i-th operation, he will pour kiwi juice from bottle fromId[i] to bottle toId[i]. He will stop pouring when bottle fromId[i] becomes empty or bottle toId[i] becomes full, whichever happens earlier. Return an int that contains exactly N elements and whose i-th element is the amount of kiwi juice in the i-th bottle after all pouring operations are finished.

Definition

  • Class: KiwiJuiceEasy
  • Method: thePouring
  • Parameters: int, int, int, int
  • Returns: int
  • Method signature: int thePouring(int capacities, int bottles, int fromId, int[] toId) (be sure your method is public)

Limits

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

Constraints

  • capacities will contain between 2 and 50 elements, inclusive.
  • Each element of capacities will be between 1 and 1,000,000, inclusive.
  • capacities and bottles will contain the same number of elements.
  • For each i, bottles[i] will be between 0 and capacities[i], inclusive.
  • fromId will contain between 1 and 50 elements, inclusive.
  • fromId and toId will contain the same number of elements.
  • Each element of fromId and toId will be between 0 and N-1, inclusive, where N is the number of elements in capacities.
  • For each i, fromId[i] and toId[i] will be distinct.

Solution

public class KiwiJuiceEasy {

    public int[] thePouring(int[] capacities, int[] bottles, int[] fromId, int[] toId) {
        for (int i = 0; i < fromId.length; i++) {
            if (capacities[toId[i]] > bottles[fromId[i]] + bottles[toId[i]]) {
                bottles[toId[i]] += bottles[fromId[i]];
                bottles[fromId[i]] = 0;
            } else {
                bottles[fromId[i]] -= capacities[toId[i]] - bottles[toId[i]];
                bottles[toId[i]] = capacities[toId[i]];
            }
        }
        return bottles;
    }

}