masamasa1981
@masamasa1981

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

AtCoder ABC326CのWAになる原因が知りたい。

Q&A

Closed

解決したいこと

ABC326C
以下のpythonの回答がWAになります。
https://atcoder.jp/contests/abc326/submissions/49902523

こちらの記事を参考に
しゃくとり法のDequeを使ったバグりにくい実装
しゃくとり法をdequeを使って実装してみたのですが、
入力例では問題ないにも関わらず、test13〜27でWAになります。
原因がわからず、同じような回答をしている方も検索して見つけられなかったので質問させていただきました。
考察としては、
・並び替えて、
・左隣との距離を先に出しておき、dequeの最後に入れていく。
・dequeの合計(=dequeの最初の位置からの距離)がM以上になった場合は、dequeの最初の位置のものをpopleftする。
です。
別のやりかたでACになるのは確認済なのですが、初めに自分で思いついた考察のどこに原因があるのかわからずどうしてもモヤモヤしております。
よろしくお願いいたします。

自分で試したこと

実際のin_test14を試そうとしましたが、(out_test14:5749)
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AADDqsbRZGrRw1i-xjdeNFoxa/abc326/C/in?dl=0&preview=test_14.txt&subfolder_nav_tracking=1
こちらで実行したところ、
https://paiza.io/ja/projects/new?language=python3
{"error":"Input must be shorter than 100000"}とエラーで確認できませんでした。

0

2Answer

ご提示のコードは、プレゼントの獲得数が最大となる位置が先頭以外の場合に、誤った結果となります。
例えば、以下の入力例に対し、正しい出力は2ですが、ご提示のコードですと1が返ります。

3 2
0 2 3
1Like

Comments

  1. @masamasa1981

    Questioner

    ありがとうございます!
    すごい・・・
    「ABC326C」に修正しました。

実際のin_test14を試そうとしましたが、(out_test14:5749)
https://www.dropbox.com/sh/nx3tnilzqz7df8a/AADDqsbRZGrRw1i-xjdeNFoxa/abc326/C/in?dl=0&preview=test_14.txt&subfolder_nav_tracking=1
こちらで実行したところ、
https://paiza.io/ja/projects/new?language=python3
{"error":"Input must be shorter than 100000"}とエラーで確認できませんでした。

paiza.ioの実行上の制約ですね。

自分の環境(Python 3.11.6)ではエラーとならず、5748と出力されました。
正解の5749との差が1あるということが、WA15個の理由でしょうね。

0Like

Comments

  1. 以下の入力で試せば原因が分かると思いますよ。

    入力
    11 1
    3 1 4 1 5 9 2 6 5 3 5
    
    正解
    3
    

Your answer might help someone💌