ABの二完。Cを考えているときに体調が悪くなり撤退。
No.2394 部分和乗総和
自力AC。
しばらく分からなかったが、形式的ベキ級数に思いを馳せたら解けた。
No.2395 区間二次変換一点取得
自力AC。
各indexごと独立なので、各indexについて何回クエリが適応されているかだけ見れば良い。
問題文を理解するのがちょっと難しいけど、理解してしまえばBやCより簡単では。
2023年7月29日土曜日
2023年7月28日金曜日
Codeforces Round 888 (Div. 3)
Gが解けなかった。
コンテスト後のツイート
Codeforces Round 888 (Div. 3)
— titia (@titia_til) July 25, 2023
B 奇数偶数に分けてソート
C A[0]を前からk個、A[-1]を後ろからk個
D 差を取って場合分け
E x（達）からyが作れるとき、x→yの辺を引き、入次数0のものから順に決める
F 上の桁から同じもの同士をまとめる分割統治
G 並列二分探索で良いと思うけどTLEが取れず。
G. Vlad and the Mountains
並列二分探索を使わないでも解けるというツイートを見てAC。
しばらく考えて分からなかったのが、並列二分探索で解けるということに気付いて喜んで実装したらMLEやTLEが出て、残り時間が少なかったため定数倍高速化を試したがACできなかった。
落ち着いて考えれば、「start時点の山の高さ+e」までの高さの山を結んだときstartからgoalにたどりつけるかさえ調べればよいため、並列二分探索は必要なかった。
2023年7月23日日曜日
トヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311)
Fまで。
コンテスト後のツイート
F あるマスが黒だとその下のマスも黒い。ので、列ごとに見ると「xマスより下が黒」という状態で表せる。これを状態としてDP。
— titia (@titia_til) July 22, 2023
G - One More Grid Task
解説AC。
「最大長方形」のアルゴリズムを使うのかな、とはコンテスト中に考えたのに、（検索したら）最大長方形のアルゴリズムはヒストグラムの形にしか適応できないことを見て、この問題には適応できないと思ってしまった。
「i行より上の部分だけを見る」として最大長方形のアルゴリズムを適応する発想がなかった。
最大長方形のアルゴリズムを使うかもしれないと思ったのなら、もうちょっと使える形に変形できないか考えないと。
Codeforces Round 886 (Div. 4)
pretestは全完。あまり迷うところもなかったので、GがHackされ、FでシステムテストでTLEしていて驚いた。
コンテスト後のツイート
Codeforces Round 886 (Div. 4)
— titia (@titia_til) July 21, 2023
D ソートする
E 計算すると二次方程式になる
F 計算量は調和級数
G x,y,x+y,x-yについてCounter
H 重み付きUnion-find
F. We Were Both Children
Pythonでset（Counter）を使うとHashを衝突させられる案件でTLEしていた。
何の気なしに、Counter(A)と書いてしまった。
Counter(sorted(A))に直してAC。
G. The Morning Star
これもF同様Counterのせいで落ちていた。
ただ、sortしただけでは通らないケースが入っており、座標を1ずらしたらACした。
CodeforcesではsetやCounterを気楽に使ってはいけないってことですね。うーむ。
2023年7月22日土曜日
yukicoder contest 398
ABの二完。
No.2387 Yokan Factory
自力AC。
答え二分探索＋ダイクストラ。解法は分かったのに睡魔に襲われて実装できなかった。しかし、いくら眠くてもこれを実装し切れないのはですね。
No.2390 Udon Coupon (Hard)
自力AC。
最も効率良いものをたくさん買った後、残りをDPすれば良い……というのは、この問題などを解いていたため知っていた。
それなのに、三分探索で良いのでは？ などと混乱してしまいWAを出したのはダメ。
2023年7月18日火曜日
freee プログラミングコンテスト2023（AtCoder Beginner Contest 310）
Fまで六完。
コンテスト後のツイート
freee プログラミングコンテスト2023（AtCoder Beginner Contest 310） D~
— titia (@titia_til) July 15, 2023
Fどれも苦戦したがFまで。
D 答えの最大値が小さそうなので雑にDFS書いたら間に合った。
E ランレングス圧縮してメモ化再帰で解いた。もっと簡単な方法がありそうだけど分からず。
F 今までに現れた和の種類2^10個をもってDP
G - Takahashi And Pass-The-Ball Game
解説を読んだけど、ダブリングの解法がすぐには理解できず、解説放送も参考にしてAC。
ダブリングでいけそうということは分かっても、実装するのが難しい問題だった。
ダブリングでさくっと求められるのは、「xさんのボールがy回の操作後どこにあるか？」だが、ダブリングの途中で二回の操作を一回にまとめていかねばならないため混乱しやすい。
ダブリングをこういう風に使ったことがなかった気がするので、ちょっと新鮮だった。
コンテスト中は行列累乗なんかを考えたりしていて的外れでした。
Ex - Negative Cost
解説放送を見てAC。
・ナップザック問題で重みが大きいときどうするか？
という問題の解法を知っていないと解くのが厳しかったと思う。
最大効率に着目するのは直感にも合致していて、確かにそうだな、という感じ。
この問題に帰着しようと思えたのなら、帰着する部分は思いつけなくはなさそう。
Codeforces Round 885 (Div. 2)
BCDの三完。
コンテスト後のツイート
D 一の位が0や5以外なら、一の位は2→4→8→6→2→……の繰り返しになる。その間、sは+20、kは-4するので、大体(s+20x)*(k-4x)の最大値を求めれば良い。このxを（微分か平方完成かで）求めてその周囲を調べる。
— titia (@titia_til) July 16, 2023
A. Vika and Her Friends
解法ツイートを見てAC。
市松模様に分けたとき、自分と同じ場所に来る可能性があるのは、同じ色の場所のみ。
自分が動いた後、敵は自分の動きを見てから移動できるので、敵が同じ色の場所に一人でもいたら捕まる。
読解がやや難しくて、最初問題を読んだときは勘違いした（一手後に捕まるかを判定するのかと思った&「敵は自分の動きを見てから移動できる」を読めていなかった）が、最後は正しく理解していたのに分からなかった。
「敵は自分の動きを見てから移動できる」というのを正しく読めたのに解法に反映させておらず、よく分からないけど敵が二人いたらダメなのかな、などと考えていた。
コンテスト中の立ち回りとしては、すぐに理解できなかったら飛ばすのが正解だったと思う。飛ばすのがちょっと遅かった気はするけど、まあ良いか。
登録:
投稿 (Atom)