2023年3月29日水曜日

パ研合宿2022　第2日「パ研杯」

 　全問見て部分点を稼ごう、という方針に従ったのは良いけど、Cは解けないとねぇ。

コンテスト後のツイート

C - Collaboration

　解法はコンテスト中に考えたものであっていたが、実装に苦戦。

　たとえば、AとBをマージした配列において、l<x<r<yのとき、xの前やrの後ろもケアしなくてはいけないことに気付かず、WAを量産してしまった。

　TLEもしたが、セグ木をSparse tableに直してAC。
時刻: 0 件のコメント:
ラベル:

2023年3月25日土曜日

yukicoder contest 382

　A一完。


No.2253 Ignore Subtle Differences

　コンテスト後、自力AC。

　コンテスト中は、二頂点がx軸上にある二等辺三角形を探していたが、それでは見つからない。（ツイッターを見ていたら、これでも見つかるという発言を見つけた。実装ミスしていたっぽい）
　コンテスト後、(0, 0), (x, y), (y, x)のような三角形を探索すれば良い（y=x*tan15°付近を調べる）と気付いてAC。

　もっとも、「ほぼ正三角形」が二等辺三角形に限られることにも気付いてなかったので、二等辺三角形のみを探索していたのも偶然に過ぎない。

No.2254 Reverse Only

　解説AC。

　kが小さいときは全て並び替えできるだろうとは思ったが、それ以上考えられなかった。N-1のときだけ例外なのは結構意外。
時刻: 0 件のコメント:
ラベル:

Educational Codeforces Round 145 (Rated for Div. 2)

　Cまで三完。


D. Binary String Sorting

　swapは高々一回で良い＆DPで解けるというツイートを見てAC。

　コンテスト中は、左右で0にする区間、1にする区間で分けた後、境目が"1110"などのときもswap三回で処理した方が良いと思い、実装に戸惑っていた。
　多分、これでもちゃんと実装すれば解けるのだが、この場合は"0"を消去した方が得ですね。

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

Codeforces Round 859 (Div. 4)

　全完。

コンテスト後のツイート

　速く解けたとは言い難いが、全完できて良かった。
時刻: 0 件のコメント:
ラベル:

2023年3月19日日曜日

yukicoder contest 378

　AHCの途中に少しだけ参加してBまで二完でした。


No.2226 Hello, Forgotten World!

　自力AC。

　あてはめられる一番最後のところを"helloworld"として他は"a"にすれば良いかと思ったが、それだとWA。テスト1にある、"helloworl?elloworld"のようなとき、hを入れてしまいダメ。

　この問題ではあてはめられる場合全て試しても間にあう制約なので、試さなくてはいけませんでした。

No.2227 King Kraken's Attack

　デバッグでtestcaseを見てAC。

　横パンチの回数を全て試し、縦パンチの回数で二分探索すれば良いのだが、二分探索の上限など罠が多く、WAを量産してしまった。

No.2228 Creeping Ghost

　自力AC。これはお絵描きして頑張るしかないね。

No.2229 Treasure Searching Rod (Hard)

　自力AC。
　sampleに描いてある図が優しく、これを元に立式すれば良いので簡単。式だけでも解けたとは思うけど、倍くらい時間かかったと思う。

No.2230 Good Omen of White Lotus

　自力AC。
　以前、一度問題を開いたとき、「期待値DPか。面倒くさそう」などと思って閉じてしまったが、良い知らせに行く回数だけ求まればよく、期待値DPなど必要なかった。問題文はちゃんと読みましょう。

　（H, W）にも白い蓮の花が生えると思って、サンプルが合わない……と悩んでいた何十分かももったいない。

　こういうのは防ぎようがないねぇ。
時刻: 0 件のコメント:
ラベル:

2023年3月18日土曜日

yukicoder contest 381

　Dまで四完。


No.2250 Split Permutation

　解説AC。

　解説と同じことを考えたのにBITで上手く処理できなかった。
　敗因は、$2^3*(2^3-1)$のような式を展開しなかったこと。展開したら、何をBITに入れたら良いか分かりました。億劫がらずに計算しましょう。

No.2251 Marking Grid

　解説AC。

　最初の言い換えが難しいし、その後、連結成分さえ分かれば良いという部分も簡単ではないと思う。
　でも、これくらいさくっと解けるようにならなくちゃいけないんだなぁ……。
時刻: 0 件のコメント:
ラベル:

2023年3月13日月曜日

AtCoder Regular Contest 158

　Cまで三完。

コンテスト後のツイート

D - Equation

　解説放送を見てAC。

　コンテスト中はあまり考えなかった。けど、解説で同次式を利用すると見ても比の利用を思いつかなかったので、解けた可能性は少ないか。
　大学受験数学では典型だったね。
時刻: 0 件のコメント:
ラベル:

2023年3月11日土曜日

yukicoder contest 380

　Cまで三完。


No.2242 Cities and Teleporters

　ダブリングというキーワードを見てAC。

　キーワードを見た後も実装ミスしたのは反省。
　ライブラリ化した方が良いのかな……。

No.2243 Coaching Schedule

　解説AC。

　包除原理っぽく見えても、何で包除すれば良いかは難しい。

　（解説のコピペだけど、）

・集中精進期間をK日として、K 日のうち d 日を指定し、その d 日間で N 人全員に教えてもらう。その d 日間では何も教わらない日があってもよい。（ただし、同じ日に同じ分野を 2 度以上教わらない。）

　とすると、包除できる。

　別の言い方で書くと、集中精進期間をK日としたとき、「教わる期間がd日以下」という条件で包除する。

　これで求められる、と分気付けるようになりたい。

　（その後、FFTを使えば解けると気付く部分も難しそうだけど、解説を見てしまったのでまあ）
　
時刻: 0 件のコメント:
ラベル:

2023年3月9日木曜日

Codeforces Round #854 by cybercats (Div. 1 + Div. 2)

 　Eまで。ただし、Gは典型だったようなので、ちゃんと復習したい。

コンテスト後のツイート

F. Halve or Subtract

　解説AC。
　難しいけれど、そこそこ時間があったのだから解きたい問題だったなぁ。

　Aを大きい順に並び替えたとき、

・halve and subtract →　halve　→　subtract　→halve　→　何もしない

　という順序になるので、最初の二つの区間の長さを全探索する。

　まず、
・subtractした後、halveするのは無駄
　を押さえた上で、

・何もしない区間があるとすれば、一番小さい部分
　と気付かなくてはいけない。

　その上で、
・残りの区間でsubtractする部分は、連続な箇所になる
　と気付くのが重要。

　これは、bの前後が一番subtractの効果が大きいと気付けば直感にも適する。

　はじめから上記に気付くのは難しいが、二乗が通る制約なのだから、何かの区間と何かの区間を全探索できないか？　と考えていけば気付けたかもしれない。

G. Count Voting

　解説AC。

　理解してしまえば確かに典型なのだが、解説を見て包除原理というキーワードを知っても理解するまでなかなか苦労した。

　包除原理を使う。

　まず、チームごと、投票する人が決まっている場合を考えよう。

　このときは、「k人以上同じチームに投票した場合の数」を求めると、包除原理を使って答えが求められる。（包除原理を使うときは、「～以上」または「～以下」の数え上げをすることになるので、そういう数え上げができないか考えるのが大事そう）

　k人が同じチームに投票し、残りの人の投票先がチームごとにx票、y票だった場合、残りの人の投票先の決め方は、$(n-k)!/(x!*y!)$のようになる。分子は後からかけることにし、分母の部分をDPで求める。

　ただし、同じチームから複数人が自分のチームに投票する場合は、「チームの中で誰を選んだか？」を考慮しなくてはいけないことを忘れずに。

　チーム内に複数投票先がある場合は、上記のことを各チームごとに行う。
　そして、そのDP結果をmergeしていけば（畳み込みも使えるが、今回は必要ない）最終的なDP結果を求めることができる。
　


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

2023年3月8日水曜日

AtCoder Beginner Contest 292

 　Fまで六完。

コンテスト後のツイート

G - Count Strictly Increasing Sequences

　解説放送を見てAC。

　解説を見ても良い実装方法が分からず、実装を見てもなかなか理解できず苦労した。
　こういう書き方ができるようになるにはどうしたら良いのかなー。こういうDPを解けるようになるのは非常に大事だと思うんだけど。

Ex - Rating Estimator

　自力AC。

　BITで[1, n]の和 - n*B　を持ち、遅延セグ木でそのmaxを管理した。普通のセグ木でできるのかな、と実装を始めたら、遅延セグ木が必要なことに気付いて直したため結構時間を食った。
　ただ、今kyopro_friendsさんの解説を見たら、遅延セグ木を使うならBITはいらなかったぽいね……。

　なお、遅延セグ木上の二分探索は実装していなかったので、普通に二分探索をしたが間に合った。
時刻: 0 件のコメント:
ラベル:

2023年3月6日月曜日

Educational Codeforces Round 144 (Rated for Div. 2)

　Cまで三完。


D. Maximum Subarray

　「耳DP」というキーワードを見てAC。

　この問題を耳DPと読んで良いかは微妙な気もするけど、

・kが小さいからそれを利用してDPしよう

　と考えなくてはいけなかった。

　添え字のミスで3WA出したのは反省。
時刻: 0 件のコメント:
ラベル:

2023年3月4日土曜日

Codeforces Round #855 (Div. 3)

　全完したがシステムテストでFが落ちた。根付き木のHashを初めて書いた。


コンテストへのリンク

コンテスト後のツイート

F. Dasha and Nightmares

　解説AC。
　使わない文字を一つ決めて、それを使っていないものだけ抜き出したら、奇数個あるものの集合だけで計算ができることは気付いていなかった。

　ただ、本番で投げたのと計算量自体は変わっていない気も……。




　まあ、Fはともかく、Gで根付き木のハッシュを、この前のABCで木の重心について理解できたことで、長年解説を理解できなかったこの問題を（解説）ACできたのが大きな収穫。
　嬉しいね。
時刻: 0 件のコメント:
ラベル: ,

yukicoder contest 379

　Cまで三完。 Aに苦戦したのは反省。


No.2235 Line Up Colored Balls

　解説AC。

　期待値の線形性は考えたのだが、その後の考察がおかしかった。色が同じボールの間に他のボールが挟まる確率は……などと考えていたが、これでは線形性は使えない。

　（tester解の通りだが）ボールを順番に並べていくと考えて、

・（i番目と$i+1$番目が異なる確率）の総和と考える

　すると、

・色iのボールが最後以外で取り出される確率は$(S-1)/S$
・次のボールが色iでない確率は$(S-x_i)/(S-1)$

　から求めることができる。

No.2236 Lights Out On Simple Graph

　解説AC。

　半分全列挙と言われても頂点を半分にすることしか思い浮かばず、辺で半分全列挙すると思いつかなかった。
時刻: 0 件のコメント:
ラベル: ,

2023年3月1日水曜日

AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）

　Fまで六完。全完の多い回だったが、GもHも解けず。


G - OR Sum

　解説AC。

　bitごとに考えるのは自然で、その後どうするか。
　bitset高速化を主に考えてしまったが、上手くいかず。
　bitごとに考えるなら、1と0のみの配列になるのでorと掛け算が一致する。なので、FFTが使える、という問題だった。

Ex - Balanced Tree

　解説AC。

　重心分解は使ったことがなかった。勉強になりました。
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)