2024年2月29日木曜日

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)

　Fまで六完。連敗は止めた。

コンテスト後のツイート

G - Christmas Color Grid 2

　解説AC。

　lowlinkでできるらしいと聞いて、lowlinkのライブラリは持っていたし、コンテスト中にも考えたのに……と思ったが、何個の連結成分に分かれるかは考えたことがなかった。
　さらに、実は自分のlowlinkライブラリが間違っていたことが判明。AOJでは通っていたので安心していたが……。

　コンテスト中に通せる可能性はほぼなかったし、lowlinkライブラリの間違いを直せたので良かった。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Round 929 (Div. 3)

　全完。
　最近、Div.3も全完できていなかったので、全完できて嬉しい。

コンテスト後のツイート


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

2024年2月28日水曜日

yukicoder contest 418 (Re: start!)

　Dまで四完。


No.2651 [Cherry 6th Tune B] Complex комбинат

　解説AC。

　複素数の式変形を頑張るしかない。

　解説を見て式変形を追うこと自体は難しくないが、自分でやるのはかなり厳しい……と思って、他の人がどうやって通したのかとTwitterを見たら、Wolfram alphaを使っていた人が多そうだった。
　とはいえ、Wolfram alphaに入れれば解説の式変形をすぐやってくれるという感じでもないので、何をWolfram alphaに入れるか？　また返ってきた式をどう捉えるかといったあたりに習熟する必要がありそう。


No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ

　解説AC。

　問題を見て、焼きなまし？　と思い、本当にそれで良いのか解説を見たら、Mo's algorithmを使うと条件を満たすと書いてあった。

　Mo's algorithmは思いついたけれど、それで条件を満たすとは思わなかったなぁ。ちゃんと検討すべきだった。

　なお、まず山登りを書いてみたが（PyPyでは）TLE、その後Mo's algorithmでACしました。

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

2024年2月27日火曜日

鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）

　Fまで。

コンテスト後のツイート

G - Leaf Color

　解説放送を見て、 Auxiliary Treeを使ってAC。

　仕組みは理解したが、汎用性のない実装になってしまった。
　ライブラリ化はしていないけど、一応このときの提出にコメントをつけたので、後で見ても分かるといいな。


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

2024年2月25日日曜日

Educational Codeforces Round 162 (Rated for Div. 2)

　Dまで四完。さらにレートを落とした。ひどい。

コンテスト後のツイート

E. Count Paths

　マージテクでAC。

　最近のABCで似た問題が出題されていることに引きずられてしまったが、マージテクでも解けると言われたら普通に解けた。
　コンテスト中もマージテクを検討したので解けておかしくなかったはずなのに、なぜかライブラリを持っていない解法に突撃したのがひどい。
　このABCをまだ復習していなかった、というのも反省。
時刻: 0 件のコメント:
ラベル: ,

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）

　Eまで五完。

コンテスト後のツイート

F - Black Jack 

　解説AC。

　コンテスト中は三分探索に固執してしまった。
　解説を見たらすぐ理解＆ACできたので、解けなくてはいけない問題だったのは間違いない。

　ただ、今見ても三分探索で通りそうに思えるので、三分探索に飛びついたのは仕方ないかな、という気もする。方針転換できなかったのは反省。

G - Retroactive Range Chmax

　自力AC。

　双対セグ木にheapqを乗せるだけで簡単だった。ちゃんと順位表を見てこっちから解くべきだったけど、Unratedだったからまあ良いか。




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

2024年2月23日金曜日

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

　Fまで。

コンテスト後のツイート

G - Highest Ratio

　解説放送を見てAC。

　「凸包」というキーワードを見ても分からず解説放送を見た。

　式から図形的性質を読み取るのは昔から苦手だったので解けなくても仕方なかったかな……とも思わなくはない。しかし、実験して、左端lに対して、右端rがどの位置で最大値を取るか？　と考えていれば凸が見えなくても解けて欲しい気もする。

　いずれにせよ、難しい問題ではなかった。

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

2024年2月21日水曜日

think-cell Round 1

　D1まで。D2もEも分からず、またレートを下げる。

コンテスト後のツイート

D2. Sum over all Substrings (Hard Version)

　解法ツイートを見てAC。

　大事なことを見逃していた。「1、010、001100、……のいずれかを置く」と考えていたが、置くのは基本的に「010」だけで良かった。
　これに気付かなくてもD1がACできてしまうから、DPの遷移について考えなかったなぁ。

　そう気付けると、D2のDPは自然に書けた……のだが、思いつくまで結構時間がかかった。時間がかかった原因は「配るDP」が頭にあったせいかなぁ。「もらうDP」で書こうとすると簡単に書けた。

E. 2..3...4.... Wonderful! Wonderful!

　解説AC。

・出来上がりったsequenceがgoodになる条件を見つける
・goodでないsequenceの数える

　の二つができなくてはいけなかったが、どちらもできていなかった。

　できなかった一因は、実験して数を数え、oeisなどでどうにかしようとしてしまったことか。二項係数の和みたいになることは分かったが、そこから考察が進まなかった。

　実験すること自体は間違っていないので、そこから情報を得ようとするところに問題があった。自分には、実験した後、頭を使わずどうにかしようとしてしまう傾向がありそう。実験の結果を眺めて、なんで二項係数の和になるんだろう？　という方向で考えなくてはいけない。（そういう風にしたら思いついていたかはまた別の話だが）


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

2024年2月20日火曜日

AtCoder Regular Contest 172

　体調が悪かったのと、AHCの途中ということもあってUnrated参加で三完。Ratedで出ていたら+10くらいだったみたい。

コンテスト後のツイート

D - Distance Ranking 

　解説AC。

　解説を読むとこの問題も解ける可能性がある問題だった気もしてしまうが、本番中は立方体で正三角形を作るということすら全く思いつけておらず、焼きなましなんかしようとしていたんだよね。惜しいところは全くなかった。

　二次元でも解けそうな問題（実際、サンプルは二次元で解を作っている）のにN次元で出題されているのだから、それを利用した解法がないか考えなくちゃいけなかった。それで発想できたかはともかく、そこは反省点。

E - Last 9 Digits

　解説AC。

　実験して予想する方法も、10=2*5を利用する方法も、思いついて良いものだった。こういう、色々試してちょっと強引な方法でも解ける方法で解ける問題は取らなくてはいけないのに。




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

2024年2月16日金曜日

Codeforces Round 926 (Div. 2)

　Dまで四完でさらにレートを落とす。問題を理解するのに時間がかかったのが敗因の一つだけど、他の人も読解には苦戦してそうだねぇ。考察速度も遅かった。

コンテスト後のツイート


F. Sasha and the Wedding Binary Search Tree

　大小の配列が一意に決まるという情報を得てAC。

　これ、言われてみれば当たり前なのにコンテスト中に気付かなかった。そして、ただdfsする感じで良いのに、しばらく考えないと復元方法も分からなかった。



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

2024年2月14日水曜日

Codeforces Round 925 (Div. 3)

　全完。と思ったらシステムテストでDが落ちた。

コンテスト後のツイート

D. Divisible Pairs

　dictのハッシュ衝突対策で、randomな数をdictのキーとxorしなくちゃいけないのに、値とxorしていた。
　多分、このミスをしたのは初めてですね。そんなにしないミスだと思うけど、まあ気を付けよう。

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

2024年2月10日土曜日

yukicoder contest 417

　Eまで五完。

コンテスト後のツイート

No.2626 Similar But Different Name

　解説AC。

　ローリングハッシュ（など）を使えば大文字小文字の違いを区別しない場合の一致できるかは判定できる。問題は、大文字小文字が異なる箇所が1文字以上K文字以下という方。bisetか？　と思ったが、あまり時間に余裕がなさそうで止まってしまった。

　FFTを使うとは思いつかなかったが、言われてみると典型っぽいので、この手法は覚えておきたい。SとSより短いTに対して、Sの全ての連続部分列とTを比較するときにFFTは使える。
　ただ、FFTを使うとしても、使い方がすぐには思いつかなかった。色々な解法ツイートを見て、大文字=1、小文字＝-1とするのが分かりやすく感じ、その方法でACした。
時刻: 0 件のコメント:
ラベル: ,

2024年2月7日水曜日

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

　Eまで五完。

コンテスト後のツイート

F - Usual Color Ball Problems

　解説放送を見てAC。

　Kがなかったら尺取りで簡単なのに……から進まなかったが、

・どの色を何箱使うか、さえ分かれば答えは計算できる

　ことに気付けば、Kがあっても尺取りでやることができた。

　確かにちょっと気付きにくいけれど、尺取りでやるしかないと思えば十分思いつける内容だった。
　コンテスト中はGばかり見てたから仕方ないけど、これは自力で解けても良かったね……。

　

G - Tree Inversion 

　解説放送を見てAC。

・木において、部分木は区間で表せる

　を利用し、あとは差分計算で解く問題で、難しい知識は必要なかった。そういう意味では解けなくてはいけない問題だった。ここで既出だったようだけど、既出じゃなくてもまあまあ解かれていた気がする。

　しかし、解説を理解してからも答が合わずかなり時間を費やしてしまった。
　値の足し引きをどこで行うかにかなり神経を使った。

　実装の仕方が悪いんだけど、おとなしく再帰で書いた方が良いのかなぁ……。

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

Codeforces Round 923 (Div. 3)

　Fまで六完。FでLOWLINKを持ち出すまで迷走したのが痛い。

コンテスト後のツイート

G. Paint Charges

　一応自力AC。

　まあDPするしかないけど、同じやつを左右両方に使うと困る。なので、左方向に使ったやつだけ特別扱いする別のDPテーブル用意して、そこからは右に遷移しちゃいけないよ、とした。

　なんか無理矢理やった感じが強いけど、これ良いんだろうか。
　→Hackされたが修正してAC。
時刻: 0 件のコメント:
ラベル: ,

2024年2月5日月曜日

AtCoder Regular Contest 171

　AB二完。まあまあ速かったのでレートが減ることはなかったが、難しい問題が解けないなぁ。

コンテスト後のツイート

C - Swap on Tree

　解説AC。

・どの辺について操作するかを決めたとき、「各頂点で、どの順番で辺を消していくかを決めるかと操作終了時のAが定まり、それらは全て異なる」

　ということに気付かなくてはいけなかった。

　コンテスト中は、ある頂点をどこへ移動させるか……というようなことを考えていて、順番が大切だということは分かっていた。そこから類推して、順番さえ決まれば数列が定まるのでは？　と思わなくてはいけなかった。

　その後の木DPも結構難しいが、ここまで分かっていれば遷移式は立てられるか。

D - Rolling Hash

　解説AC。

　コンテスト中は問題を読み、ニ十分くらい考えたが何も思いつかなかった。BがPの生成元になっているかで条件が変わってくる？　とか考えていた時点でダメ。まず、B=1のときに解けるかを考えるべきだった（今回は、それが答えになっている）。Bが本質的には関係なさそうなのはまあそうなので、B=1で考えるのは自然。

　B＝1のときはグラフの彩色数を求めれば良い、というのもしばらく納得できなかったのは、彩色数の定義が頭に入っていなかったせいか？

　グラフの彩色数自体はこのFを解いていたのだが、このときは彩色数とはあまり考えなかったからねぇ。

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

2024年2月4日日曜日

日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）

　Fまで六完。

コンテスト後のツイート

D - Synchronized Players

　コンテスト中は、四方向の移動を愚直に書いていた（四回コピペ）したらTLEして困っていたのだけど、for文で

・for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:

　みたいに書いたら700msになった。

　PyPyのforは遅いからコピペした方が速いと思ってたんだけど、今は違うのかな……。

F - Product Equality

 何個かmodを取り、乱択するのが想定だったらしい。なるほど。

G - Smaller Sum

　コンテスト中、wavelet matrixで解ける気がして検索したらけんちょんさんのこの記事が出てきた。

　ここにあるコードを使って通そうとしたが修正に時間がかかり通せなかった。C++のコードを改造する力も付けたいね……。

　公式解説のmerge-sort treeを使う方法も理解しないとね。


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

2024年2月3日土曜日

Codeforces Round 922 (Div. 2)

　Dまで四完でさらにレートを落とす。

コンテスト後のツイート

E. ace5 and Task Order

　コンテスト中提出したコードをPython3で出したらあっさり通った。

　PyPyのprint(flush=True)が遅いというのを忘れていたのが敗因。こどふぉでは、「PyPy3でTLEしたらPyPy2やPython3でも試してみる」というのも重要ですね。PyPy3-64ができてから、PyPy3-64とPyPy3しか試さなくなっていた気がする。

F. Caterpillar on a Tree

　解説AC。

　解法ツイートで貪欲でいい、というのを見てもどう貪欲すれば良いか分からなかった。

　全ての葉を通れば良いので、葉の順番を考えれば良いというのは分かったが、その上で、

・子の中からmax深さが低い順にたどって、葉をつないでいくのが最適

　と気付くと、そのうちどこかの葉で親まで戻ったとき、何歩省略できるかが分かる。
　あとはソートしてやっていけばOK。

　E捨ててFいっていれば良かったかな、とコンテスト直後は思っていたけど、これだと無理だったかな……。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)