Cまで三完。
No.2792 Security Cameras on Young Diagram
解説AC。
経路数の和になることには気付かなくてはいけなかった。
2024年6月24日月曜日
2024年6月19日水曜日
CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)
Fが解けず終了。
コンテスト後のツイート
G Eより楽に感じた。最後はある場所にとどまり続けるのが最適。DPテーブルをたくさん更新した後、ずっとそこにいるときの値を計算。
— titia (@titia_til) June 15, 2024
F - Easiest Maze
何回かWAを出したが自力AC。
解けなかったのは実装力不足のせい……といいたいところだが、Yes、Noの判定も間違っていたのはまずい。こういうのはちゃんとした確認してから実装しよう。
2024年6月15日土曜日
yukicoder contest 433
ABの二完。Dを考えていたが分からなかった。
No.2783 4-33 Easy
解説AC。
「良いスコアボード条件」の最後の条件の意味が分からず困ってしまった。このまま読むと、〇Xという形は使うことないけど……→使わないのが正解でした。
この、-4というのが分からなかったのだけど、一回に点が入るのは満塁ホームランの最大四点ということなのですね。
3 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 27X
みたいなのものあり得るはずなのにこの式は何？ と悩んでしまった。
ただ、ここに書いてあるものだけだと、「数字+Xが9回裏に入るとき、9回表の時点で裏のチームが引き分けか負けている」という条件が抜けてないだろうか。
このことが式に書かれているはず、と先入観を持って読んでいたせいで読解ができなかった気もする。
No.2784 繰り上がりなし十進和
解説AC。
線形代数っぽい見た目で、結合和として表したときに各係数が10以下で良いと気付くと解ける。
また、DFSのようにしても良い。全部で10^6個しかないので、0からスタートしてたどりつける数字を埋めて行けば解ける。
ただ、自分のPyPyのコードはTLEしてしまい、（Chat GPTを使い）RUSTでACした。writerさんのコードは結構余裕を持って通っているのだけど、どこで差がついているのかよく分からない……。
No.2785 四乗足す四の末尾の０
自力AC。
自力ではあるのだが、Nが1、-1のとき以外は素数だということの証明はできなかった。
2024年6月13日木曜日
Codeforces Round 952 (Div. 4)
Gまで。H2はコンテスト二分後に通った。
コンテスト後のツイート
G 9/k以下の数字しか使ってはダメ。等比数列の和。
— titia (@titia_til) June 11, 2024
H1 Union findして、各行・各列においたとき、どの連結成分が加わるかを見る。
H2 (x,y)を中心とする十字に置いたとき、何個プラスになるか？ を連結成分ごとにimos法して求める。
H2. Maximize the Largest Component (Hard Version)
ツイートした解法であっていた。
imos法をすぐに思いつけなかったのは問題だが、解法が分かってもそんなに簡単な気がしないので仕方ないかなぁ。
2024年6月9日日曜日
サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357）
Eまで五完。
コンテスト後のツイート
サントリープログラミングコンテスト2024（AtCoder Beginner Contest 357） Eまで。F遅延セグ木に乗るよね？→実装できずに終わる。ひどい……。（実装が下手なだけでなく、立式もおかしかった）
— titia (@titia_til) June 8, 2024
C 再帰で実装
D 等比数列の和の公式
E SCCしてごにょごにょ。
F - Two Sequence Queries
自力AC。
コンテスト中、遅延セグメント木を使えば解けると気付き、十分時間もあったのに解き切れなかった。
いい加減に実装して数値を合わせようとするのではなく、ちゃんと、何が何個足されるのか考えてから実装すべきだったか。
2024年6月7日金曜日
yukicoder contest 432
全完。Hで詰まったけれど、どうにかACできたのは良かった。
コンテスト後のツイート
yukicoder contest 432
— titia (@titia_til) June 7, 2024
B 二分探索
C 大きい方から消費
E,F Counter
G 左右から、len(A[:i])!=len(set(A[:i]))となる場所を探して、その間
H SCCしてごにょごにょ。最初に人1の手に渡ったというのを読み落として30分以上惑っていた。
Codeforces Round 951 (Div. 2)
Dまで四完。
コンテスト後のツイート
E (x+y,x-y)と座標変換して、各xについてのリストを作る。ある(x,y)について、x+kやx-kに二個k離れたものが[y-k,y+k]についてあれば良い。これは尺取りでできる。y座標についても同様にする。
— titia (@titia_til) June 6, 2024
……で良いと思っているけどどうだろうか。（最初WAを出したときはミスがあった）
E. Manhattan Triangle
ツイートした解法で良かった。コンテスト終了一分後くらいに書き終ったものを提出してAC。
Unratedだから笑い話で済むけど、Ratedでこういうことをしたら悔し過ぎるので、もっと集中しよう。
2024年6月5日水曜日
Codeforces Round 950 (Div. 3)
F1まで。
コンテスト後のツイート
E {sorted(A[i])}がsetとして一致。列についても一致。
— titia (@titia_til) June 3, 2024
F1 あるmまでのnの最大値を持つ。
F2 F1で1になったものそれぞれについて、使わなかった場合との差分を計算。その計算する箇所は、一つ前に1だった場所～一つ後に1だった場所の間だけで良いはず。
F2. Field Division (hard version)
自力AC。
コンテスト中に考えていた方針であっていたが、実装が大変だった。Gに行かずF2に集中していたらギリギリ間に合っていたかなぁ……。
G. Yasya and the Mysterious Tree
Binary Trieを使うということを参考にAC。
ただし、コンテスト中は誤読しており、xorではなくorを計算するものと思っていた。これがなかったら解法を思い付いていた気がする。
ただし実装には非常に苦戦した。
自分のTrieだとTLEで通らず、Chat GPTによりC++へ書き換えると、エラーが起きてしまい、どこが間違っているか分かるまで一時間以上かかった。
偶奇に分けて要素たちをBinary Trieに突っ込み、毎回自分の要素を減らした上で最適なものを探すのだが、要素数が0になっていたときの処理を怠っていた。
Pythonのコードもバグっていたはずなのだけど、PythonだとLIST[-1]というのでエラーが出ないため、たまたま合ってしまっていたんですね……。
修正してなんとかAC。
ただ、C++でも制限時間ギリギリだったので、Trieの書き方に問題がありそう。Binary Trieをちゃんと書かないといけないのかな。
2024年6月3日月曜日
AtCoder Beginner Contest 356
Eまで五完。
コンテスト後のツイート
AtCoder Beginner Contest 356 Eまで。F分からず困った。
— titia (@titia_til) June 1, 2024
C bit全探索
D 各桁ごとに
E 頑張ると調和級数の計算量へ帰着できる。
F 平方分割とかを疑っていたが分からず終了。
F - Distance Component Size Query
解説AC。特にevimaさんの動画を参考にした。
セグメント木とSortedSetを使い、二分探索で頑張れば解ける。「ある数と右隣の数が繋がっているか？」という配列をもとう、と思えるかがポイントか。
2024年6月1日土曜日
Educational Codeforces Round 166 (Rated for Div. 2)
Dまで四完。
コンテスト後のツイート
D (で+1、)で-1とした配列をAとすると、A[l]=A[r]が必須。また、l～rでA[l]*2を超えるものがあってはダメ。セグ木二分探索の後、二分探索。
— titia (@titia_til) May 30, 2024
E (q+1)*(q+2)*...がどの数字をどこへでも置けるときの答えで、そこからいくつか削る方針で考えていた。
E. Splittable Permutations
こたつがめさんの放送を見てAC。
クエリで与えられた数字が一意に並ぶことは分かっており、その間に余った数字を入れていくと考える部分もあっていたが、その条件が分かっていなかった。
ただ、並べる部分を再帰を使って書き、その書き方だと二乗になっていることに気付かずなぜTLE・MLEするか分からず随分悩んでしまった。
こういう実装はすらすらできるようにならないと。
F. Remove Bridges
こたつがめさんの放送や実装を見てAC。
解法は面白かったが、それだけだと実装が分からずこたつがめさんの実装を見る。すると、「各葉について、消された頂点までの距離」（この説明は意味不明だが……答えを得るのに必要な配列のことです）がdfs一発で求められていることに驚いた。言われてみれば分かるが、葉を中心に考えていたため思いつかなかった。
ただ、そのままだとPyPyの再帰がメモリを食うため通らず、非再帰に直してAC。木DPを使うと非再帰に直せた。
yukicoder contest 431
ABの二完。
No.2767 Add to Divide
テストケースを見てAC。
「B-Aの約数がA+Xになる」でXを絞る方針でコードを書いたがWA。ランダムテストを回したが落ちるケースがなく途方にくれてしまった。
テストケースを見たところ、A=Bで落ちていると分かってAC。全然気付かなかったなぁ。
No.2768 Password Crack
自力AC。
これは簡単だけど、もっと質問回数を減らせるとは気付いていなかった。
No.2770 Coupon Optimization
自力ACだが結構苦戦してしまった。
畳み込みなのでFFTしようとしたが、numpyによるFFTの方法を忘れており、numpy.fft.fft(A,k)のkの値の足りないコードを書いてしまった。最終的にできる配列が基準だから、今回はk=1<<19が必要。
畳み込みを使わなくても解けるらしいことには気付かなかった。
登録:
投稿 (Atom)