2024年4月28日日曜日

AtCoder Regular Contest 176 （Sponsored by Mynavi）

　Cまで三完。ARCでこれくらいの順位が取れると嬉しい。

コンテスト後のツイート

D - Swap Permutation


　解法ツイートで行列累乗で解けるというのを目にしたが、ある(a,b)というペアが最終盤面でどのような位置にあるか？　という遷移を考えてしまい、上手くできなかった。

　index i, i+1が最終的にどの数字になっているか？　に着目するのは言われてみれば自然。コンテスト中に解けなかったのは仕方ないにせよ、行列累乗で解けると言われたら思いつきたかった。
時刻: 0 件のコメント:
ラベル:

2024年4月25日木曜日

Educational Codeforces Round 163 (Rated for Div. 2)

　Eまで五完。

コンテスト後のツイート

F. Rare Coins

　解説AC。

　自分になじみのない解法が必要かと思って解説を見たのだが、普通の方法で解けた。

　ちゃんと問題を整理し、1/2の確率で自分のお金が増える、相手のお金が増える、というのを元のお金を調整して、「1/2の確率で差を減らす」と解釈するとシンプルな二項係数の和になる。










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

2024年4月23日火曜日

Codeforces Round 940 (Div. 2) and CodeCraft-23

　Dまで四完。ARCの後だったこともあり、前半は休み休みやっていた。

コンテスト後のツイート

E. Carousel of Combinations

　解説AC。

　Combi(n, k)*(k-1)! mod k の和を求める問題。実験コードを書いてこれを計算してみると、k=4と素数のとき以外は0になること、かつ、規則的に値が変化することが分かる。ｋを固定したとき、最初に値が正になるのはn=kのときで、k-1。そこからkごとに-1し、0になったらまたk-1に戻る。（これはkが素数のとき。k=4は2と0を交互に取る）

　これが分かった後、埋め込みか？　などと考えてしまい解説を見てしまったが、累積和を二回やるのが正しかった。規則的に値が変化するのだから、累積和を考えるのは自然。

　大体解けたけどTLEが微妙ってとき、変な手法を考えてしまうのは悪い癖。まともに計算量を減らす手法を考えるようにしないといけない。






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

2024年4月22日月曜日

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）

　G解けず。Fで苦戦したため順位は悪い。

コンテスト後のツイート

G - Mediator

　解説AC。

　マージテクで解いた。コンテスト終盤にマージテクが使えるんじゃないか？　というアイディアは思いついたけど、具体的な解法には思い至れなかった。
時刻: 0 件のコメント:
ラベル: ,

2024年4月20日土曜日

yukicoder contest 428

　Dまでの四完。Eが解けそうで解けず、FはTLEに苦しむ。



No.2732 Similar Permutations

　4で割った余りで分類し、同じものが二つあれば1,2を入れ替えて置けばOK。
　ただし、Nが5以上ならこれでOKだが、Nが小さいときはこれだと答えが探せない場合があるため全探索。

　コンテスト中、こういう解法を考えたがWAが出たので、何か考察ミスがあるのだろうと別の解法を探してしまった。
　が、コンテスト後、改めて考えて見ると正しそうな気がし、コードを見直したら実装ミスに気付いた。（Nが小さいとき全探索する部分でミスがあった）

　これで提出したがWA。
　Xで割った余りが3や4の場合は、1,2を置くのではダメですね。2,3を置くようにしてAC。

　解説を見たら、2で割った余り（つまり偶奇）が同じものが二つあれば、上と同じような議論ができるらしくびっくりした。

No.2733 Just K-times TSP

　各頂点を何回通ったかと、最後に通った頂点を持ってDPすれば良い。PyPyだと制限時間が厳しく、コンテスト後に定数倍高速化を頑張ってなんとか通した。

　しかし、writer解がPyPyで、シンプルかつ高速に書けていた。こういう風に書けば良かったのか……。
　同じような風に書こうとして上手くできず、itertools.productを使ったのだが。

No.2734 Addition and Multiplication in yukicoder (Hard)

　自力AC。

　ちょっと実験してみると、最終的にできる数字はA[i]たちを適切に並び替えたものになると分かった。
　なら、A[i]を文字列とみてソートし、その順に置いて行けば良いのかと思ったがこれだとWA。

　よく考えると、"2"と"21"なら"21"の方が先に置いた方がお得。

　じゃあ、"2"は"22222222222222222"として"21"は”212121212121212121"のように元の数字を繰り返したものとして判定すれば良さそう。こうみなしてソートした後、並べていったら（TLE、MLEにちょっと苦しんだけど）ACできました。
時刻: 0 件のコメント:
ラベル:

2024年4月18日木曜日

AtCoder Beginner Contest 349

　Eまで五完。Eまでが速かったのでギリギリ黄色に復帰できました。

コンテスト後のツイート

F - Subsequence LCM

　素数の個数でいけるというのを手掛かりにAC。

　ゼータ変換を使う方法は思いつかなくても、DPで素数の個数^2でやる方法は難しくなかった。これはコンテスト中に落ち着いて考え直していたら通せていたはず……。

　



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

2024年4月15日月曜日

Educational Codeforces Round 164 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Chain Reaction

　解説ツイートを見たところ、√max(A)回加算するというところは合っているみたい。
　→落ち着いて書き直したら答えがあった。

　ただし、PyPyだと制限時間が厳しく、PyPy2で2999msでACした。ルートだけでなくlogもかかっているからねぇ。二分探索使わない方法はあるのだろうか……と書いていたら、使わなずにできそうな気がしてきた。

　a/xの繰り上げが変化する場所をメモしていけばいい（後で累積和を取る）ので、前半はxを一個ずつ増やし、後半はa/xの値を一個ずつ減らしていけば良さそうです。
時刻: 0 件のコメント:
ラベル:

2024年4月14日日曜日

Codeforces Round 939 (Div. 2)

　Cまで三完。

コンテスト後のツイート

D. Nene and the Mex Operator

　コンテスト五分後くらいに実装終わり、そのコードでACできました。
　この問題の実装に時間がかかったのは良くない。


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

2024年4月13日土曜日

yukicoder contest 427 (ゲーム問題コンテスト)

　Cまで三完。


No.2724 Coprime Game 1

　解説AC。

　N/2以上の素数は使えないけど、それ以外の数は使えるはず→WA
　解説を見たら、Nが素数の場合後手必勝と書いてあった。これを忘れていました。直してAC。

No.2725 Coprime Game 2

　自力AC。

　未証明で投げたらACした。解説を読むと、この証明は自力でできた気がする。（まあ、直感が正しいというのも大事なことだと思う）

No.2726 Rooted Tree Nim

　解説AC。

　「個数制限付きNim」と、「Staircase Nim」に関する知識があれば解ける。後者についてはyukicoderの問題で見た記憶があったけど、覚えていなかったなぁ。

　この問題の後に書かれた記事のようだけど、kobaeさんの記事でNIM問題をまとめてある。頭に入れておきたいね。


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

2024年4月10日水曜日

Codeforces Round 938 (Div. 3)

　Gまで六完。

コンテスト後のツイート

H. The Most Reckless Defense

　解説AC。

　タワーごとに独立でやれば良いのでは？　と思ったが、よく分からず解説やこたつがめさんの放送を見た。（独立にやれば良いというのは正しかった）
　bit DPを使って解けば良い、というあたりで問題文を誤読していたことに気付いた。……というか、その部分以外も、問題文を正確に把握できていなかった。

　難しい問題ではないのだが、問題文の内容を理解するのが難しいと思う。
時刻: 0 件のコメント:
ラベル:

2024年4月8日月曜日

yukicoder contest 426

　AB二完。


No.2716 Falcon Method

　自力AC。
　二分探索だとは思ったが、添え字で混乱したりしてコンテスト中に通せなかった。

No.2717 Sum of Subarray of Subsequence

　（一応）自力AC。

　立式して、Wolfram alpfaに突っ込んだら正しい式を返してくれたので解けたが、式変形まで自分でやれと言われたらできる気がしない。

No.2718 Best Consonance

　解説AC。

　gcdを使えば立式できるがgcdはA[i],A[j]を決めないと計算できない。
→gcdの代わりに約数を使っても答えは変わらない！　約数なら予め列挙できる！

　と、gcdを公約数に緩和するのがポイント。

　解説を見ても理解できず、解法ツイートをいくつか見たら理解できた。

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

2024年4月4日木曜日

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）

 　Fまで六完。

コンテスト後のツイート

G - Alone

　解説・解説放送を見てAC。

　各数字のx個目を見て、その数字を一つだけを含む区間がどこなのか？　というのを求める方法は分かっていたが、重なる区間の処理をどうすれば良いかが分からなかった。

　それが長方形区間に対応する→平面走査　と考え、遅延セグ木を用いれば処理できる。
　ただ、平面走査した後も、どう遅延セグ木を用いれば良いかは解説を見なければ分からなかった。ただ、ここは典型問題で、 （公式解説にも書いてある通り）Library Checkerにもあった。




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

2024年4月3日水曜日

AtCoder Beginner Contest 347

　過去最高順位で黄色に復帰！

コンテスト後のツイート

F - Non-overlapping Squares

　解説AC。

　長方形三つは「品目」と覚えると良いらしい。知らなかった。
　これを知っていれば多少実装は大変だが難しくはない。
時刻: 0 件のコメント:
ラベル:

April Fools Day Contest 2024

　遅刻参加してABFの三完でした。FでQRコードを思い付けたのは嬉しい。


C. They Have Fooled

　解説AC。
　コンテストに関連するのか？　とはちょっと考えたが、問題数とは気付かなかった。

D. Are You a Procrastinator?

　解説AC。
　時間が影響するとは考えなかった。Procrastinatorという単語になじみがあれば思いつけたんだろうか。

G. Mathematician Takeover

　ヒントを見てAC。
　なるほど、確かにコンピューターサイエンスではlogといえば底が2のlogを指しますね。
時刻: 0 件のコメント:
ラベル:

2024年4月2日火曜日

AtCoder Grand Contest 066

　一問も解けず青に落ちた。

コンテスト後のツイート

A - Adjacent Difference

　解説AC。

・市松模様に分ける
・片方を0, もう片方をd (mod 2*d)にする

　どちらも考えたはずなのに、一次元でも上手くいかない気がして捨ててしまった。上手くいかなかったのは、mod 2*dで良いと明示的に考えられていなかったのと、例で計算するのが下手だったせいか。

　ただ、公式解説の、これで良いという証明は自分には思いつきにくいものだった。これを思い付ける数学的証明能力があれば解けていたかもしれないので、そこを反省しよう。

B - Decreasing Digit Sums

　解説AC。

　5ベキに注目するのは全く考えなかった。N=3となる小さい数として625にはちょっと着目したけどそこから考察を進められなかった。

　単純にその数のNの値を考えるのではなく、二倍していったときに桁和がどう変化するかに着目するのが大事だったのですね。

　答えを直接求める実験をするのではなく、ちょっと一般化したような内容で実験をするというのはしばしば必要となる手法。直接答えを求める実験しかせず何も情報を得られず失敗したことは結構記憶にある。そのあたりが反省点か。

　なお、コンテスト中は、あるSにx*2ベキを文字列として足したものを繋げていってNが大きくなるものを探すような実験をしていた。（これでN=19まで見つけられた）
　この実験コードの2ベキの部分を5ベキに変えたら（理由はよく分かっていないが）N=51のものが見つかった。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)