2024年7月31日水曜日

AtCoder Beginner Contest 322

　Eまで五完。

コンテスト後のツイート


F - Vacation Query

　コンテスト後、Pythonで遅延セグ木を使った実装だとTLEになる……という話を聞いて避けていたのをようやく実装。
　普通に遅延セグ木で通りました。（ただし、二重配列にしないという工夫はしている）

　なお、ツイートで書いている解法だと、遅延セグ木に乗せるものが足りていないですね（多分、実際に実装したら気付いたでしょう）。

　演算が多要素×多要素の場合も簡単に書けるように、遅延セグ木をライブラリ化しておくべきですね。


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

2024年7月28日日曜日

Codeforces Round 962 (Div. 3)

　全完。

コンテスト後のツイート


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

2024年7月27日土曜日

yukicoder contest 438

　A、Cの二完。Aが難しくて困ったけど、解けて良かった。（それと比べるとCは簡単だった）


No.2820 Non-Preferred IUPAC Nomenclature

　色々参考にしてAC。

　どうやって解を構成するかは分かったのだけど、木DPとかマージテクとか考えてひどいことに。
　行きがけ、帰りがけを考えればDFSで構成することができた。やっぱりDFS系は苦手なのかなぁ。
　
時刻: 0 件のコメント:
ラベル:

2024年7月25日木曜日

Codeforces Round 961 (Div. 2)

　B2もDも解けず。

コンテスト後のツイート

B2. Bouquet (Hard Version)

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

　x,x+1が使う候補のとき、

・xをできるだけ使う　→　x+1をできるだけ使う　→　xのものをx+1に変換する

　で良いのではないか、というのはコンテスト中にも考えていた。（それで本当に良いのかは分かっていなかったが）
　ただ、ツイートの方法で良いと思ったため方針転換できなかった。

　x,x+1を使う個数の和をm/x個とすると、その個数がxの個数より大きかったとき、最低でも、求める数より大きくなってしまう。それでダメだった。
　（簡単に反例が見つかるかと思ったが、そう簡単でもなかった。ランダムテスト書くしかなかったか）





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

2024年7月23日火曜日

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

　Fまで六完。

コンテスト後のツイート

G - Sum of Tree Distance

　解説AC。

　マージテクで解けると聞き、マージテクで通そうと思った後も自力で解けなかったのは情けない。「ある頂点から根の方向へ何歩進んだか？　の総和」を持たなければいけない気がし、それだと一歩一歩全ての色について更新しなくてはいけないと思ってしまった。

　が、根からの距離の総和さえ持てば代用できるため、マージテクが適用できる。



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

2024年7月22日月曜日

AtCoder Beginner Contest 363

　Eまで五完。

コンテスト後のツイート

C - Avoid K Palindrome 2

　Pythonで通す方法の一つとして、

・from more_itertools import distinct_permutations

　を使うというものがあったらしい。
　知らなかったので仕方ないか。

F - Palindromic Expression

　ツイートした解法で、bit全探索の部分で、「Nより大きくなるなら探索をやめる」という枝狩りをしたらACできた。
時刻: 0 件のコメント:
ラベル:

2024年7月20日土曜日

yukicoder contest 437 ('09 Contest 002 day2)

　A一完。


No.2812 Plus Minus Blackboard

　コンテスト中に、プラス、マイナスそれぞれ絶対値の小さいものについて操作を行っていけば良いのでは？　と思いついたが証明が分からず、証明を考えていたら終わってしまった。
　コンテスト後、証明は分からないけどとりあえず投げてみたらACだった。

　解説を見るとこの方法で正当そう。
　ただ、この方法を直接示しているわけではないので、「この方法を示そう」と考えるのでは難しかったか。

No.2816 At Most Two Moves

　解説AC。

　1以外の点について、1から一歩でいけない確率は1/2で、2歩でいけない確率はいくらだろう……と考え、中継点と繋がっていないときだな、と思ったはずなのに答えが出せなかった（解説を見た）。そこまで考えたならすんなり分かって欲しいのだが。

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

Codeforces Round 959 sponsored by NEAR (Div. 1 + Div. 2)

　Eまで五完。

コンテスト後のツイート


F. Stardew Valley

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

　使っても使わなくても良い辺たちの連結成分ごとに見て木DPするという方針は思いついていなかった。
　この問題が類題だったようだけど、思い出せなかった。

　ただ、この部分が解けたとしても、オイラー閉路を構築する部分で躓いていただろう。DFSして帰りがけ順に見ていけば良い（！）とは知らなかった。

G. Minecraft

　こたつがめさんの放送の振り返りを見てAC。解けなきゃいけない問題だった。

　繰り上がりの数を持ってDPする方針は問題を見てすぐ思いつたのに、繰り上がりの値が大きくなるかも、と思って実装できなかった。
　高々nになる、というのは言われれば当たり前。Fを考えている合間に見たため長いこと考えたわけではないが、思いつかなかったのは悔しい。

　なお、定数倍高速化をしないと自分のPyPyの実装では通らなかったので、コンテスト中に通すならChatGPTを活用しなくてはいけなかったかも。


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

2024年7月15日月曜日

yukicoder contest 436 ('09 Contest 002 day1)

　A一完。BでWAが出て、10分以上見直したがどこが間違っているか分からず、頭が働いていないと思って寝てしまった（こんなのばっかり）。


No.2804 Fixer And Ratism

　WAが出たテストケースを見て、「同時に帰った人々の名前をレートが低い人から順に出力」するなら、パソコンを使用可能にしていない人→パソコンを使用可能にした人の順ではいけないことに気付いた。

　結構気付きにくいところだと思うので仕方なかったか。

No.2805 Go to School

　自力AC。

　スタートとゴールからダイクストラですね。

No.2806 Cornflake Man

　自力AC。

　小さい順に調べていけば良さそう→0以上M以下の全ての整数について調べなくてはいけないかと思ったが、よく考えたらAに入っているものだけ調べれば良いと気付いてAC。

No.2807 Have Another Go (Easy)

　自力AC。

　確率を求めると思って答えが合わず（計算量も間に合いそうになく）悩んでしまったが、場合の数を求めると気付いたらDPでできた。

No.2809 Sort Query

　テストケースを見てデバッグしたけど方針は自力でAC。ただ、タグの「クエリ先読み」は見た。

　最初、SortedMultisetを使えばそのままできそう？　と思ったけど、全くそのままではなかった。クエリの2（ソート）が与えられてから、再度クエリの2が与えられるまでの間はSortedMultisetの中身は変更せず、クエリの2が来るたびに変更するようにすれば良かった。

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

2024年7月14日日曜日

トヨタ自動車プログラミングコンテスト2024#7（AtCoder Beginner Contest 362）

　Fが解けず。

コンテスト後のツイート

F - Perfect Matching on a Tree

　解説AC。

　重心で分けることはコンテスト中も考えていたが、正当性が分からなかった。主客転倒を考えるのはなるほど。

G - Count Substring Query

　以前自分で書いたAho-Corasick法の実装を参考に書き直したが、こっちの方が汎用性がある気もする。今度書くときはこっちを元にすべきか。
時刻: 0 件のコメント:
ラベル: , ,

2024年7月13日土曜日

Codeforces Round 957 (Div. 3)

　Fまで六完。


E. Novice's Mistake

　（n, a）を定めると、bは高々一つ。また、単調なので二分探索で求めた。
　そして、その個数が少なそうなので、n=1以外のときは埋め込んだ。

　でも、n*aは高々7桁なので、二分探索も埋め込みもいらなそうですね。


G. Ultra-Meow

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

　二項係数でやる方法は考えたはずなのだけど、三乗だと思って棄却してしまった。ちゃんと計算量を見積もらないと。
　その後、nを増やしていったときDPでできるのでは？　とその方針ばかり考えてしまった。
時刻: 0 件のコメント:
ラベル:

2024年7月10日水曜日

Codeforces Round #956 (Div. 2) and ByteRace 2024

　Cまで解いた後、Dをすぐに思いつかず睡魔に襲われ途中でやめてしまった。パソコンを消した後でDの解法に気付いたが実装する気力が湧かなかった。


D. Swap Dilemma

　いくつか実験したら、転倒数の和の偶奇では？　と気付いた。

　まあ、見てすぐ分かるものではないし、すぐ分からなかったのは仕方ないかなぁ。

E. I Love Balls

　自力ACしたが時間がかかった。

　specialじゃないカードは交互に二人のプレイヤーにわたるので、その回数で分配すれば良い。
　specialなカードは、specialじゃないカードと一緒にわたる or 全部配り終わってからわたるのいずれか。なので、n-k+1回わたる回数があるので、それで分配すれば良い。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)