No.2078 魔抜けなパープル
解説AC。
魔法を使う回数で全探索というのを本当に思いつけなかった。kの魔法とk+1の魔法を使うとき～とかは考えたのに……。
No.2080 Simple Nim Query
一番右端の1個じゃないindexを調べればいいよね？ と出したけどWA。
結局、解法はあってて、全部1のときの答えを逆にしていたのでした。一番最初に書いたところなので、そこが間違っているとは思わなかった……。
2022年9月26日月曜日
2022年9月25日日曜日
トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)
Eまで五完。
コンテスト後のツイート
トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270) Eまで。F思いつけなかったのダメ。
— titia (@titia_til) September 24, 2022
A A|B
C どこから来たかを持ってdfs
D 貪欲にとったらWAが出たので、ゲームDPを再帰で書いた。
E 何周するか二分探索。その後シミュレーション。
F - Transportation
解説AC。
最小全域木を作る問題なので、クラスカル法かをプリム法を使うしかない。（一応、他にブルーフカ法というのもあるが、あまり使わない）
空港・港とあるが、それぞれを使う・使わないで四種類ありそう。
コンテスト中、ここまで考えて、止まってしまった。
あとは、「超頂点を作って空港や港を処理する」というのを思いつかなくてはいけない。見たことないなら仕方ないが、何問も類題を解いているのに思いつかないのはまずい。
ただ、超頂点を作る、という手法を思いつかずに問題を落としていることは結構多い気がする。自分の苦手な方法なのかもしれないので、気を付けよう。
なお、PyPyだと制限時間がきつい。毎回グラフを構築していると間に合わないため苦労した。
G - Sequence in mod P
解説放送を見てAC。
B=0ならBaby-Step Giant-Step法が使えるので、それを応用できないか、と考えると大体そのまま解ける。Baby-Step Giant-Step法をよく覚えていなかったのは問題だけど、まあ平方分割ですね。
ACするためには、A=1やA=0の場合をケアしないといけない。
2022年9月24日土曜日
Codeforces Round #822 (Div. 2)
Cまで三完。
D. Slime Escape
コンテスト中は主に区間DPを考えていて解けなかった。
コンテスト後、解説を読んでもよく分からなかったけど、ちゃんと整理したらACできた。
左右どちらに進むにせよ、得できるなら得をしたい。
ので、累積和と、累積minを考え、累積和がプラスになった箇所について、「いくつ以上のHPがあれば得できるか」を調べる。
それを貪欲に取っていけば良い。
2022年9月22日木曜日
UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)
Fまで六完。
コンテスト後のツイート
UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269) GH分からない。
— titia (@titia_til) September 17, 2022
C bit全探索
D dfs
E 二分探索を二回。
F 等差数列の和。がんばる。
G - Reversible Cards 2
解説放送を見てAC。なるほど、という感じ。
コンテスト中、表と裏の総和がMという条件を使うのだろう、とは考えたが、二乗のDP解も、種類数がルートで抑えられるというのも分かっていなかった。
後者はともかく、前者のDP解法が見えなかったのはまずい（二乗DPが思い浮かべば、それを高速化しよう、ということで後者が見えるかもしれない）。まず、計算量が悪くても解ける方法がないかを考えなくてはいけなかった。
2022年9月19日月曜日
Kick Start Round F 2022
全完できたが苦労した。実装大変でした。
コンテスト後のツイート
D 平面走査（イベントソート）。BIT二つ用意して、一つは、その区間で仕事がx個ある人数は何人か？ を管理。もう一つは、人数*仕事の数を管理。前者のBIT二分探索で、K人になる箇所を調べ、後者のBITで答えを出す。
— titia (@titia_til) September 18, 2022
2022年9月17日土曜日
yukicoder contest 360
A一完。Bが分からなかった。
No.2071 Shift and OR
解説AC。
コンテスト中、Nが16以上なら答えが$2^16-1$になることにはすぐ気付いたが、その後が分からなかった。正当性のない、maxを持つbit DPを（コンテスト後に）投げてWA。
正しい解法は、もっとシンプルに、A[0]からA[i]までで、何の数字が作れるかを持つDP。遷移先が高々16個なのでこれで計算量も間に合う。
言われてみればこれで良いけど、気付きにくい気がする。
No.2072 Anatomy
自力AC。
後ろから見てUnion-find……と、すぐ思ったのだが、なぜかそれで上手くいかない気がして時間がかかってしまった。
No.2073 Concon Substrings (Swap Version)
一応自力AC。
indexを3で割った余りについて、c, o, nの個数を考えるのは良い。ただ、その個数だけ見たのでは作れない場合がありそう？ というのがこの問題の胆。
どういうとき作れないか分からず戸惑ったが、答えがNになるのは、concon...と並ぶときだけだと気付いた。他の場合が作れることが分からないままACしたが、冷静に考えれば当たり前か。
No.2074 Product is Square ?
解説AC。
Nの二乗が通る制約なのでそれを利用できないか、と考えるべきでした。
2022年9月13日火曜日
Codeforces Round #820 (Div. 3)
実装が大変な回だった。なんとか全完。
コンテスト後のツイート
F 9で割った余り=各桁の和%9を使う。累積和で頑張る。実装が大変。
— titia (@titia_til) September 12, 2022
G DP[i][j]=i回消して、j番目より前のTの出現まで消えているときの場合の数としてDP。i番目のTの出現を消すためには、i～x番目までのTの出現を消さなくてはいけない……というxは二分探索（または尺取り）で求められる。実装が大変。
2022年9月3日土曜日
freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）
Fまで六完。
コンテスト後のツイート
freee プログラミングコンテスト2022（AtCoder Beginner Contest 264） Fまで
— titia (@titia_til) August 13, 2022
B 1/4をお絵描きした。
C 行・列にbit全探索だが、実装が大変。
D 愚直で良い。Cよりかなり簡単。これはCとD入れ替えるべきでしょ。
E クエリを後ろから見る。実装が面倒。
F DPだが、遷移を立式するのが非常に大変。
G - String Fair
解説放送を見てAC。
・後ろ二文字を持ってDP
という方針を思い付けたなら、グラフの問題（最短経路問題）となり、負辺があるのでベルマンフォードを使って解くことができる。
Ex - Perfect Binary Tree
解説放送を見てAC。
ただのDPなのだが、遷移式を立てるのに非常に苦労した。特に工夫する方法もなさそうなので、落ち着いて、整理して考えるしかない。
登録:
投稿 (Atom)