AtCoder Beginner Contest 113 C – ID についてのメモ

2018年11月18日

今回は備忘録やお試し記事ってやつです。
AtCoderに最近参加してABC(AtCoder Beginner Contest)にたまーに参加して問題を解いているのですが、ABC113-Cでどうして間違っているかわからない問題が出てきてしまったのでteratailにて質問させていただきました。

 

「[Python]AtCoder Beginner Contest 113 のC問題でWAになる理由がわからない」

解答者が間違っている部分を指摘してくれたのですが、いまいち良く分からず、もう少し聞いて見たところ、入力例を教えていただいたのでそれを元に今回はPython3.7でテストして見ようと思います。

問題は文はちょっと著作権的にマズそうなのでURLだけ載せておきます。

AtCoder Beginner Contest 113 C – ID

んで僕が作成したコードはこちら

一応入力例は全て正確な答えが出るのですが、下記みたいな入力を行うと正常に出力されないようです。(この入力例考えてくれた方は天才かな?)

2 3
1 63
2 32
1 12

動作を追うことがちょっと出来ないので少しづつprintしながら動作を確認しようと思います。

とりあえず上記のコードにめっちゃprint文を足したコードはこちらになります。

んで出力はこんな感じになりました。

出力結果

(見やすくするため入力と出力は1行あけました。)
少しずつ見比べていきましょう。
まずは最初の出力です。これは入力した物を一つにまとめ、元の番号を識別するためにキーをつけているわけです。(出力部分1)
次にsortを使って第一要素で並び替えました。(出力部分2)
その後にsortで第二要素を並び替えました(出力部分3)

この部分の出力は
[1, 12, 2]
[2, 32, 1]
[1, 63, 0]
なのですが、これだとその後の識別番号の割り振りで詰みます。

すなわちここでミスってる訳です。

コードの変更

ここで15,17行目のキーの引数を逆にしてあげましょう

ハイライト部分は変更しています。

再実行

んじゃこれで実行してみましょう。

実行結果はこちら

うまく出力できていますね。

ちょこっとだけ考察をすると、今回私が作成したプログラムが正常に動作する条件は、第一要素が昇順になっていることが絶対条件です。

なので、最初に第二要素でソートしてそのあとに第一要素でソートすれば動作条件を満たすことができます。

これが原因で相当な時間ハマってしまいWAの連鎖を生んでしまいました。 皆さんも是非気をつけて見て下さい。

Python

Posted by reud