読者です 読者をやめる 読者になる 読者になる

ichirin2501's diary

いっちりーん。

EPOCH@まつやま 予選通過

ほよほよ(@hoyohoyo000)さんと組んで参加したんだけど、なんか予選通過してたw
チーム名は「0x55」です。
今はもう問題見れないようなので問題文を書いておきます。

1問目 数列の構成は同じ?

いま,1 個以上の正の整数が書き並べられたものを“数列” と呼ぶことにします.例えば,
2, 5, 7, 9, 3
は5 個の正の整数からなる数列です.この数列をX と呼ぶとき,以下のように書くこととします:
X = [ 2, 5, 7, 9, 3 ] .
同様に別の数列Y を考えます:
Y = [ 7, 5, 9, 5, 7, 9, 3, 2 ] .
X とY は,完全一致とはいきませんが,それぞれに登場する整数は同じものになります.つ
まり,どちらも“2, 3, 5, 7, 9” という5 種類の整数だけが登場する数列になっています.上述の
X と Y のように “数列を構成する整数(の集まり)” が同じ場合,これらを 同じ構成の数列
と呼ぶことにします.複数の数列を入力として,その中で同じ構成の数列を見つけ出し,
構成の異なる数列が全部で何種類存在しているのかを出力するプログラムを作成して下さい.
入力では,最初に数列の個数N が一行で与えられます(1<=N<=100000).それに続くN 行
では,一行に一つずつ数列が与えられます.各行では整数が空白文字で区切って与えられ,数列の
終端は − 1 で表されます( − 1 は数列には含まれない).ただし,数列の内容として登場する整数
は1 以上1000 未満とし,個数は256 未満とします.
出力では,構成の異なる数列が全部で何種類存在していたのかを一行で出力して下さい.なお,
行末では改行して下さい.
実行例
【入力】
3
2 5 7 9 3 -1
7 5 9 5 7 9 3 2 -1
2 5 7 9 3 6 -1
【出力】
2


解答:
bitを利用したアルゴリズムで書いた、気がする。

2問目 素数暗号

いま,英文字を素数に置き換えた暗号文を考えます.これは“k 番目の英文字を(小さい方から
数えて)k 番目の素数に置き換える” というものです.ただし,ここでいう素数とは,その数と1
以外では割り切れない正の整数とします.したがって,素数は小さい方から2,3,5,7, · · · とな
り,それらは無限に存在します.また,英文字としては小文字と大文字を考えます.そして,1 番
目から26 番目までを小文字a からz に,27 番目から52 番目までを大文字A からZ にそれぞれ
対応させます.ただし,53 番目以降に関しては,再度1 番目から数え直すことにします.
• 1 番目の素数(= 2) ↔ a
• 2 番目の素数(= 3) ↔ b
· · ·
• 26 番目の素数 ↔ z
• 27 番目の素数 ↔ A
· · ·
• 52 番目の素数 ↔ Z
• 53 番目の素数 ↔ a
· · ·
いくつかの整数が暗号文として与えられたとき,それらを上述のルールに従って順番に英文字に
解読して出力するプログラムを作成して下さい.ただし,与えられた数字が素数でない場合はアン
ダースコア“ ” に対応させて下さい.
入力では,暗号(整数)が一行に一つずつ与えられます.整数の個数に上限は無く,入力の終わ
りは“-1” で表されます.ただし,登場する整数は(-1 を除いて)0 以上10000000 未満です.
出力では,入力と同じ順番で,対応する英文字を出力して下さい.なお,答えは一行で(最後だ
け改行して)出力して下さい.
実行例
【入力】
3
5
1
2
7
-1
【出力】
bc_ad


解答:
この問題関与してないw

3問目 n番目に大きい分数は?

N 個の分数を入力として,その中でn 番目に大きな分数を出力するプログラムを作成して下さ
い.ただし,10<=N<=1000000 とします.また,当然ながら1<=n<=N です.
入力ではまず,一行目にN とn がこの順番に空白文字で区切って与えられます.そして,それ
に続くN 行では,一行に一つずつ分数が“a/b” のかたちで与えられます.(“/” の前後に空白は
入りません.)これは
a
b
を意味します.ただし,a, b ともに − 10000 以上10000 以下の整数であり,なおかつb は0 以外
の整数です.
出力では,n 番目に大きな分数を入力と同じ形式で出力して下さい.(最後に改行も含めて下さ
い.)なお,本問題で与えられるデータに限り,n 番目に大きな分数は必ず一つに決まると考えて
構いません.(つまり,答えの候補が複数登場することはありません.)また,答えの分数は通分せ
ず,符号も含めて入力とまったく同じかたちで出力して下さい.
実行例
【入力】
5 2
3/2
-1/100
5/-20
-50/-100
0/3
【出力】
-50/-100


解答:
整数のままで処理したアルゴリズムだったはず


どのプログラムも最大ケースで8秒前後だったと思う。
なんでこれで予選通過したのかよくわからんw
topcoder的には全部2秒ぐらいで終了しないとまずいんじゃないのw