Hatena::Grouptopcoder

TopCoder戦記

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

2011-05-18SRM 504.5

久々の参加。

ox- +50 -0 で182.31pt、Ratingは1376に上がりました。

SRM 504.5 Easy

| 00:30

問題文:http://www.topcoder.com/stat?c=problem_statement&pm=11096&rd=14514

このEasyだけは落とすまいとテストケースを相当書きました。今の自分のRatingでは、Mediumを頑張って通すよりもEasyを確実に通してchallengeで稼ぐ方が確実だと考えるためです。

今回はEasyを落とす人が少なかったのでこれだけ通してもあまり嬉しくなかったのですが、方針として大きく誤ってはいないと思うのでしばらくこのEasy死守戦略を続けてみます。

public class TheNumbersWithLuckyLastDigit {
	public int find(int n) {
		if (n < 4 || n == 6 || n == 10)
			return -1;

		switch (n % 10) {
		case 4:
		case 7:
			return 1;
		case 0:
			return 5;
		case 2:
			return 3;
		case 6:
			return 4;
		case 8:
			return 2;
		default:
			if (n % 2 == 1) {
				int k = find(n - 7);
				return k == -1 ? -1 : k + 1;
			}
			return -1;
		}
	}

	// BEGIN CUT HERE
	public static void main(String[] args) {
		TheNumbersWithLuckyLastDigit temp = new TheNumbersWithLuckyLastDigit();
		System.out.println(temp.find(1) == -1);
		System.out.println(temp.find(2) == -1);
		System.out.println(temp.find(3) == -1);
		System.out.println(temp.find(4) == 1);
		System.out.println(temp.find(5) == -1);
		System.out.println(temp.find(6) == -1);
		System.out.println(temp.find(7) == 1);
		System.out.println(temp.find(8) == 2);
		System.out.println(temp.find(9) == -1);
		System.out.println(temp.find(10) == -1);
		System.out.println("===");

		System.out.println(temp.find(11) == 2);
		System.out.println(temp.find(12) == 3);
		System.out.println(temp.find(13) == -1);
		System.out.println(temp.find(14) == 1);
		System.out.println(temp.find(15) == 3);
		System.out.println(temp.find(16) == 4);
		System.out.println(temp.find(17) == 1);
		System.out.println(temp.find(18) == 2);
		System.out.println(temp.find(19) == 4);
		System.out.println(temp.find(20) == 5);
		System.out.println("===");

		System.out.println(temp.find(21) == 2);
		System.out.println(temp.find(23) == 5);
		System.out.println("===");

		System.out.println(temp.find(99) == 4);
		System.out.println(temp.find(11) == 2);
		System.out.println(temp.find(13) == -1);
		System.out.println(temp.find(1234567) == 1);
	}
	// END CUT HERE
}

今回は二重ループで解を求める形が最もシンプルで好ましかったのではと思います。ただループの回数が足りずに撃墜されているケースもあったので、最低でも何回ループするかをきちんと考えることが重要です。下1桁だけ考えればいいことに着目すると、4で終わる数は少なくとも6個以上にならないこと・7で終わる数は少なくとも10個以上にならないことが言えそう*1ですので、以下のような二重ループにすべきだったのでしょう。

	public int find(int n) {
		int result = Integer.MAX_VALUE;
		for (int i = 0; i < 6; ++i) {
			for (int j = 0; j < 10; ++j) {
				if ((i * 4 + j * 7) % 10 == n % 10 && i * 4 + j * 7 <= n && i + j > 0) {
					result = Math.min(result, i + j);
				}
			}
		}
		return result == Integer.MAX_VALUE ? -1 : result;
	}

*1:もっときちっと考えると削れそうですが、計算量的には大差ないのでこれでOKとする

2011-04-17

コードリーディング

| 20:48

GCJは入力の1行目にデータ量、2行目移行に加工対象データが渡されるケースが多そう。こうした入力形式をどう扱えば良いのか、先人のコードを元に考えてみる。こうしてコードを公開してくださっていることに感謝。

<$>とは何か

他の箇所は大体理解できるものの、main関数の定義だけは見慣れない<$>演算子が使われていたためよくわからなかった。ひとつずつ分解してみる。

-- a part of submitted code for A
main = gcjMain solve $ map read . words <$> getLine

<$>演算子はControl.Applicativeで定義されている、fmap関数へのシノニム。わかりやすさのため、fmapに置き換えると以下のようになる。

main = gcjMain solve $ fmap (map read . words) getLine

関数適用の優先順位はどんな演算子の優先順位よりも高いことから、"read . words"よりも"map read"の方が優先的に適用される。

main = gcjMain solve $ fmap ((map read) . words) getLine

$より右の式は「入力から得た文字列を空白で区切って[String]に変換し、その各要素を数値に変換することで[数値]を得る」という意味を持っているように見える。実際の型をghciで調べると以下のようにまだIOモナドの形を保っている=入力未実行なので、この解釈は厳密には誤りであろう。でも雰囲気的にはそんな感じ。「入力をよろしく解釈して[数値]を返すIOモナド」というのが正しいか。

*Main> :t fmap ((map read) . words) getLine
fmap ((map read) . words) getLine :: (Read a) => IO [a]

実際に使ってみる

練習用問題を解いてみる。

この問題ではStringを空白で区切って[String]とし、これをreverseすれば目的の出力が得られそう。空白で区切って逆転させるconvert関数をgetLineにfmapすることで、作用させるだけで出力すべき文字列が得られるIOモナドを作ってみる。

import Control.Monad
import Control.Applicative
import Data.List
import Text.Printf

convert :: String -> String
convert = concat . (intersperse " ") . reverse . words

gcjMain m = do
  n <- readLn
  dat <- replicateM n m
  forM_ (zip [1..n] dat) $ \(i, d) -> do
    printf "Case #%d: %s\n" i d

main = gcjMain $ convert <$> getLine

submitしたところcorrectだった。replicateMとforM_を組み合わせた繰り返しはCodeJamでのパターンになりそう。

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