2023/6/10に開催された、京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)に参加しました。
先週のABCでは、負け確の結果だったものの、Unratedになったおかげで、なんとかレートを減らさずに済みました。今回、改めてレート上げを目指し、水パフォ目標で頑張ります。
Rated参加します。
— devgenjin77 (@devgenjin77) 2023年6月10日
水パフォ以上出せるように頑張ります✊
京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305) - AtCoder https://t.co/OxHwlnuh0D
今回の結果
今回は、なんとA-Fの６完を達成することができました！
ほぼ１年ぶりに青パフォを獲得し、レートは急騰！惜しくもHighest更新までは行けませんでしたが、もうちょいで入水というところまで上げることができました。
６完青パフォ😂😂😂
— devgenjin77 (@devgenjin77) 2023年6月10日
入水が見えてきました！
devgenjin77さんの京セラプログラミングコンテスト2023(AtCoder Beginner Contest 305)での成績：737位
パフォーマンス：1616相当
レーティング：1123→1183 (+60) :)#AtCoder #京セラプログラミングコンテスト2023(ABC305) https://t.co/bXqqLmjwEx
振り返り
F問題で１つ小ミスがありましたが、概ね順調に解き進めることができました。
A問題
切り捨てか切上げかを判断する必要がある問題。うまく書けば１行程度で済みそうな感じもするが、見落としがあってWAを喰らうのも嫌なので、ある程度愚直な処理を書くことに。
を
で割った余りが
の場合、答えはそのまま。それ以外の場合は、一旦
から
で割った余りを引いた数を答えとし、元々の余りが
以上なら答えに
を足す感じで実装。提出して問題なくACが取れましたとさ。
3分39秒で1完。愚直に書いた分、時間をかけてしまいました。
提出コード
https://atcoder.jp/contests/abc305/submissions/42122698
B問題
から各点への距離を累積和で持っておく。ただ累積和を実装するのも手間だし、今回は固定値で指定されているので、暗算したものを決め打ちで使用。
あとはから
の距離に対して
から
の距離を引けば良い。答えは、絶対値で出すことに気をつける。
こんな感じの実装で問題なくAC。7分5秒で2完です。
提出コード
https://atcoder.jp/contests/abc305/submissions/42127390
C問題
問題文にある、を求めてから、改めてその範囲内にある
.の位置を求めるのが正道かという問題だが、そこまでやると実装が大変そう。
あくまで直感ではあるが、.の上下左右に隣接する場所に#がつ以上あれば、それが対象では？
ということで、一度、この実装で組んでみて提出したらACが取れましたとさ。
15分17秒で3完。実際、ACするか心配でしたが、とりあえず通ってよかったです。
提出コード
https://atcoder.jp/contests/abc305/submissions/42134217
D問題
見た感じ、までの睡眠時間から、
までの睡眠時間を引けば良さげ。
睡眠時間の求め方としては、まず、入力の睡眠記録を起床時刻と就寝時刻に分けてから、各起床時刻までの合計睡眠時間を累積和で計算しておく。
次に起床時刻の配列を、経過時間で二分探索して、何回目の起床が、直近の起床なのかを判別する。後は、直近の起床までの累積睡眠時間と、それ以降の睡眠時間を計算して足せばOKという感じ。
後は実装というところで、結構バグらせたりしたため、大分時間が取られましたが、なんとか１度の提出でACを取り切ることができました。
44分26秒で4完。肌感では、これぐらいの難易度だと緑パフォぐらいかと思いましたが、実際は茶パフォでした。。参加者のレベルが上がってきているような気がします。
提出コード
https://atcoder.jp/contests/abc305/submissions/42146540
E問題
各頂点に対して、警備員が配置、もしくは移動してきた後の残体力の最大値を計算する事を考える。
具体的には、警備員が配置されていない頂点にを代入し、配置されている頂点に、入力で与えられた体力を代入。
次に、ダイクストラ法の要領で、残体力の大きい警備員に着目し、隣接する頂点に移動した時、各頂点の最大残体力を更新していく。
処理が終わった時に、残体力の最大が以上、要は１度は到達した頂点の集合を求めれば、答えは出る。
と、こんな感じで実装して、提出。問題なくACが取れました。64分37秒で5完。
提出コード
https://atcoder.jp/contests/abc305/submissions/42153313
F問題
忘れた頃にやってくるインタラクティブ問題。今回は問題のタイトルがダンジョン探検と言っている通り、無向グラフ内を探索していく問題の模様。
解法を検討していくと、普通に移動したことのない頂点に移動を繰り返すという感じの実装では、袋小路に入った時に抜け出すことが出来なさそうです。
そこで思いついた解法は、各頂点に対して、頂点からの移動コストを更新しながら移動を繰り返していくという方法。
具体的には、まず、以外の各頂点の移動コストの初期値を
で初期化し、次に移動先を決める際、頂点
が候補にない場合は、移動先の中で、移動コストが最小になっている頂点を移動先として選び、現在のコストに
を足したものを遷移先のコストとして更新する。
こうすることで、基本的には、未探索の頂点が移動先の候補となり、未探索の頂点がない場合は、移動元の方に戻る挙動になってくれる筈。これを繰り返せば、いつか頂点に辿り着くかという算段です。
で、実装して提出してみると、初回提出は実装ミスがあったため、WAを喰らうも、修正版でなんとかACを取り切ることができましたとさ。
84分10秒1ペナで6完。この時点で、順位は700位の後半ぐらい。久々に高パフォーマンスを叩き出すことが出来そうです。
提出コード
https://atcoder.jp/contests/abc305/submissions/42159708
G問題
多少、時間があったので、一応目を通してみましたが、何もわからずでした。。７完への道は遠いです。
Ex問題
問題すら見れておりません。
これまでの実績
青パフォゲットで、一気にHighest付近までレートを回復。今度こそ、この勢いで入水を目指します。
総括
今回の難易度的には、６完取るのは無理という感じではなかったので、なんとか順調に進めることが出来て良かったというのが正直なところです。
来週は、ABC、ARCと２回チャンスがあるので、ここで一度入水を決められるよう、準備を進めていこうと思います。
ということで、また次回も頑張ります。
