ラベル ACM/ICPC の投稿を表示しています。 すべての投稿を表示
ラベル ACM/ICPC の投稿を表示しています。 すべての投稿を表示

2013年1月13日日曜日

ACM/ICPCを解くの巻その3~携帯メッセージ~

こんにちは,今回問題はこちらです.

携帯の入力を実装しろってことですね.
今はスマホでフリック操作だから関係ねえよ!と思ったあなた,私もです.

この手の問題はとりあえず辞書が必要ですね.
作ります.


one   = ['.',',','!','?',' ']
two   = ['a','b','c']
three = ['d','e','f']
four  = ['g','h','i']
five  = ['j','k','l']
six   = ['m','n','o']
seven = ['p','q','r','s']
eight = ['t','u','v']
nine  = ['w','x','y','z']
dict = [one,two,three,four,five,six,seven,eight,nine]

こんな感じでしょうか.
次はメインの変換関数です.引数は1行分の数字の列にしました.

流れとしては

for 数字 in 数字列:
  数字が"0"じゃないなら
    辞書から数字の部分を取り出す.
    数字が連続した回数(count)を辞書の長さで割った余りの位置にあるアルファベットを取り出す.
    この文字を仮のアルファベットにする.
    countを1増やす
  数字が"0"なら
    仮のアルファベットを確定して返り値用の文字列の最後に追加する.
    仮のアルファベットをリセットする.
    countもリセットする.

全部終わったら,返り値用の文字列を返す.
こういきます. 詳しくはコードをみてください.

特に難しくもない課題かなあとおもいました.


余談ですが,今回までのような,上からデータを処理していくような問題は,for文で回してindexの値を使うよりも,while文とdeque()を使った方が簡単なんじゃないかと思いました.

ACM/ICPCを解くの巻その2~大賀家の資産~

今回のはこれです。
なんか難しそうですね~(笑)

話によると資産管理をしたいので,いくつかの方法で運用した場合の結果から一番成績がいいものを選びたいらしい,なるほど

ちなみに入力データは
入力はいくつかのデータセットが並んだものである.全体としては以下 のような形式になる.

データセット数(=m)
データセット1の記述
データセット2の記述
...
データセットmの記述
「データセット数」mは100を越えないものとする. 各「データセット」の記述は以下の形式をしている.
初期運用資金量
運用年数
運用方法の種類数(=n)
運用方法1の記述
運用方法2の記述
...
運用方法nの記述
「初期運用資金量」,「運用年数」,「運用方法の種類数」nはいずれも正整数で, 資金量は1億を,運用年数は10を,種類数は100を越えることはない.
各「運用方法」の記述は以下の形式をしている.
単利・複利の別 年利率 毎年の手数料
と書いてある.
最初見た感想は「うわメンドクサソウ.」

私は何を考えたのか「クラス作ってやればいける!」と考えました.
  1. データセットの数でインスタンス作成
  2. それに順々に初期値資金,運用年数を突っ込む
  3. 運用方法の種類でリストかなんかを作って,そこに運用方法を格納
  4. 全部の運用方法を試して保存し,最大を出力
まあ案の定めんどくさかったですが,できました. 詳しくは私のgithubをごらんください.


完成した後に思いついてしまったのですが,これ別にクラスとかいらなかったんじゃないか?
必要なのは,引数に運用方法,初期資金,運用年数,手数料をもって,戻り値に結果の資金を返す関数だけでよかったんじゃない?
なので修正したコードを書いています.近日公開です.

最後に今回から文章の句読点を,.にしました.論文もこの形式なので合わせました.

2012年12月22日土曜日

ACM/ICPCを解くの巻その1~花札シャッフル~

問題はここを見てもらうことで,はしょろうと思います。

さて考えていきましょう。


ふむふむ、とりあえず問題を読むと

  1. 2つの数字がスペースで区切られたデータが並んでいる
  2. "0 0"という文字列がデータの終わり
ってことがわかるのでまあとりあえずそこまで実装してみましょう。
今回は(そしてこれからも)コードはpythonで書きます。

#!/bin/python
#-*-coding:utf-8-*-
f = open("hanahuda.txt")#テキストファイルを読み込み
line = f.readline()#1行読み込む

while line != '0 0':
    print line[:-2]#改行文字(\r\n)が含まれるから、文字列の頭から最後-2番目まで
  line = f.readline()
こんな感じになりそう。
まあ行を分割するのはsplit使えばいいから問題ないでしょう。


data_set = line[:-2].split(' ')
これでここからはこのデータセットを使っていきます。

これが問題文のn, r, p, cに対応しているみたいですね。 n r
p c
p c
.
.
p c
(p cのセットがr個あるみたい)それがいくつもあると、ってなるとそれを判断しなければいけませんね。
簡単にカウンタでも導入してみましょう。
こんな感じでカウンタをセットすればいいはずです。
  • counter == r ならそれは最初の行(= n rの行)だからrを読んで設定する
  • 違うなら、それはp cの行だからcounterを1増やす
コードにすると
#-*-coding:utf-8-*-
f = open("hanahuda.txt")#テキストファイルを読み込み
line = f.readline()#1行読み込む

count = 0
r = 0

while line != '0 0':
    data_set = line[:-2].split(' ')#改行文字(\r\n)が含まれるから、文字列の頭から最後-2番目まで
    if count == r:
        r = data_set[1]#データセットの2番目がr
        count = 0#カウンタをリセットする
        print 'n rの行だよ'
    else:
        print 'p cの行だよ'
        count += 1#カウンタを進める
  line = f.readline()#次の行読み込み


これでOK 次の問題は
  • 1~nの番号のカードの山を作る
これはpythonにはrange関数なんて便利なものがあるのでそれを利用しましょう。ここで気を付けるのはrange関数は引数に自然数nを、返り値に0~(n-1)のリストを返すので1~nが欲しいときは書き方に気を付けなければいけません。
こんな感じ
#-*-coding:utf-8-*-
f = open("hanahuda.txt")#テキストファイルを読み込み
line = f.readline()#1行読み込む

count = 0
n = []#最初は中身のないリストにしておく
r = 0

while line != '0 0':
    data_set = line[:-2].split(' ')#改行文字(\r\n)が含まれるから、文字列の頭から最後-2番目まで
    if count == r:
        r = data_set[1]#データセットの2番目がr
        count = 0#カウンタをリセットする
        n = range(int(data_set[0])+1)[1:]#n+1分のリストをrangeで作ってからそれを0番目からじゃなく1番目から
        print n#デバック用出力
        print 'n rの行だよ'
    else:
        print 'p cの行だよ'
        count += 1#カウンタを進める
  line = f.readline()#次の行読み込み
これでnとrに関しては完了です。いいところまで来ました。
次にpとcについて考えていきましょう。
問題を見ると
  1. 上(数字が多いところから)p-1個のカードを取り出す。
  2. 1の後残った山からc枚カードをとり出す。
  3. 2つの取り出した山を1,2の順に戻す
これはスタックを使えば簡単でしょう。 whileの中に書くとごちゃつくので、外部に関数として作成します。
後、その関数内で、nを参照します。たぶんやっちゃダメでしょうが、やっちゃいます。
#!/bin/python
#-*-coding:utf-8-*-

def shuffle(p, c):
 p_stack = []
 c_stack = []
 
 for i in range(p-1):#まずはp-1個の数字をキューに退避させる
  p_num = n.pop()
  p_stack.insert(0, p_num)
 
 for i in range(c):#次にc個の数字をキューに退避させる
  c_num = n.pop()
  c_stack.insert(0, c_num)
 
 #順番を入れ替えてnに戻してあげる
 n.extend(p_stack)
 n.extend(c_stack)
 print n #デバック用出力コード

f = open("hanahuda.txt")
line = f.readline()

count = 0
r = 0
n = []
while line != '0 0':
 data_set =  line[:-2].split(' ')
 if count == r:
  r = int(data_set[1])
  count = 0
  n = range(int(data_set[0])+1)[1:]
  print n
 else:
  shuffle(int(data_set[0]),int(data_set[1]))
  count += 1
  
 line = f.readline()
これでほぼほぼ完成しました。
問題では、1つのシリーズ (n rから最後の p cまで)が終わった時に一番上のカードを出力せよとのお話なので、それもやっときましょう。関数にしておくと楽です
#!/bin/python
def asnwear(card_list):
    if len(card_list)>0:#もしリストの中身が何かしらあれば最後を出力
        print card_list[-1]
    else:#リストが空なら何もしない
        pass
この関数をn rセットの場合の最初に引数はnで実行しましょう。
あり?最後のシリーズの回答が出てこないぞ?
これは最後は0 0で終了させられちゃうのでn rセットのとこに行かないんですね!
pythonにはwhile文が終了した(あるいは実行されない)ときに実行するelse文を付けられるのでそこでもanswearを実行しましょう。
#!/bin/python
#-*-coding:utf-8-*-

def shuffle(p, c):
 p_stack = []
 c_stack = []
 
 for i in range(p-1):#まずはp-1個の数字をキューに退避させる
  p_num = n.pop()
  p_stack.insert(0, p_num)
 
 for i in range(c):#次にc個の数字をキューに退避させる
  c_num = n.pop()
  c_stack.insert(0, c_num)
 
 #順番を入れ替えてnに戻してあげる
 n.extend(p_stack)
 n.extend(c_stack)

def answear(ans_list):
 if len(ans_list) > 0:
  print ans_list.pop()
 else:
  pass

f = open("hanahuda.txt")
line = f.readline()

count = 0
r = 0
n = []
while line != '0 0':
 data_set =  line[:-2].split(' ')
 if count == r:
  answear(n)
  r = int(data_set[1])
  count = 0
  n = range(int(data_set[0])+1)[1:]
  print n
 else:
  shuffle(int(data_set[0]),int(data_set[1]))
  count += 1
  
 line = f.readline()
else:
 answear(n)
これで完成。
まあ星1つの問題なのでそんなに時間はかからないはずです。
私のコードはgithubにあります。