読者です 読者をやめる 読者になる 読者になる

ferinの競プロ帳

競プロについてのメモ

AGC007に参加してみた

AGC 競技プログラミング

 リアルタイムでコンテストに参加するのは初めてで緊張しました… 結果はA,Bの2完でした!過去問を解いていた感じではB問題で解けるか五分五分くらいだったので目標の2完が達成できて嬉しいです。B問題を時間ギリギリで解けたときの達成感で競プロのモチベが上がってます。毎週のようにリアルタイムであるのはモチベーションの維持にいいですね!

agc007.contest.atcoder.jp

A問題

 深さ優先探索を使って右下にたどり着いたときに#の数と歩数が一致していたら"Possible"、一致するパターンがなかったら"Impossible"を出力するように実装しました。
 最小経路からH+W-1と#の個数から求めるなんてスマートな方法があったんですね。左上から右下まで繋がっていることが保証されていることに気づきませんでした…

B問題

 最初どうすればいいのか全く目処が立たなかったんですが、aとbの最初の値を適当に決めて、順番に並ぶようにするにはどこを足したり引いたりすればいいのか紙に書いて色々試した結果、aとbに足していく数を1ずつ増やしていけばいいことに気づきました。そして、配列の隣の要素の間隔を広めにとって初期化すれば順番がおかしくなることはなく、n<=20000なので20000刻みで初期化すればいいことに気づき実装できました。(あと20000*20000=4*10^8なので数列の要素の大きさの制限に引っかかることはありえない。)

C問題、D問題

 パッと見で全探索しか思い浮かばず実行時間が足りないと思ったので解いてないです。

E問題、F問題

 解ける気がしなかったので見てもないです…