2024年1月28日日曜日

Codeforces Round 921 (Div. 1)

　A一完で紫に落ちた。

コンテスト後のツイート

B. Space Harbour

　等差数列をセグ木で扱えることは知っていたが、どうすれば良いか覚えていなかったので、検索するとstoqさんのこの記事が出てきた。
　等差数列を足し込む遅延セグ木があることを知り、そのコードを拝借して解こうとした動き自体は良かった。遅延セグ木を使う問題だとPyPyじゃ間に合わないことも多いしね。

　しかし、C++に慣れていないためコードを直すのに時間がかかり、WAが出た後の修正もできなかった。

　結局、間違っていたのは、「upper_bound()をそれ以下のindexが現れる最大のindex」だ
と思うという勘違いのため。

　lowerとupperで対称的なのかと思ってしまったんだねぇ。そして、それでもtest7まで通ってしまったため、定義を確認したり色々なケースを試そうという気持ちになれなかった。せめて他のケースを試していれば気付けて時間内に修正できた可能性はあるね……。そこも反省。

・lower_boundはbisect_left
・upper_boundはbisect

　胆に銘じておこう。

　なお、その他に添え字ミスもしていて結構ACは遠かった。test7まで通ってるから本質的なミスじゃないはず、と思ったのがはっきり間違いでした。

　

　


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

AtCoder Beginner Contest 338

　Eまで五完。

コンテスト後のツイート

F - Negative Traveling Salesman

　解説AC。

　ワーシャルフロイド法により、二点間の最短距離を全て求めておく。その距離を使って、全点を巡る距離をbit DPで求めれば良い。
　x→zよりx→y→zが短いとき、前者で計算してしまうのが問題になる気がするが、結局後者でも計算することになり、通った集合が後者の方が優れているのでこれで答えが求まる。

G - evall

　解説放送を見てAC。

　解説放送を見たときは実装が大変に思えたが、そこまで大変な実装ではなかった。なお、再帰で書いたらPyPyではTLEになり、Pythonで提出したらACした。
時刻: 0 件のコメント:
ラベル: , ,

2024年1月27日土曜日

yukicoder contest 416

　AB二完。C分からず眠ってしまったが、眠くなくても解けなていなかった可能性が高い。


No.2616 中央番目の中央値

　解説AC。

　計算量が二乗になるところまでは良くて、そこからの式変形が難しい。ヴァンデルモンドの畳み込みを知っていれば思いつきやすかったらしい。解法ツイートを見てもこれを使っている人が多い。
　自力で解くなら、ちゃんと式に書く→検索する（Wolfram alphaを使う）という感じだったかなぁ。二乗方針を思い付いてはいたが、式に書き下していなかったのはまずくて、手間を惜しまずちゃんと式にして考えるべきだった。

No.2617 容量3のナップザック

　一応自力AC。

　最初、貪欲に価値が高いものを詰めていけば良いのでは？　と実装してWA。価値3の個数を三分探索し、価値2のをいくつ取るか全探索したらACしました。
　多分、価値2のやつも三分探索で大丈夫そうですね。

No.2618 除霊

　解説AC。

　何か難しい考え方を使うわけではなく、適切に場合分けして、適切にまとめれば解ける。そういう問題こそ実力が問われるねぇ。
　解けるまで自力で考えるべきだったか。

No.2619 Sorted Nim

　解説AC。

　最初、解説を読んでも意味が分からなかったけど、この問題と本質的に同じだという言及を見て考えたら、なるほど、という気持ちになった。
　
時刻: 0 件のコメント:
ラベル:

2024年1月22日月曜日

AtCoder Regular Contest 170

　Cまで三完。

コンテスト後のツイート

D - Triangle Card Game

　解説AC。

　コンテスト中は、同じカードを二度出して良いって条件で考えていたことに気付いた。自分の実装だと、簡単には修正できなかった（頑張れば修正できそうだが……）のだが、noshi91さんの解説を見ると、「Aliceが最初選ぶ手は、min(B)に関する条件を満たすもののうち最大のものとして良い」とあり、これを使ってAC。実装が大分楽になりました。

　A[i]を全探索という方針に走ってしまうと思いつきにくいけど、これ自体は言われてみれば確かに……という感じ。

　誤読してなかったとしても、実装に苦戦してACできなかったと思うけど、Cを飛ばしてDにいっていたらACできた可能性はあるかなぁ。
時刻: 0 件のコメント:
ラベル:

2024年1月20日土曜日

Codeforces Round 920 (Div. 3)

　遅刻してEまで。

コンテスト後のツイート

F. Sum of Progression

　自力AC。

　平方分割で、最近のABCに出た問題とほぼ同じ考え方で解けますね。ただ、こっちは、累積和に加えてx+2*x+..ももたないといけないのがちょっと難しかった。

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

2024年1月19日金曜日

AtCoder Beginner Contest 335（Sponsored by Mynavi）

　Fまで六完。黄色に復帰できたのは嬉しかった。

コンテスト後のツイート

G - Discrete Logarithm Problems

　解説AC。解説放送も見ました。

・素数pについて、Z/pZに積を演算としてみたものは元の個数がp-1個の巡回群になる。
・各要素の位数はp-1の約数になる。

　あたりは知識としてもっていたかった。（もっていたはずだが、よく覚えていなかった。コンテスト中に一応理解できたが）

　そのうえで、

・位数が約数・倍数の関係になっているとき、今回の問題の条件を満たす
・各要素の位数を求めることができる

　ことが分かれば解ける。

　整理して考えればそこまで難しい問題ではないのだが……。
　ただ、各要素の位数の求め方はちょっと思いつきにくいので、次出題されたとき解けるようにしておきたい。








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

2024年1月14日日曜日

Codeforces Round 919 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Counting Binary Strings

　ツイートした方法で通った。

　D通した時点で残り時間が少なかったけど、そこまで難しくないDPなので20分あれば通せて良かった。DPの高速化する問題だろう、と思うなら、dict（Counter）でDPを実装したのは筋が悪かった。dictで実装すると高速化が必要なとき手間が増えてしまう。
時刻: 0 件のコメント:
ラベル:

2024年1月13日土曜日

yukicoder contest 414

　Cまで三完。


No.2603 Tone Correction

　解説AC。類題

　こういう区間に関する問題で階差を取るのは結構何度もやっているのに、身に着いていなかった。

No.2604 Initial Motion

　最小費用流の問題だとは思ったのだが、各点から各点への最短距離を前計算しなくてはいけないと思ってしまった。グラフを直接利用して最小費用流へ持ち込むことができる。（が、自前の最小費用流ライブラリだとTLE。うーん）
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)