Hatena::Grouptopcoder

ぷろこんメモ用紙

 | 

2011-03-21

Codeforces Unknown Language Round #2

21:13

直前まで言語が発表されないマイナー言語コンテストの2回目。

今回はIo。開始前に処理系の7zアーカイブが配布されて、すぐに環境を整えられたのがよかった。

結果は7問解いて26位。知ってる人は軒並み上位にいるのでちょっと悔しい。

初動

IoってあからさまにGooglability低いからダメだろうなーと思いつつぐぐってやっぱりロクな情報が得られなかったので、アーカイブに同梱されていたドキュメントを頼りに進める。

幸いにもtutorialがあったので適当に流し読み。ふむ、メッセージを後置するオブジェクト指向型の言語なのね。

で、これ標準入力どうするの……。とりあえずgetlineかreadかそんなメソッド名だろうと推測し、samplesディレクトリでgrep掛けると

input := File standardInput
while (line := input readLine,

がsamples/shootout/reverse-complement.ioに見つかったので流用。

A Goshtasp, Vishtasp and Eidi

nが与えられて素数の和で表す。複数の候補があればlexicographically latestなものを出せと言っている……。

ゴールドバッハ予想があったから素数の和への分解はn≤10000なら絶対できるはずだけど、これって一意に定まるんだっけ?と悩んで放置。

G Fibonacci army

なんかAが妙に重いなーと思って問題一覧を見たら、Gが解答人数多いし名前も簡単そう……。

n番目のフィボナッチ数を計算すればいいっぽい。やるだけ。

f := File standardInput
n := f readLine asNumber

prev := 1
ans := 1
for(a, 2, n,
	tmp := ans
	ans := ans + prev
	prev := tmp)
ans println

C Extraordinary Nice Numbers

次に解答人数が多い問題へ。

奇数の約数の個数と偶数の約数の個数が同じかどうか判定する問題らしい。これfilterかselectがあれば一発だなーと思ってドキュメント見たらselectがあるらしい。じゃあやるだけ。

1〜nのリストを作るのにRangeとかあるかと思ったけどよく判らないので安直にrepeatで作る。

この頃はselectのoptionalIndexが省略できるの知らなくてiとか書いてる……。

f := File standardInput
n := f readLine asNumber

list := List clone
n repeat(a, list append (a+1))
list := list select(i, v, n % v == 0)
odds := list select(i, v, v isOdd) size
evens := list select(i, v, v isEven) size
if(odds == evens) then("yes" println) else("no" println)

H Reverse It!

最大1000桁の数値をひっくり返せばいいらしい。ひっくり返す前、後それぞれでleading zeroを削除する、と。

正規表現使えば簡単だけど使い方が不明なのでループで削っていく。

……WA。-0とか来るのかと思っていろいろ試すも通らない。うーむ。とりあえず放置しよう。

次のGoofy Numbersを解いてから戻ってくる。これもしかして向こうのサーバ固有のエラーじゃないか……と思ってCustom Testに投げてみる。と、なんかエラー出た!

文字列を削るのに使っていたinclusiveSliceというのが存在しないらしい。なんだそれ。よく見るとCodeforcesのIoと手元のIoでバージョンが違う……。手元のドキュメントだとdeprecatedになっているsliceというメソッドを使わないといけないらしい。ひどい……。

f := File standardInput
line := f readLine 
neg := false
if(line at(0) asCharacter == "-", 
	neg := true
	line := line slice(1))

while(line at(0) asCharacter == "0",
	line := line slice(1)
	if(line == "", break))

if(line == "") then(line := "0") else(
		line := line reverse
		while(line at(0) asCharacter == "0",
			line := line slice(1))
		if(neg, line := "-" .. line))
line println

I Goofy Numbers

正整数nが与えられて、各桁の数字でnが割り切れるかどうかを判定する。

Project eulerにあったような。とりあえずやるだけ。

foreachでSequenceを回すとASCIIコードになってしまうのがちょっと面倒。

f := File standardInput
line := f readLine

happy := false
happier := true
n := line asNumber
line foreach(v,
	digit := v asCharacter asNumber
	if(n % digit == 0) then(happy := true) else(happier := false))

if(happier) then("happier" println) else(if(happy) then("happy" println) else("upset" println))

F Oil

残ったB,D,E,Fを見て、明らかにBとDは実装が重いのでEとFを解くことに決定。

グリッドが与えられて、列と行を塗り潰して、残ったマスがいくつのシマになっているか数える問題。

残った行、列をそれぞれくっつけられるだけくっつけて掛ければ終わり。

もうちょっと綺麗に書けそうだなーと思いつつベタ書きした。

f := File standardInput
arr := f readLine split map(v, v asNumber)
n := arr at(0)
m := arr at(1)
rows := List clone
cols := List clone
for(i, 1, n, rows append(i))
for(i, 1, m, cols append(i))

ts := f readLine split map(v, v asNumber)
ts removeAt(0)
ts foreach(v, rows remove(v))

ss := f readLine split map(v, v asNumber)
ss removeAt(0)
ss foreach(v, cols remove(v))

rc := 1
for(i, 1, rows size - 1,
	if(rows at(i) - rows at(i-1) > 1, rc := rc+1))
cc := 1
for(i, 1, cols size - 1,
	if(cols at(i) - cols at(i-1) > 1, cc := cc+1))

if(rows size == 0 or cols size == 0) then(0 println) else((rc*cc) println)

E Ali goes shopping

文字列Aが与えられて、Aの部分文字列のうちAの中で一番多く出現しているものを探す問題。

全探索するだけ。最初、出現は連続していないといけないのかと思って違うコード書いてた。

あとnotをどう書くのかでちょっと悩んだ。

f := File standardInput
line := f readLine

ans := line clone
rep := 1
for(len, 1, line size,
	for(start, 0, line size - len,
		pat := line slice(start, start+len)
		cnt := 0
		pos := line findSeq(pat)
		while(pos isNil not,
			cnt := cnt+1
			pos := line findSeq(pat, pos+1))
		if(cnt > rep or (cnt == rep and (pat size > ans size or (pat size == ans size and pat > ans))),
			ans := pat
			rep := cnt)))

ans println

B INI-file

Dはパーサ書く問題ぽくて面倒そうだったので放置。

Iniファイルを読み込んで、セクション順→キー名順に出力する問題。

クラス定義してcompareを自分で書いて……とやったらなんだか変な挙動を示したのでsortByを使って通した。あとsectionのstripに気づかなくて1WA。

Entry := Object clone
#Entry compare := method(other, 
#	if(self section != other section) then((self section compare(other section))) else((self name compare(other name))))

f := File standardInput
n := f readLine asNumber

section := ""
list := List clone
n repeat(
	line := f readLine strip
	if(line at(0) asCharacter == ";", continue)
	if(line at(0) asCharacter == "[") then(
		section := line slice(1, line size-1) strip
		entry := Entry clone
		entry name := ""
		entry section := section
		list append(entry)
	) else(
		eql := line findSeq("=")
		name := line slice(0, eql) strip
		value := line slice(eql+1) strip
		entry := nil
		list foreach(e, 
			if(e name == name and e section == section, 
				entry := e
				break))
		if(entry isNil,
			entry := Entry clone
			list append(entry))
		entry name := name
		entry value := value
		entry section := section
	)
)

list := list sortBy(block(a, b, 
	if(a section != b section) then(return a section < b section) else(return a name < b name)))

prevsec := ""
list foreach(e,
	if(e section != prevsec,
		writeln("[",e section,"]")
		prevsec := e section)
	if(e name != "", writeln(e name,"=",e value)))

D Perse-script

パーサ実装問題……かと思いきや、twitterで聞いたところによるとconcatとかreverseとかを定義してからdoStringすれば良かったらしい。気づかなかった……。

 |