AtCoder Beginner Contest 246 振り返り
AtCoder Beginner Contest 246 - AtCoderに参加しました。
結果
ABC3問ACで、パフォーマンスは968でした。
C - Coupon
クーポンの効果は「X円引き（ただし負の値段にはならない）」なので、できるだけ無駄にならないように、まずは値段がX以上の商品にクーポンを適用していく。クーポン1枚の効果はX円なので、順番は関係ない。
この時点でクーポンを使い切ったら、その時点での値段を合計して終了。
すべての商品の値段がX未満になってもクーポンが余っていたら、できるだけ値段の高いものから適用していく。クーポンが0枚になったら、その時点の商品の値段を合計して終了。
D - 2-variable Function
全然わかりませんでした。aとbが最大でも10^6だということに気づきたかった。
E - Bishop 2
幅優先探索で解こうとしましたが、テストケース60個中、40AC・20WAとなりました。こういう時どうすればよいんでしょうね。
Eを解きに行くより、残り時間すべてD問題で粘るべきだったかも。
AtCoder Beginner Contest 245 振り返り
AtCoder Beginner Contest 245 - AtCoderに参加しました。
結果
ABC3問ACで、パフォーマンス829でした。D問題解きたかった……。
D - Polynomial division
係数を一つずつ求めていく、という手順はわかりましたが、実装が時間内にできませんでした。実装を簡単にしようとして、ABのうち短いほうの数列の先頭に0を足して長さを同じにしようとしたりしていました（最高次係数以外は0の可能性があるのでこれはうまくいかない）。
配列の添え字が変数の組み合わせになるようなコードを書くのが苦手なのかもしれません。具体例を一般化するの難しい。
AtCoder Regular Contest 137 振り返り
AtCoder Regular Contest 137 - AtCoderに参加しました。
結果
B問題のみAC。パフォーマンスは前回のABCに引き続き1000越えでした。うれしい。
各問振り返り
A - Coprime Pair
制約が10^18なので、なにか数学的な工夫をしないとTLEしてしまうのではないかと思いこんでしまいました。雑に桁数からループ数を考えるのではなく、数の性質からきちんと計算量を見積もるべきでしたね。
B - Count 1's
連続部分列に含められる（1の個数－0の個数）の最大値と最小値を求めればよいということは、わりとすぐに分かりました。その求め方にかなり悩みましたが、0を-1とみなして累積和を使って何とかAC。
終了後に解説を読んでみたら、1行目に、
1 の個数を最小/最大で何個にできるか，は簡単に求まります．
とありました。あんまりだ……。
まとめ
✅2回連続でパフォーマンス1000越え！
✅B問題コンテスト中に粘って考えてACまでたどり着けた。
❌計算量の見積もり方がいい加減だった。素数の分布を知らなくても、その場で調べることができたはず。
ABC243 振り返り
結果
ABC243に参加しました。ABCD4完で、パフォーマンス1069でした。やったね。
各問振り返り
B問題
かっこわるいけど全探索で解きました。
C問題
Y座標ごとに独立して考える。
左に進む人をL、右に進む人をRとすると、LLLRRRのように、いずれのRもすべてのLよりも右側にいれば衝突しない。Lのうち最も右側にいる人の座標と、Rのうち最も左側にいる人の座標を保持しながら、人全体をループで回して衝突しないか調べる。
ifによる分岐が複雑になり、1度バグを含むコードを送信してWAを出してしまいました。
D問題
制約が2の(10の100乗)乗。10の100乗個のビットがなければ表現できない数！
木の構造上、子に移動→親に移動、と移動すると必ずもとの頂点に戻る。移動情報をスタックに入れていき、RorLとUを打ち消し合わせていく。残った移動情報だけでシミュレーションする。
R,L,Uのそれぞれの移動先は移動元の頂点番号から計算で求められる。
E問題
グラフ全然わからない。コンテスト中にワーシャルフロイド法とか調べたけれど、どうにもなりませんでした。
まとめ
- ✅はじめて1000パフォーマンス超えた！
- ✅D問題で移動情報を圧縮するのに、スタックを使えばシンプルに実装できることに気づけた。
- ❌C問題が複雑な条件分岐になってしまった。
- ❌グラフが全然わからない。
ABC242振り返り
AtCoder Beginner Contest 242に参加しました。
結果
ABC3完、パフォーマンスは879でした。1時間かけてD問題に挑みましたが、解けず。
レーティングの推移を見ると右肩上がりに見えますが、これは登録直後にかかるマイナス補正が外れつつあるためです。各コンテストのパフォーマンスは毎回ほぼ800台で、全然成長していない？
言語
今まではPythonを使っていましたが、今回はKotlinで書きました。本番までに過去問やCodewarsで練習していたので、とくに言語が変わったことによる苦労は感じませんでした。まあ、そもそもPythonに習熟していたわけでもないしね。
各問題振り返り
A - T-shirt
実数を扱う問題はあまり経験がありませんでした。大小比較の時に誤差が心配だったので、整数型で受け取り、割り算の時だけ実数に変換しました。
B - Minimize Ordering
ソートするだけ。
C - 1111gal password
問題を一読した時には、『典型90問』の069-Colorful Block 2と同様の問題かと思いました。しかし2~8の隣は3パターンあるのに、1と9の隣は2パターンのため、うまく計算で一撃では求まりそうにありません。
制約がN <= 10^6であるので、余裕をもってN回ループを回せそうです。ある桁のパターン数は隣の桁の数字によって決まるので、DPで解けました。
D - ABC Transform
二分木のような構造や、A-B-Cが循環しているということには気づきましたが、回答までたどり着けませんでした。制約が大きすぎる！
まとめ
- ✅ C問題をDPで解けるという発想ができた。
- ✅ 制約から計算量を見積もって、DPで間に合うことを確認してから実装できた。
- ❌ D問題歯が立たなかった。正直何が分かっていれば解法までたどり着けたのかもよくわからない。でも難しすぎるからしょうがないね。
Asprovaプログラミングコンテスト
3/6から第8回Asprovaプログラミングコンテストというヒューリスティック型のコンテストが始まるそうです。ヒューリスティックコンテストは一度だけ(AHC008)参加したことがあるのですが、その時は考えた動きをするコードを実装することができず、結局ランダムな動きをするコードを提出して終わってしまいました。
次はランダムよりはマシな得点を取ることを目標にして参加してみようかな。
