今回は備忘録やお試し記事ってやつです。
AtCoderに最近参加してABC(AtCoder Beginner Contest)にたまーに参加して問題を解いているのですが、ABC113-Cでどうして間違っているかわからない問題が出てきてしまったのでteratailにて質問させていただきました。
「[Python]AtCoder Beginner Contest 113 のC問題でWAになる理由がわからない」
解答者が間違っている部分を指摘してくれたのですが、いまいち良く分からず、もう少し聞いて見たところ、入力例を教えていただいたのでそれを元に今回はPython3.7でテストして見ようと思います。
問題は文はちょっと著作権的にマズそうなのでURLだけ載せておきます。
AtCoder Beginner Contest 113 C - ID
んで僕が作成したコードはこちら
N, M = map ( int, input ( ).split ( ) )# N,Mを取得
#初期化
lists = [ ]
#listに要素を追加 後で並び変えるため並び替える前の順番を示すキーを第三要素に挿入しておく
for i in range ( M ):
lists.append ( list ( map ( int, input ( ).split ( ) ) ) + [ i ] )
#第一要素に昇順で並び替えた後、第二要素で昇順に並び替える
lists.sort ( key=lambda x: x[ 0 ] )
lists.sort ( key=lambda x: x[ 1 ] )
# befは前回の第一要素 stateは第一要素での順位
bef = 0
state = 0
retstr = ''
triple = [ ]#第四要素に識別番号を追加したリストの初期化
for i in lists:
if (i[ 0 ] != bef):
bef = i[ 0 ]
state = 1
triple.append ( [ i[ 0 ], i[ 1 ], i[ 2 ], str ( i[ 0 ] ).rjust ( 6, '0' ) + str ( state ).rjust ( 6, '0' ) ] )
else:
state += 1
triple.append ( [ i[ 0 ], i[ 1 ], i[ 2 ], str ( i[ 0 ] ).rjust ( 6, '0' ) + str ( state ).rjust ( 6, '0' ) ] )
triple.sort ( key=lambda x: x[ 2 ] )#第三要素で並び替えて、元の入力に対応した式ベンツ番号の順番に戻す
for i in triple:
print ( i[ 3 ] )#識別番号の出力
一応入力例は全て正確な答えが出るのですが、下記みたいな入力を行うと正常に出力されないようです。(この入力例考えてくれた方は天才かな？)
2 3
1 63
2 32
1 12
動作を追うことがちょっと出来ないので少しづつprintしながら動作を確認しようと思います。
とりあえず上記のコードにめっちゃprint文を足したコードはこちらになります。
N, M = map ( int, input ( ).split ( ) )# N,Mを取得
#初期化
def print_list(lists:[]): #関数を追加
for i in lists:
print(i)
print('//----------------------------------------------//')
lists = [ ]
#listに要素を追加 後で並び変えるため並び替える前の順番を示すキーを第三要素に挿入しておく
for i in range ( M ):
lists.append ( list ( map ( int, input ( ).split ( ) ) ) + [ i ] )
print_list(lists) #追加1
#第一要素に昇順で並び替えた後、第二要素で昇順に並び替える
lists.sort ( key=lambda x: x[ 0 ] )
print_list(lists) #追加2
lists.sort ( key=lambda x: x[ 1 ] )
print_list(lists) #追加3
# befは前回の第一要素 stateは第一要素での順位
bef = 0
state = 0
retstr = ''
triple = [ ]#第四要素に識別番号を追加したリストの初期化
for i in lists:
if (i[ 0 ] != bef):
bef = i[ 0 ]
state = 1
triple.append ( [ i[ 0 ], i[ 1 ], i[ 2 ], str ( i[ 0 ] ).rjust ( 6, '0' ) + str ( state ).rjust ( 6, '0' ) ] )
else:
state += 1
triple.append ( [ i[ 0 ], i[ 1 ], i[ 2 ], str ( i[ 0 ] ).rjust ( 6, '0' ) + str ( state ).rjust ( 6, '0' ) ] )
print_list(triple) #追加4
triple.sort ( key=lambda x: x[ 2 ] )#第三要素で並び替えて、元の入力に対応した式ベンツ番号の順番に戻す
print_list(triple) #追加5
for i in triple:
print ( i[ 3 ] )#識別番号の出力
んで出力はこんな感じになりました。
出力結果
$ python3 c-test.py 2 3 1 63 2 32 1 12 [1, 63, 0] [2, 32, 1] [1, 12, 2] //----------------------------------------------// [1, 63, 0] [1, 12, 2] [2, 32, 1] //----------------------------------------------// [1, 12, 2] [2, 32, 1] [1, 63, 0] //----------------------------------------------// [1, 12, 2, '000001000001'] [2, 32, 1, '000002000001'] [1, 63, 0, '000001000001'] //----------------------------------------------// [1, 63, 0, '000001000001'] [2, 32, 1, '000002000001'] [1, 12, 2, '000001000001'] //----------------------------------------------// 000001000001 000002000001 000001000001
(見やすくするため入力と出力は１行あけました。)
少しずつ見比べていきましょう。
まずは最初の出力です。これは入力した物を一つにまとめ、元の番号を識別するためにキーをつけているわけです。(出力部分1)
次にsortを使って第一要素で並び替えました。(出力部分2)
その後にsortで第二要素を並び替えました(出力部分3)
この部分の出力は
[1, 12, 2]
[2, 32, 1]
[1, 63, 0]
なのですが、これだとその後の識別番号の割り振りで詰みます。
すなわちここでミスってる訳です。
コードの変更
ここで15,17行目のキーの引数を逆にしてあげましょう
lists.sort ( key=lambda x: x[ 1] ) print_list(lists) #追加2 lists.sort ( key=lambda x: x[ 0 ] ) print_list(lists) #追加3
ハイライト部分は変更しています。
再実行
んじゃこれで実行してみましょう。
実行結果はこちら
[1, 63, 0] [2, 32, 1] [1, 12, 2] //----------------------------------------------// [1, 12, 2] [2, 32, 1] [1, 63, 0] //----------------------------------------------// [1, 12, 2] [1, 63, 0] [2, 32, 1] //----------------------------------------------// [1, 12, 2, '000001000001'] [1, 63, 0, '000001000002'] [2, 32, 1, '000002000001'] //----------------------------------------------// [1, 63, 0, '000001000002'] [2, 32, 1, '000002000001'] [1, 12, 2, '000001000001'] //----------------------------------------------// 000001000002 000002000001 000001000001
うまく出力できていますね。
ちょこっとだけ考察をすると、今回私が作成したプログラムが正常に動作する条件は、第一要素が昇順になっていることが絶対条件です。
なので、最初に第二要素でソートしてそのあとに第一要素でソートすれば動作条件を満たすことができます。
これが原因で相当な時間ハマってしまいWAの連鎖を生んでしまいました。 皆さんも是非気をつけて見て下さい。