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

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

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


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

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を１増やす

コードにすると

#-*-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 次の問題は

• １～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. ２つの取り出した山を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にあります。