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問題をまとめてある。頭に入れておきたいね。


2024年4月10日水曜日

Codeforces Round 938 (Div. 3)

 Gまで六完。

コンテスト後のツイート

H. The Most Reckless Defense

 解説AC。

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

 難しい問題ではないのだが、問題文の内容を理解するのが難しいと思う。

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を公約数に緩和するのがポイント。

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

2024年4月4日木曜日

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

  Fまで六完。

コンテスト後のツイート

G - Alone

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

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

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




2024年4月3日水曜日

AtCoder Beginner Contest 347

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

コンテスト後のツイート

F - Non-overlapping Squares

 解説AC。

 長方形三つは「品目」と覚えると良いらしい。知らなかった。
 これを知っていれば多少実装は大変だが難しくはない。

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を指しますね。

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のものが見つかった。