Eは難しく差がつかないラウンドだった。コンテストとしては不満。|追記:原因がわかったので編集しなおしました。追記の追記:Sigmarさんのご指摘で真の原因が判明しました。前の記事のコメントを参照してください。前の記事の通り、R1は落ちてしまいました。今回はAのバグを探りたいと思います。正解者のコードを実行して得た結果answer.outと、自分がsubmitしたファイルA.outのdiffをとります。4256235となります。8512466のときだけ値が合わないようです。そこで、前の記事にあるコードの最後の出力部分を少し書き換えてみます。567503となります。4前後まで計算してストップしたほうが、今回のようなややこしいバグを含まなくて良かったかもしれません。Bはちょっと考えて大変そうだったので早めに諦めました。今日の3:00にR1が終了したので、軽く振り返ってみようと思います。コードや考え方が間違ってる可能性もあるのでご注意を。(なお、問題説明は省略します。これ読んでる人の多くはR1に参加してると思うので)最後に、誰か、はてなの日記でコードを綺麗にハイライトしてくれる方法をご存知でしたら、是非教えてください~(追記:←解決しました)追記:結果は残念ながらxooでした。phase対策の格好の勉強材料になりそうですw未だにバグがわからないので、気付いたら教えてくださると嬉しいです。計算して、nCrに対する最小のnを記憶しておくこと。nCrの計算にパスカルの三角形を利用しました。Sequence1,2,...,Nを求める答えとしてマージソートして逆変換する方針で解きました。リストの使い方が楽なのでpythonで書きました。sequence中の0の扱いに注意する必要があります。以上に注意すれば、比較的に簡単な問題かと思いました。自分はメモ化再帰で解きました。0;}追記:A落ちてます・・・。17:54Mi_Sawaさん情報ありがとうございます!お陰様でハイライトできました。Mi_Sawaさんは無事にR1通過したようですね。01:21Aのパスカルの三角形の計算ですが、恐らくprepare全体の中で一度でも要素が10000000を超えた場合(a+pre>10000000もしくは2*pre>10000000となった場合)、その後2*preをasに一切追加しないようにする必要があるのではないかと思います。16:17Sigmarさんご指摘ありがとうございます!ああ、なるほど!!確かに2*preの追加に注意すべきでした。224.28+0+0+(50-25)=249.28で144位。877→968(+91)。Easyで慎重になりすぎたのとMediumでメモ化再帰の実装を時間に追われてミスったのが反省点。res;}};プロコンを始めて四ヶ月、ようやくメモ化再帰とDPが実装できるようになって来ました。全探索のコードを考える→(TLEの可能性)→メモ化→(スタックオーバーフローの可能性)→DPの順番で考えること。最初の「全探索のコードを考える」のが一番重要で難しい。Div2カウンター47743。