2024年11月19日火曜日

Codeforces Round 988 (Div. 3)

　時間ギリギリ全完。
　ARCの後だったせいもあり、序盤やる気が出なかったけど、全完できて良かった。

コンテスト後のツイート


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

2024年11月18日月曜日

AtCoder Regular Contest 187

　A遅解き一完。

コンテスト後のツイート

B - Sum of CC

　解法ツイートを見てAC。DPでできるのでは？　と考えたくなるが、主客転倒で考えなくてはいかなかった。

　階段状になることを利用するのは正しくて、そこから、段に関して主客転倒して考えようと思わなくてはいけなかった。主客転倒はちょっと考えたはずなんだけど、うまく考察できなかった。

C - 1 Loop Bubble Sort

　自力AC。

　実験して、-1がなく最後がNの場合は、pow(2,累積maxの更新回数)が答えになると分かった。
　そこまでも時間がかかったが、その数え上げがDPでできると分かるまでも長かった。

　時間があれば自力で解ける問題だったことは分かったが、コンテスト中に通すためにはどうすれば良いんだろうか。
時刻: 0 件のコメント:
ラベル:

2024年11月17日日曜日

AtCoder Beginner Contest 380

　Fまで六完。

コンテスト後のツイート

G - Another Shuffle Window

　自力AC。

　大まかな方針はあっていたけど、三つ分けたとき、左同士、右同士の転倒数も足さなくてはいけないことを忘れていた。
　結構本質的な考察ミスなので、コンテスト中に解き切るのは厳しかったか……。

　しかし、解けなくてはいけない問題でした。
　



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

2024年11月14日木曜日

Codeforces Round 971 (Div. 4)

　G1まで。

コンテスト後のツイート

G1. Yunli's Subarray Queries (easy version)

　そもそもクエリの種類がn種類しかないのにMoを使ったのはおかしかった。
　順番に求められますね。

G2. Yunli's Subarray Queries (hard version)

　こたつがめさんの放送の振り返りを見てAC。

　Div.4だから、という先入観があったからかもしれないけど、遅延セグ木を使うと思いつかなかった。
　典型ではあるかもしれないけど、簡単ではないね。


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

2024年11月12日火曜日

Refact.ai Match 1 (Codeforces Round 985)

　Eまで五完。

コンテスト後のツイート

F. Palindrome Everywhere

　parityが関係するというツイートをヒントにAC。

・RRとBBが同時にあるとダメ
・Rが一個以下、または、Bが一個以下ならOK

　はコンテスト中に分かっていたが、

・RBBRBBはなぜダメなのか？
・RBBBRBBBRBBは良いのか？
・RBRBBRBBは良いのか？

　などは分かっていなかった。

・RBBRBBがダメなのは、相対位置の偶奇を考えれば分かる。（RBRBや、RBRBBBも同様）
R(x)BBR(y)BBのxからyを考える（x,yから同じ文字の方向を挟む方へ動かせる、と考える）と、xがRをまたぐときyもRをまたぐためxからyへたどりつけない。

・RBRBBRBBは良い。偶奇（Rの間に入っているBの個数）両方含まれるなら偶奇をずらせるので良さそう。

　ただ、さらに、
・「RBBRBB」（Rの間に偶数のものが二つある）が含まれていたら即ダメ、にも気付かなくてはいけない。
R(x)BBRB(y)Bのxからyを考えると、xの左右どちらかがRのとき、yの左右は両方Bなのでダメだった。

　これらが分からなくてはいけなかった。

　WAが出たテストケースから、何文字のとき間違っているか？　などを推測しながらやらないと解けなかった。時間があったら解けたかもしれないけど、コンテスト中だったら、ランダムテストを書いて考えなければ解けなかっただろうから、短い時間で解くのは結構厳しいね。
時刻: 0 件のコメント:
ラベル:

2024年11月11日月曜日

Codeforces Round 986 (Div. 2)

　Dまで四完。Eは実装間に合わず。

コンテスト後のツイート

E. Alice's Adventures in the Rabbit Hole

　ツイートした方法であっていた。

　単純に、トポロジカルソート順にDPの値を更新していく……とかじゃなく、枝分かれしたら、そこから一番近い葉まで一気に値が決まる、みたいな感じなので実装に戸惑ったことが間に合わなかった原因か。
　トポロジカルソート順でも、どこから値が伝搬してきているか？　みたいなのを持てばできるとは思ったけど、それもちょっと大変。

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

THIRD プログラミングコンテスト2024（AtCoder Heuristic Contest 039）

　94位。悪くはないけれど……。

コンテスト後のツイート




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

トヨタ自動車プログラミングコンテスト2024#11(AtCoder Beginner Contest 379)

　Fまで六完。

コンテスト後のツイート

G - Count Grid 3-coloring

　解法はあっていた。
　DPをdictで実装したらAC。dict→listに直してTLEを解消することはよくあるけど、逆は珍しい。気付かなかった。


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

2024年11月9日土曜日

yukicoder contest 452

　一問も解けなかった。ずっと参加していたわけではないけど、Aに30分以上はかけたのにひどい。


No.2953 Maximum Right Triangle

　求めたい点Bの座標は(x,y) + k(-y,x)と表せると勘違いし、WAを重ねた。
　kが実数ならこれで良いのだが、kが整数なら、これで全ての格子点は表せない。gcdを考えなくてはいけないとコンテスト終了間際に気付いたが間に合わなかった。

No.2954 Calculation of Exponentiation

　たくさんWAを出した後にAC。
　こういう問題で、たくさん提出してACするのはあまり意味ない気もする。　

No.2955 Pizza Delivery Plan

　一応自力AC。

　巡回セールスマン問題のbit DPをした後、3^Nのbit DPをすれば良いと気付いた。しかし、forループの順番を間違えてWAを出してしまった。

No.2956 Substitute with Average

　一回WAを出したが、WAが出たtestcaseを見て正しい解法に気付きAC。

　累積和みたいなことをしたい（Zero-Sum Rangesみたいなことをしたい）けど上手くいかないかなぁ、と考えていたら、A_iが30以下という制約の意味が分かった。
　そこまであっていたのだから一回でACしたかったね。（A_iが左のいくつかの要素の平均になっている、ということしか考えておらず、右のいくつかの平均になっている場合を考えていなかった）
時刻: 0 件のコメント:
ラベル: ,

2024年11月5日火曜日

yukicoder contest 261

　Dまで四完。

コンテスト後のツイート

No.1172 Add Recursive Sequence


　（以前ちょっと読んで挫折したことがあったはずなのだが……）読みやすく、すんなり理解できた。
　が、実際に実装するとなると累積和の添え字など迷いどころが多くかなり大変。線形漸化式を加算するクエリの問題を見たら、この提出を見に戻った方が良い気がする（かといって、ライブラリにするほどの出現頻度はないはず）。


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

2024年11月4日月曜日

Codeforces Round 984 (Div. 3)

　Fまで六完。Gはコンテスト終盤に思いついたのだけど、実装する気力が湧かなかった。最初考えていたものを提出したらWAで、ちょっとデバッグがやりにくいWAの出方だったので、実装したとしても間に合っていなかった気がする。

　いつものDiv.3よりやや簡単めで、特にEまでは楽な気がしました。
　Fは、0^1^2^3=0、4^5^6^7=0のように、累積xorが四つ周期になることを利用する知識問題という印象でした。


G. Library of Magic

　二分探索すれば解けそうだが、三つの数字のxorが0だったときが困る。

　が、よく考えると、最上位bitを固定すれば、そこに三つ数字が含まれていてxorが0になることはないし、（同じ数字ではないので）二つが0になることもない。
　なので、解ける……と思ったらWA。

　冷静になると、一回につき二分探索を行う回数が最大60回くらいかかるので、制限回数である150回をオーバーしてしまう。
　"xor 1 n"と聞けば、三個の数のxorは分かるので、二分探索するのは二回にできてAC。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)