2022年3月31日木曜日

UTPC 2021

　Aだけ解きました。


M - Open the Door

　解説を読んだけどよく理解できず、雰囲気でAC。

　一番当たる確率が高い方から貪欲に選んだ方がいいのは、まあそう。
　問題は、外れを引いたとき確率がどう変化するかというところ。

・一回外れを引くごとに、(1-q)倍になる

　と分かるかがポイント。

　たとえば、もしq=099ならほぼ確率pで当たり、その回で当たらなかったということは次回以降ほとんど当たることはなくなる。
　当たりが確率p*0.01くらいになりそう、ということから推測できる。
時刻: 0 件のコメント:
ラベル:

灘中入試コンテストday1

　ABCEの四完。Dが思いつけなかったのはまずい。


No.1345 Beautiful BINGO

　私の場合、考えて分からなかった問題のほとんどでは、解説を読んでもすぐに理解できない。解説を見て、何言っているんだろう？　と考え込むことも多い。（いや、これって大抵の人はそうだと思うんだけど。解説を読んですぐ分かるよう問題は自力で解けませんか？）

　逆に言えば、解説を見たらすぐ分かるような問題を落とすのはまずいと思っている。この問題はそうだったのでまずい。

　Nが16以下ということでbit全探索を当然考えるのだが、縦横斜めあわせると最大34個あるから上手くいかないと思ってしまった。
　が、縦と斜めだけbit全探索すれば、残り（横）は貪欲で良い。

　……言われてみれば当たり前ですね。半分全列挙に近い考え方か。

　なお、PyPyだと多少実装を工夫しないとTLEするようです。最初、何も工夫せずに書いたコードはTLEしました。

No.1348 Split Tile

　実験エスパーにより自力AC。

　実験はitertools.permutationsでやったけど、解説にあった二乗のDPは一応思いついていたのでまあ良いか。
時刻: 0 件のコメント:
ラベル:

2022年3月30日水曜日

パ研合宿2021　第3日「パ研杯」

　ヒューリスティック問題のHに手をつけた後、部分点集めを頑張った。Dは解きたかったね。

コンテスト後のツイート

D - 試験作り

　ソートしてDPだとは思ったが、ソートの仕方を詰められなかった。

　DP[Aで要した時間] = (Bより何問お得か, Bがかかった総時間)　として、DPを更新する際、Aについては全部を見るので、Bについてどうソートするかが重要。Bの数が小さい順に問題は解かれるので、Bを小さい順にソートしておけばOK。

　コンテスト中はAについてソートしていたので部分点しかもらえず。どういう理由でソートするのかちゃんと考えなくてはいけなかった。




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

2022年3月26日土曜日

yukicoder contest 337

　Cまで三完。


No.1886 Sum of Slide Max

　全部の順列の和を求めるので、平均が分かれば良さそう。

・1, 2, ... , NからK個選ぶときの最大値の期待値

　が分かれば良い。

　コンテスト中はこれが分からず困った。
　ただ、検索すると、こういう事実が出てくる。

　今回、実数でも離散でも一様なのは変わらないので、この期待値は$(N+1)*K/(K+1)$で良い。
時刻: 0 件のコメント:
ラベル:

2022年3月25日金曜日

CodeTON Round 1 (Div. 1 + Div. 2, Rated, Prizes!)

　Dまで四完。

コンテスト後のツイート

E. Equal Tree Sums

　解法ツイートを見てAC。コンテスト中は最初にに頂点が決まると他が埋まるな～という方針しか考えていませんでした。そこから方針転換するのは難しい。

　頂点に書かれた整数の総和をSとする。ある頂点に書かれた整数をx、その頂点から出ている辺の本数をyとすると、S-xはyで割り切れなくてはいけない。特に、Sが0だとバランスが良くて上手くいきそうなので、試してみると上手くいく。

　つまり、木を二部グラフにして、片方に(その頂点から出ている辺の本数)を、片方に-(その頂点から出ている辺の本数)を割り当てれば良い。
時刻: 0 件のコメント:
ラベル:

2022年3月23日水曜日

Educational Codeforces Round 125 (Rated for Div. 2)

　pretestはDまで四完。Dの前にしばらくEを考えていたけど、分からずDへ戻った。
　システムテストでDが落ちた。

コンテスト後のツイート


D. For Gamers. By Gamers.

　システムテストで落ちたのは、枝刈りが悪さをしていたためでした。
　コストの小さい順に見ていく際、「あるコストで倒せるD*Hの値」が今調べているものを上回っていたら次のタイプは移していたのだけれど、それではダメですね。

　たとえば、
　コスト2で2, 4, 6, 8, ...と処理し、
　コスト３で3, 6, 9, ...と処理しているとき、6ではお得じゃないけれど、9ならお得なことがあり得た。（具体的には、testcase 125。これで落ちた）

　これを直すとTLE→PyPy3-64にしたらAC。こどふぉのPyPy3とPyPy3-64の速度感覚はいまだに全く分からない。大きい数を使いたいときは-64にした方が良いっぽいというのが基本だろうけど、それで遅くなることもあるため。

E. Star MST

　解法ツイートを見てAC。
　1から頂点iに重みxの辺が、頂点jに重みyの辺が張られているとき、iとjの間の辺の重みはy以上k以下になる。それらを掛け合わせたものの和が答え。

　それをDPで求める。制約を見るとDPっぽいが、それで正しかった。

　ある頂点まで見て～だと上手くいかないが、
　1と重みx以下の辺が張られている頂点の個数がy個のとき～と考えると上手くいく。
　次に重みx+1の頂点をz個張るとき、y+z個の頂点間で、今まで辺が張られていなかったところ全てについて、重みx+1以上の辺を選んで良いと確定するため。

　頂点ごとに見ると上手くいかないが、このように重みの小さい辺から張っていく、とするとDPが回る。
時刻: 0 件のコメント:
ラベル:

2022年3月20日日曜日

Hokkaido University Competitive Programming Camp 2021 Day 2

　20分くらいでAとDの二問だけAC。


C: 見つからないように移動する

　H,Wがそれほど大きくならなそうなので、各見張りそれぞれについて見張っている菱形の境界のマスを通れなくしておけばいいか、と思ったがTLE。

　実際は、imos法を使って高速化することができる。

　ただ、最初に書いた方法でも、O(HW*√HW)くらいなのでは？　高速な言語なら通りそうな気もするけどどうだろう。

E: 正四面体転がし

　底面が黒マスになるのは、元のマスから向かいのマスへ何回かいったところ、ということは分かったが、判定が分からなかった。
　（+1, +1, -1）を繰り返すということは分かったので、それを使ってどうにかしようとしたのだが偶奇に気付かず。

　ただ、自分が考えた、(+1, +1, -1)を使って絶対値の和を減らしていく……という方針でも解けるはずなので、ACできなかったのは良くないですね。
時刻: 0 件のコメント:
ラベル:

Kick Start 2022 Round A

　久しぶりにKick Startに参加してみました。

コンテスト後のツイート

Dの復習はやらなそう。
時刻: 0 件のコメント:
ラベル:

2022年3月19日土曜日

Hokkaido University Competitive Programming Camp 2021 Day 1

　ABの二問しか解いていないけど、一応参加。


J: GCD swap

　解説AC。

　とりあえず、１, ５, ７を取り除いて考えるのはOK。
　そうしたら、6が動けないということに気付いていなかった……。ちゃんと具体例を書いていれば分かったと思うので、面倒がらずに手を動かそう。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 336

　A一完でした。

コンテスト後のツイート


 No.1879 How many matchings?

　上記ツイートの通りで、奇数の場合もDPでいけるということをヒントにしてAC。

　偶数のときにDPになることには気付いていたのだから、奇数の場合も同じ方針で立式、遷移を書いてみるべきだった。
時刻: 0 件のコメント:
ラベル:

2022年3月16日水曜日

AtCoder Beginner Contest 243

　ABCDGで五完でした。

コンテスト後のツイート

E - Edge Deletion

　解説AC。

　制約からワーシャルフロイドをすることは思いつくけど、その後が難しい。
　解説の条件で良いことを思い付くのも簡単ではないし、証明も容易ではない。
　ただ、コンテスト中全く考えなかったか？　と聞かれると、頭を掠めた気はするので、試すことはできたかもしれない。

F - Lottery

　解説ACしたが、解説を見てもしばらく分からなかった。

　N種類のどれが既に手に入ったか？　を持ってDPしたくなるが、それだと間に合わない。「くじを一回引く」ごとに更新していくようなDPではダメ。これに捉われていると解説を読んでも全く分からなくなってしまう。

　発想を転換して、K個のマスに1～Nの数字を埋める、と考える。
　「各商品について考えて、その商品は何回目のくじで当たったか？」でDPテーブルを更新していく。これだと、「残っているマスx個のうちy個にi番目の商品が当選した」のなら、(x, y)という二項係数を掛けることで更新できる。

　詰まったら発想を転換しよう、という気持ちでいれば難しくないはずなのだが。
時刻: 0 件のコメント:
ラベル: ,

2022年3月13日日曜日

Tohoku University Programming Contest 2021

　AとC二問の二問しか解いてないけど、一応参加。


G - Tree Happiness

　解説AC。
　解かれている人数が多いし、これは解けなくちゃいけなかったけど、全然思いつかなかった……。

・木の問題で、辺に数字が書いてあるとき、ある二点間のpath上にあるxorは、根からの累積xor二つのxorとなる

　というのは他の問題でも使ったことあったと思う。
　使えるようにしたい。
　
時刻: 0 件のコメント:
ラベル:

yukicoder contest 335

　Cまで三完。Cで詰まって睡魔に襲われてしまった。


No.1870 Xor Matrix

　各bitごとに考えるのはOK。
　一つ答えが見つかれば、行や列のサイズによって答えが変わってきそう、というのも分かる。
　問題はその答えがどうなるかだけど、一番後ろの行、列に押し込めば$2^{(N-1)*(M-1)}$ですね。

No.1871 divisXor

　これは自力AC。
　2ベキを考えると良い。

No.1872 Dictionary Order

　自力AC。
　部分和問題なのでDPしたくなる。
　見出し数列が辞書順最小になるか？　を調べたいので、Pの値が小さいindexから順に調べたい。
　そのとき、（Aに関する）index iを使ったとして、index i+1以降の数字たちだけで和をMにできるか？　が分かれば良い。
　これは、後ろからDPをすれば前計算できる。


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

2022年3月10日木曜日

Codeforces Round #776 (Div. 3)

　Eまで五完。

コンテスト後のツイート

　Fは未読。

G. Counting Shortcuts

　自力AC。最初の提出はmodの取り忘れでシステムテストで落ちたが、まあ。

　個数を調べるのはDPでやるしかない。最短距離の経路の個数を調べるならDPで求められる。
　問題は、最短経路+1のものをどう求めるか、だが、これも同じような感じでDPするしかなかった。

　スタートから同じ距離のもの同士を結ぶところで+1用のテーブルに遷移させ、後は同じようにやる。

　コンテスト中も似たようなことを考えていたのだけど、最短距離+1の経路になるかどうかを判定するところで、スタートとゴールから距離を調べる系かと思って混乱してしまった。
時刻: 0 件のコメント:
ラベル:

AtCoder Beginner Contest 241（Sponsored by Panasonic）

　Fまで六完。

コンテスト後のツイート

G - Round Robin

　解説AC。
　フローで判定する問題。
　問題文を読んでフローらしさを感じるのは難しいけれど、「iさんがx勝で他の人たちがx勝未満、という状況は可能か？と捉えると、フローを使いたい気持ちにもなるか。

Ex - Card Deck Score

　解説放送を見て、さらに解説も参考にAC。

　形式的ベキ級数には慣れないが、この問題は形式的ベキ級数を用いて立式しようという気持ちになり、立式はできた。
　問題はその後の式変形。部分分数分解を用いた後、さらに
$\frac{1}{1-x}=1+x+x^2+x^3+\dots$
　を用いて変形するところはテクニカルに見えるが、慣れればできるのかなぁ。

　なお、解説放送でBostan–Mori のアルゴリズムの解説もしてくれたのはありがたかった。これで典型90埋まるかも？
時刻: 0 件のコメント:
ラベル: , , ,

2022年3月9日水曜日

AtCoder Beginner Contest 242

 　Eまで五完。

コンテスト後のツイート

F - Black and White Rooks

　解説放送を見てAC。

　コンテスト中、包除原理だと思ったが、詰められる気がしなかった（及び、Gの方がAC人数が多かった）ため飛ばした。

　意外とシンプルな包除で、多分解説を見なくても解けたと思う。
　解説を見ても何を前計算ができるかピンと来ず、毎回包除をやるのだから八乗になってしまうのでは？　と思ったが、自分で書いて見たら納得できました。こういうのは実際書いてみた方が分かりやすいですね。

　あと混乱していたのは、包除原理で「黒が使う行がk1行, 列がl1列。白が使う行がk2行, 列がl2列の場合の数」を求めるとき、そのk1, k2, l1, l2が小さいバージョンの答えを使う（それらを除いていく）のか？　と考えたこと。
（公式解説を見るとこれでも解けた模様。公式解説の「1. 動的計画法による解法」ですね。なんかこの方法も包除原理の一種と思っていた気もするけど、「これは包除原理じゃない」ということを頭に叩き込みたい）

　包除原理でそれは使わないのですね。
　「黒が使う行がk1以下, 列がl1以下。白が使う行がk2以下, 列がl2以下の場合の数」というものたちだけから「黒が使う行がk1行, 列がl1列。白が使う行がk2行, 列がl2列の場合の数」を求められる、というのが包除原理なのですね。

G - Range Pairing Query

　解説放送を見てAC。

　Mo’s algorithmは平方分割の一種と思っていたのですが、具体的には理解していませんでした。「二次元のクエリを先読み＆平方分割」と思って良いのかな。
　二次元クエリを平面上にプロットしてみると分かりやすかった。二つパラメーターがあるとき、困ったら平面にプロットしてみるのは鉄板ですね。

　参考：昔のMo’s algorithmの問題

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

2022年3月7日月曜日

yukicoder contest 334

　A一完で終了。

コンテストへのリンク

No.1861 Required Number

　部分和問題なので（bitsetを使うかはともかく）DPするしかない。
　だが、必ず使う数の判定はどうしよう？　その数字を除いたDPをN回すれば求められるけど……で止まってしまった。

　方針は合っていて、「DPをN回やる」という部分の高速化を考えなくてはいけなかった。左右からDPをすれば、判定は一回O(K)でできるので間に合う。
　左右からDPを思いつかなかったのは良くない。

No.1863 Xor Sum 2...?

　一応自力AC。
　コンテスト中、Bが1になる区間で条件を満たすことはないと分かり、Aたちの和とXORが等しくなるとき（つまり、繰り上がりがないとき）は、尺取り法で調べることができる、というところまでは気付いた。

　あとは、その区間の中で、$B_i$が1になるものが奇数個ある区間の個数を求めるところ。
　これは累積和を使えばいけるのですね。
　Bの累積xorの変化を見てみると、その変化の仕方は二通りしかない。ので、二通り累積和を持っておけばいける。

No.1865 Make Cycle

　解説AC。
　二分探索するだけの問題なのに思い付けなかったのはまずい。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Round #774 (Div. 2)

　Cまで三完で終了。


D. Weight the Tree

　解説AC。木DPでいける。

　木DPはコンテスト中も考えたのだが、goodの頂点の個数を求める部分はそれでいけるけれど、和の最小化の部分が無理な気がして捨ててしまった。……が、普通にいけました。

　ただ、復元部分もちょっと非自明な気がする。「トポロジカルソート順（DPテーブルを作ったときと逆順）に頂点でのDPテーブルを見て、得ならその頂点をgoodにして、その周囲の頂点はgoodにしないと印をつけておく」という方法でいける。よくあるDPの復元のように、遷移を逆に見ている感じではないので、不思議な復元に思えた。
時刻: 0 件のコメント:
ラベル:

2022年3月6日日曜日

デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）

　Eまで五完。

コンテスト後のツイート

F - Construct Highway

　一応自力AC。落ち着いて考えたら実装できた。

　ツイートした通り、「連結成分から出る辺が残り1個」なものから「2個以上のもの」へ繋ぐことを繰り返せば良い。これをどう実装するかだが、最初に、連結成分ごとにまとめたものを一点と思って実装する。そうすると、実装上ネックになる「最初からある辺」を無視することができる。各連結成分ごとに、どの頂点から何本ずつ辺が出ているかを覚えておけば、そこから復元できる。

　コンテスト中もこの方法は考えたのだけど、一旦まとめてからもう一度復元するのは面倒な気がし、一気にやる方法を考えてしまった。（一気にやる方法もあるかもしれないけど、上手くいかないときは）横着しちゃダメね。

G - Builder Takahashi

　フロー（最小カット）なのは問題を読めば分かり、グラフの構築もそう難しくはない。
　あとは復元。解説動画を見てしまったが、グラフがスタート側とゴール側に分かれるということに思いがいけば難しくなかった。

　が、その後ACするまで苦労したのは、最初に与えられるグラフが有向グラフだと勘違いしたため。何度かWAを出した後問題文を読み直してようやく気付いた。復元部分で間違っているんだろうという先入観があったせいだけど、こういうミスはひどい。

Ex - Dice Product 2

　DPを立式し、どこをまとめて高速化すれば良いかは自力で分かった。
　が、実装が上手くいかず、解説放送を見てAC。
　やることは分かっても、この実装はなかなか難しいですね。
時刻: 0 件のコメント:
ラベル: ,

2022年3月3日木曜日

AtCoder Beginner Contest 240

　Fまで六完。

コンテスト後のツイート


G - Teleporting Takahashi

　解説放送を見てAC。
　「二次元の問題なら45度回転することで解ける」ということに気付けば解けるが、これ、どうやれば思いつけるんだろう？
　コンテスト後のツイッターを見ていると、これは知識として持っている人も結構いた模様。思いつくのは難しい気がするので、知識として頭に入れておくべきか。
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)