SRM参加記録など雑記です。社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。Statement非常に問題文が長く、読むだけで10分以上かかりました。アルゴリズムとして難しいところはないので、実装するだけです。ひっかけなどもなさそうなので、submit。システムテストも問題なく通りました。何人か落ちてる人がいましたが、あまり落ちるような要素は見つけられていなかったので、チャレンジはしていません。Statement読んだ感じ、一瞬グラフかなと思いましたが、逆戻りするエッジがないので、DPで解けそうだなという印象を受けました。longのメモリが必要です。longに換算すると800万個程度までしか変数を使えません。このようにメモリ容量をオーバーする場合、コンパイルエラーにはならず、実行時にSIGKILLとかいうエラーが返るので、TLE狙いと同様チャレンジに使えます。いうことで、20分くらいダイクストラとか状態の持ち方を変えるとか色々考えてましたが、どれも計算量・メモリ量ともに大きすぎて、いい方法が思いつきません。最初から気になっていたのですが、街iから街i+jにフライトする時間が、街iから街i+1へのフライト時間+・・・+街i+j-1から街i+jへのフライト時間となっており、最初に考えたようにDPした場合にこの条件を全然活かせないので、無駄があるのではないかと考えていました。考えると、街iから街jへの経路は考える必要はないのでは・・?街iへの到達が歩いてきたかフライトしてきたかさえ記憶すれば、街i+1へフライトする際に、フライト回数を増やす必要があるかどうかは常に判定可能じゃないですか!!ということは、40万の街の状態をすべて覚えておく必要はなく、直前の街に到達したときの最小時間さえ覚えておけばよいことになるので、必要なメモリ量は2*40*2=160程度しかありません。いうことに気づいたときには、既に残り15分でした。間に合うかと頑張りましたが、コンパイルエラーやら何やらで結局間に合わず。rt[400010]={0})。bytes"という不親切なエラーメッセージで全然原因が分からなくて非常に疲れました。宣言時に初期化するとバイナリコードにデータが埋め込まれるということなのかな。バグを取った500点問題のsourceです。OpenTipsDiv1SRM455SRM456SRM457SRM466SRM467SRM468SRM469SRM470SRM471SRM473SRM474SRM475SRM476SRM477SRM478SRM479SRM480SRM481SRM482SRM483SRM484SRM485SRM486SRM487SRM488SRM489SRM490SRM491SRM492SRM493SRM494SRM495SRM496SRM497SRM498SRM499SRM500SRM502SRM503SRM505SRM504.5SRM506SRM507SRM508SRM510SRM511SRM512SRM513SRM514SRM515SRM516SRM517SRM518SRM519SRM520SRM521SRM522SRM523SRM524SRM525SRM526SRM527SRM526.5SRM528SRM529SRM530SRM531SRM532SRM533SRM534SRM535SRM536SRM537SRM538SRM540SRM541SRM543カウンター358021リンク集SigmarのProfile。