2025年9月20日土曜日

Kotlin Heroes: Episode 13

　Eまで五完。

コンテスト後のツイート


F. Array Reduction

　コンテスト中は、頻度順に並べ、縦に使うか横に使うかの貪欲だと思ったがWA。
　解法ツイートを見ると、縦に何回使った後横に何回使うか、全探索できるとあり、それを使ってAC。

　ただ、頻度列において、最初にxより大きくなるindexを前計算しておかないといけないことに気付けず、TLEを重ねてしまった。

時刻: 0 件のコメント:
ラベル:

2025年9月19日金曜日

Codeforces Round 1051 (Div. 2)

　D1まで。


E. Make Good

　コンテスト中は全然思いつかなかったのに、コンテスト後簡単に解けた……と思ったらWA。テストケースを見て見逃していたケースに気付いてAC。

　"("の海の中から、")"を二個ずつ動かせる（"("と")"は逆でも良い）、と考えるべきだった。

・まず、できる限り")"にする。
・"("を右にもっていく。
・"("の個数が足りない分、左から"("にする。
・一度右にもっていた"("をできるだけ左へ。

　この手順で上手くいっていればそれを提出、ダメなら-1とした。

　頭の中で考えていたときは、単純に"("を左にもっていけばいいと思っていたが、偶数個目に"("がある場合がありダメ。
　まず右に寄せ、左端に必要なだけ"("を作ってからその作業をしなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

2025年9月17日水曜日

Educational Codeforces Round 182 (Rated for Div. 2)

　Cまで三完。遅刻でE1。Dで考え込んでしまった。

コンテスト後のツイート

D. Price Tags

　自力で解けず、色々解説を見てAC。難しくない？

　コンテスト中は、xを絞れるのではないか？　ということを中心に考えていたが、これはダメな方針だった。
 xの全探索を考えるのが正解。

　しかし、その後も容易ではない。各C[i]を割っていくのではダメ。
　xのとき、割引後の値がdになるものは何個あるか？　と考えて、Cの頻度表を累積和の形でもっておくと調和級数の計算量になる。

　xを全探索すれば調和級数になる、と聞いてからも解法が分かるまでかなり時間がかかってしまったので全然ダメでした。


　


時刻: 0 件のコメント:
ラベル:

2025年9月15日月曜日

AtCoder Beginner Contest 423

　ABCDFの五完。Eが解けずレートを落とす。

コンテスト後のツイート

E - Sum of Subarrays

　苦労したがコンテスト中の方針でAC。

　この記事では全ての連続する部分和の総和を求めているので、累積和の差全ての和が答えになっている。
　では、この問題のように、連続部分列に対して考えた場合どうなるか？
　最初に累積和を取っているため、（累積和をSとすると）S[l:r]について同じように値を求めたあと差分を計算する必要がある。

　……と考えていたが、これはダメな方針だった。

　累積和の最初が0になっている代わりに、S[l-1]があると考えれば良い。
　そうすると同じ方針ですっきり書ける。

　これに気付くのに何時間もかかってしまい、ダメでした。

　各A[i]の寄与を考えるという方針も思いついたはずだけど、公式解説のような感じにはできなかった。そもそも立式できていない……。

時刻: 0 件のコメント:
ラベル:

Codeforces Round 1050 (Div. 4)

　全完だがGは2800msとかなので怪しい。→Gはシステムテストで落ちました。

コンテスト後のツイート

G. Farmer John's Last Wish

　コンテスト中はセグ木を使って実装したが、よく考えるとセグ木は必要ない。セグ木を削ってlogを取ったらACできた。
　コンテスト中も時間ギリギリだったから、セグ木をなくせないかは少し検討したはずなのだが……。





時刻: 0 件のコメント:
ラベル:

2025年9月13日土曜日

yukicoder contest 482

　ジャッジが動いていなかったためAB二問を解いて撤退。が、BはWAでした。

コンテストへのリンク

No.3268 As Seen in Toasters

　自力AC。

　まず、ソートした場合の値を調べる。が、それが最小値でない場合も存在するので、それがどういうときかを考える。

　色々試すと、「負の区間　正の区間　負の区間」と並んでいるときに最適になりそうと分かった。
　そして、正の区間は差が小さくなるよう山型になっていると良く、負の区間についても、端だけコストが一回しかかからないため、端に最小のものがあれば良い。（ため、全体として山型になっていれば最適）

　という、コンテスト中の考え方であっていたが、負の個数が一つもない場合の処理を忘れていてRE。そこを直してAC。
時刻: 0 件のコメント:
ラベル:

2025年8月29日金曜日

Codeforces Round 1046 (Div. 1)

　D1まで四完。D2は分かったのに実装間に合わず。あと一分あれば間に合っていた気がするので悔しい。

コンテスト後のツイート

D2. From the Unknown (Hard Version)

　D1と同じ発想で解ける。
　最初[125]*10000と聞く。（この125とか10000は色々試して探す）
　0のときは[1]*15000で決定できる。
　そうでないときはD1と同じようにやる。同じ値が連続して15000/2個以上出てたらクエリの長さが間に合わないが、この値だと間に合っている。

　この最後のパートをD1と全く同じように書いていたのがダメでした。クエリ回数を抑えるため、同じ数字が返ってくるものの個数だけ使わなくてはいけなかった。これでAC。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)