Hatena::Grouptopcoder

TopCoder戦記

研究開発者・ellerのTopCoder挑戦記録。言語は主にJavaを使用しています。ドキュメンテーションコメントはSubmit完了後、ブログ掲載前に補完したものです。

2011-04-15

SRM467 Div2 Easy

| 23:00

以前Javaで書いた解答はこちら

メモ化なし

calculate :: Integer -> Integer -> Integer
calculate 0 n = n
calculate k n = sum $ map (calculate (k - 1)) [1..n]

main = print $ calculate 14 13

メモ化あり

参考:http://www.haskell.org/haskellwiki/Memoization

2引数関数をメモ化するのはややこしそうだったので、ビットシフトを使って1引数に2引数分の情報を持たせることに。

compress_shift = 16

calculate :: Int -> Int -> Int
calculate k n = calc $ compress k n
  where compress k n = k * compress_shift + n

calc :: Int -> Int
calc = let calc' c
             | c < compress_shift = c
             | otherwise          = sum $ map (calculate ((take_k c) - 1)) [1..(take_n c)]
       in (map calc' [0..] !!)
       where take_k c = c `div` compress_shift
             take_n c = mod c compress_shift

main = print $ calculate 14 13

2011-04-14

SRM348 Div2 Easy

| 08:38

Google Code Jam Japan 2011にエントリー→フツーに予選落ちの予感→フツーに参加しても面白くないんじゃね?→そうだHaskellにしよう!

Haskellは私の「今年の言語」なのだが、なかなか使う機会がなかったので言語のキャッチアップを兼ねようという魂胆。ということでしばらくの間、以前Javaで解いた問題をHaskellで解き直してみる。今回はこれ


解法1

文字列置換と再帰を用いた解法。まずソートして"NS"を空文字列に置換、その後headとlastがそれぞれ'E','W'ならばそれを取り除いていく。

ガードを使用しており個人的にはHaskellっぽくない*1印象。replace関数の引数は第1引数にtargetを持ってきたかったのだが、部分適用を用いるために最後に定義することにした。無名関数を使えば第1引数でも大丈夫なんだろうとは思う。

import System
import Data.List
import Text.Regex.Posix

optimize :: String -> String
optimize cs = removeEW . removeNS $ sort cs
  where
    removeEW :: String -> String
    removeEW s
      | hl == "EW" = removeEW $ init $ tail s
      | otherwise  = s
        where hl = [head s, last s]
    removeNS :: String -> String
    removeNS s = replace "NS" "" s

replace :: String -> String -> String -> String
replace pattern new target 
  | match == "" = target
  | otherwise   = head ++ new ++ replace pattern new tail
  where
    (head, match, tail) = target =~ pattern

main = getArgs >>= putStrLn . optimize . concat

解法2

まず'E','N','S','W'それぞれの文字数をカウントして、必要な文だけ文字をreplicateしてやる。++にHaskellっぽくない印象を感じるものの個人の趣味の範囲か。解放1より断然シンプル。

whereに同じコードが4つも出てくるのでまとめてしまいたいが、Haskellでどうやるのかが謎。Javaならfor (char c : "ENSW".toCharArray())とかの採用を検討するところだが。

import System

optimize :: String -> String
optimize cs = 
  replicate (e - w) 'E' ++ replicate (n - s) 'N' ++ 
  replicate (s - n) 'S' ++ replicate (w - e) 'W'
  where
    e = length $ filter (== 'E') cs
    n = length $ filter (== 'N') cs
    s = length $ filter (== 'S') cs
    w = length $ filter (== 'W') cs

main = getArgs >>= putStrLn . optimize . concat

*1:「ただし」とか場合分け定義とかが数式に出てくるのは好きじゃない派、なんか流れがぶった切られる感じ

2010-05-16

SRM348 Div2 Easy

| 10:43

http://www.topcoder.com/stat?c=problem_statement&pm=7752&rd=10672

『祖母が教えてくれた道順には無駄がある。辞書順に最も小さい最短経路を求めよ。』

特にコメントなし。使用する文字は最大でも2種類ですので、辞書順に小さい解は容易に求めることができます。

public class OptimalList {
	public String optimize(String inst) {
		int ew = 0;
		int ns = 0;
		for (int i = 0; i < inst.length(); ++i) {
			switch (inst.charAt(i)) {
			case 'W': ew++; break;
			case 'E': ew--; break;
			case 'N': ns--; break;
			case 'S': ns++; break;
			}
		}

		final StringBuilder answer = new StringBuilder();
		for (int i = 0; ew < i; --i) {
			answer.append('E');
		}
		for (int i = 0; ns < i; --i) {
			answer.append('N');
		}
		for (int i = 0; ns > i; ++i) {
			answer.append('S');
		}
		for (int i = 0; ew > i; ++i) {
			answer.append('W');
		}
		return answer.toString();
	}
}

2010-05-04SRM469 DIV2

SRM469 DIV2 Easy

| 23:21

http://www.topcoder.com/stat?c=problem_statement&pm=10899&rd=14152

『列数n、列あたりの座席数mの映画館がある。予約されている座席を考慮した場合、2人で並んで座れる場所はいくつあるか。』

最近の練習で、この手のグラフィカルに考えられるアルゴリズムでは省メモリで綺麗な実装を目指すよりも、直感的でバグが入りにくいコードを書いた方が総合的な時間の節約になることに気づきました。nやmが大きくない=メモリ制限にひっかからない事を確認し、手早く実装。バグの余地が無いコードを実現できました。

public class TheMoviesLevelOneDivTwo {
	public int find(int n, int m, int[] row, int[] seat) {
		final boolean[][] field = new boolean[n][m];
		for (int i = 0; i < row.length; ++i) {
			field[row[i] - 1][seat[i] - 1] = true;
		}

		int count = 0;
		for (int i = 0; i < field.length; ++i) {
			for (int j = 0; j < field[i].length - 1; ++j) {
				if (field[i][j] || field[i][j + 1]) continue;
				++count;
			}
		}
		return count;
	}
}

2010-04-25

Member SRM468 Div2 Easy

| 16:22

http://www.topcoder.com/stat?c=problem_statement&pm=10764&rd=14183

『電車と飛行機を使い目的地へ向かう。飛行機を使える回数が制限されるとき、最速でどのくらいの時間がかかるか求めよ。』

電車と飛行機について所要時間の差を求め、その差が大きい区間から優先的に飛行機を使用しました。

import java.util.Arrays;

public class RoadOrFlightEasy {
	public int minTime(int N, int[] roadTime, int[] flightTime, int K) {
		final int maxTime = sumOf(roadTime);
		final int[] diff = diffOf(roadTime, flightTime);
		Arrays.sort(diff);
		
		int time = maxTime;
		for (int i = 0; i < K; ++i) {
			if (diff[i] >= 0) break;
			time += diff[i];
		}
		return time;
	}

	private int[] diffOf(int[] roadTime, int[] flightTime) {
		final int[] result = new int[roadTime.length];
		for (int i = 0; i < result.length; ++i) {
			result[i] = flightTime[i] - roadTime[i];
		}
		return result;
	}

	private int sumOf(int[] roadTime) {
		int sum = 0;
		for (int value : roadTime) {
			sum += value;
		}
		return sum;
	}
}