2023/8/26に開催された、ゲームフリーク Programming Contest 2023(AtCoder Beginner Contest 317)に参加しました。
先週のABCは、緑パフォ確保がやっとという体たらくでした。
実は、先週のE問題では、新ジャッジ側でJavaの実行設定がうまくいっていなかったのか、DFS実行時にスタックオーバーフローが出ており、それが原因でACが遅れたというのが敗因でもありました。
一応、今週にかけて、プログラム側でスタックサイズを指定する対策などを学んでいたのですが、どうも、今週にかけてジャッジ側で設定を修正していただいた模様。今後DFSする時、いちいちスタックサイズを考慮しないといけない所だったので、助かりました。
何はともあれ、直近コンテストは２連敗という状態。ここいらで連敗と止めようという気持ちで臨みます。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年8月26日
２回連続で大負けしているので、今回で連敗を止めるべく、水パフォ目標で頑張ります✊
ゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317） - AtCoder https://t.co/p2sZJyV8WD
今回の結果
久々の５完達成です。
これでも、結果はギリギリの水パフォ達成というところ。でも、なんとか連敗を止めることはできましたとさ。
５完水パフォでした😃
— devgenjin77 (@devgenjin77) 2023年8月26日
devgenjin77さんのゲームフリーク Programming Contest 2023（AtCoder Beginner Contest 317）での成績：1819位
パフォーマンス：1230相当
レーティング：1137→1146 (+9) :)#AtCoder #ゲームフリークProgrammingContest2023（ABC317） https://t.co/Q0H7odiK4J
振り返り
今回は、５完早解き回だった模様。D問題でミスを連発したのが痛かったです。
A問題
問題文の通り、となる最小の
を求めて出力するだけ。
1分42秒で1完。
提出コード
https://atcoder.jp/contests/abc317/submissions/44936378
B問題
答えが一意になるというのであれば、配列の最小値と最大値の間に欠番が存在するはず。
ということで、をソートして、連番になっていない所を探し、抜けている番号を答えとする実装で提出。
これが問題なくACで、4分29秒で2完です。
提出コード
https://atcoder.jp/contests/abc317/submissions/44941454
C問題
C問題から、強烈に難易度が上がってきた。。というか、いきなり巡回セールスマン問題をC問題に出してくるか？という印象でした。
ぶっちゃけ、最近、巡回セールスマン問題の実装を書いてなかったので、思い出しながらの実装。。で、やっと実装できたと思ったら、これが結局全ての頂点に行けるわけではないというのが判って、実装を少し変更。
ということで、色々実装に苦労した問題でしたが、とりあえずACを取ることはできました。24分50秒で3完。
ちなみに、この制約だとDFSでも答えが出ていた模様。まあ解けたからヨシとしましょうか。
提出コード
https://atcoder.jp/contests/abc317/submissions/44956439
D問題
読解に結構時間を使ったが、どうも議席数の合計が抑えられている制約のようなので、ナップサックの応用問題ですよという感じ。
ナップサック問題の実装も最近やってないので、これも思い出しながらの実装。で、サンプルが通ったところで提出してみたらこれが原因不明のWAを喰らってしまいました。。
分岐がおかしいのか、オーバーフローしているのか、色々調べて投げ直してはWAを喰らってましたが、結局INF値を設定するところでバグらせているということに気付く。
これを修正してAC。都合３回もWAを喰らってしまいましたとさ。
61分7秒3ペナで4完。結果的に、この３WAで順位が伸び悩んでしまいました。
提出コード
https://atcoder.jp/contests/abc317/submissions/44967736
E問題
グリッド上で、人の視線が届く範囲を通過不可にしてから、BFSで最短経路を求める問題という感じ。
通過不可にする実装を上下左右バラバラに組んだので、コード量が結構大きくなってしまいましたが、なんとか１回の提出でACを取り切ることが出来ましたとさ。
80分47秒3ペナで5完。
提出コード
https://atcoder.jp/contests/abc317/submissions/44972760
F問題
E問題終了時点で、問題には一応目を通してみました。が、、AC数からして黄Diffはありそうな感じ。。。
全く何もわからずで終了。
G問題
これも、一応目を通しましたが、何もわからずです。
Ex問題
あのtourist氏すら解けない問題の模様。問題すら見ておりません。
これまでの実績
とりあえず、３連敗は避けることが出来ました。再度、入水に向けて頑張ります。
総括
今回は、緑Diff程度の問題が着実に解けるかという回でしたが、細かいミスが響いて順位を落としてしまいました。
最近、この手の典型の復習が疎かになっていたのかも知れません。鉄則本などで復習していこうと思います。
ということで、また次回も頑張ります。
