2022年11月30日水曜日

AtCoder Beginner Contest 278

 　Fまで六完。

コンテスト後のツイート

G - Generalized Subtraction Game

　解説AC。
　
　真似っこ戦略は考えたがGrundy数を考えなかった。
　Grundy数さえ思いつけば自然に解ける（計算量が若干不安だが）し、ゲームなのだからGrundy数を考えるのは自然だった。

　ただし、実装はなかなか大変。
　最終的には、sys.setrecursionlimit(10**7)が必要なことに気付かず苦戦してしまった。これがなくてもREではなくWAが返ってくるため気付きづらい。
時刻: 0 件のコメント:
ラベル: ,

2022年11月27日日曜日

Codeforces Global Round 24

　Cまで三完。


D. Doremy's Pegging Game

　「N/2個連続で消した時点で終了」だから、最後に消す頂点とその幅を固定して、残りの頂点から何個消すかを選べば、二項係数と階乗で計算できる。

　「残りの頂点から何個消すかを選べば」というところでハマっていた。残りの頂点からも、N/2個連続で選んではいけないので、選び方を求めるのにDPが必要で、計算量三乗かかるんじゃないか、と。
　しかし、最初に選んだ箇所がN/2以上なので、残りの頂点はN-(N/2+2)以下だから、そういう事態は起きない。だから、組み合わせで計算すれば良いと分かる。

　普通はハマらないような箇所でハマって解けなかったのはおかしい。

E. Doremy's Number Line

　ツイッターで解法を検索してAC。

　どういう問題か理解するのが難しいが、整理すると、

・A[0]>=kならOK、A[0]+B[0]<kならダメ
・それ以外の場合、k-B[0]に色が塗れれば良い。そのためには、A[i]+B[i]>=kとなるようなiがあれば良い。
・一番最初に色を塗る際は、A[i]が大きいものを使いたいので、A[i]+B[i]>=kなるiのうち、A[i]が小さいものから使っていく。

　という感じになる。

F. Doremy's Experimental Tree

　解説ツイートを見てAC。

・Fを大きい順に見て、F[i][j]が繋がっていないなら、iとjは直接つながれている（Union-findで結ぶ）
・重さW[i][j]を知るためには、F[i][i]とF[i][j]を比較する

　一点目がポイント。小さいループの方がFの値は大きくなるので、これが分かる。

　ただ、PyPyだと時間の制約もメモリの制約も厳しく、ACまでは非常に苦労した。もうちょっと定数倍の良い解法がありそう？
時刻: 0 件のコメント:
ラベル:

トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)

　Dまで四完。


E - Cheating Amidakuji

　取り除かったときの結果と比較して何かする、という方針は考えたのだけど、うまくいかないと思ってやめてしまった。
　一つ取り除いたとき、最終結果とどう変わるか、と考えるのが重要だった。

　……というか、考えなくても分からないと厳しくって。

　一つ除いた場合とそうでない場合とを実験して比較して……というような手段を取れば確かに分かるのだろうけど、この問題はそこまでするような難しい問題ではないと思う。最終結果との比較でできるのかな？　と思ったら、解法のやり方でいけるのかな？　と思えて欲しいところ。
　そう思えなかったのは、頭が働いてなかったということなのかね。

F - BOX

　適切にUnion-findを使えば解けるということはコンテスト中から分かっていた。

　が、実装難しくないですか？　何を持てば良いか整理した後で、一時間以上実装にかかっている。
　コンテスト中に通すのは厳しかった気がする。こんなに解かれているのが不思議。

G - At Most 2 Colors

　自力AC。

　「自分と違う色が最も最近現れたのはいつか？」を持てば二乗DPになる。そこから、累積和を使って（セグメント木を使うこともできそう）高速化する。

　Gとしては簡単だし、今回のEやFと比べると簡単な気がする。Eは発想問題だから人によるかもしれないけど、Fよりは明らかに簡単では。
時刻: 0 件のコメント:
ラベル:

2022年11月23日水曜日

HACK TO THE FUTURE 2023 予選（AtCoder Heuristic Contest 016）

 　最終144位でした。

コンテスト後のツイート


　クリークに分解したのを上手く戻せたら……という方針でやっていて、どうもうまくいかないため、残り二日あたりで各頂点の辺の個数だけを見る方針に切り替えた。

　結論からいうと、どちらでも上位を狙えた模様。
　ただ、クリーク判定は他の方の解説など見てもいまいちやり方が分かっていないので、辺の本数だけ見る方針に早い段階で切り替えた方が上位に入る可能性は高かったか。

　辺の本数だけ見る方針でもTOP10に入れたらしい。
　ここで重要なのは、確率epsのノイズが入ったときどういう辺の個数の分布になるか、というところ。そのあたりの考察が甘かった。（クリークを考えたときや、epsが小さい場合でも、そのあたりをきちんと考えるのが大事だったみたい）

　この辺、ちゃんと考察を立式して考えるべきだった。まあ、上手い式が浮かんでいないから立式できていないのだけど、式を探す努力もしていなかった気がする。

　また、ノイズに強い「良いグラフを探す」というのは、結構序盤から時間があったらやろうと考えていて、結局最後までできなかった。この辺もできていればもうちょっと違ったかも。

　時間いっぱいやり切ったつもりだったけど、そう考えると結構やり残しはあるなぁ。
時刻: 0 件のコメント:
ラベル:

2022年11月22日火曜日

AtCoder Regular Contest 152

　AHCで疲れていたので、unratedで参加してAだけ解いて終了。


B - Pass on Path

　自力AC。

　どの休憩所からスタートし最初に進む方向を右・右、右・左、左・左と決めると、二分探索を使えばどこでぶつかるかが分かるので、それぞれ計算していく。というコンテスト中に思いついた方針で解けた。
　結構実装が大変。コンテスト中は、方針は思いつけても実装する気力がなかった。

　……と思ったが、「二人は同じ休憩所からスタートする」ものだと思って解いていた。別な休憩所からスタートしてもOKだとACしてからツイッターを見て気付いた。
　同じ休憩所からスタートして良いというの、あんまり明らかに思えないので、正しく読解していたら解けなかったかも……。

C - Pivot

　自力ACしたが、大量にペナを出してしまった。

　「通常の状態」と「反転した状態」を分けて考え、それぞれの変化はgcdになりそう……といったあたりは結構すぐ思いついたので、それをきちんと詰めれば答えにたどりついたのだが。きちんと詰めるのがなかなか大変だった。

D - Halftree

　自力ACしたが、時間がかかってしまったのでコンテスト中解けた気がしないなぁ。

　Nが偶数のときは作れない。
　Nが奇数で、NとKのgcdが1のときは、Kおきに順番に繋いでいけばOK。

　それ以外のとき。右へいくと+1、下へいくと+Kすると考えると、縦をgcd、横をN/gcdとしたグリッドとみなすことができる。
　このグリッドが縦横ともに奇数なことを利用して、木を作っていく。

　3*3での木の作り方を考えて、それをコピーしていく……と考えた。3*3のマスで木を作る（「N」の文字におまけがついたようなやつにした）。
　これをそのままコピーするとサイクルができてしまうので、一番上の行の以外では一ヶ所辺を減らせばOK。

E - Xor Annihilation

　解説放送を見てAC。
　問題文の読解が困難だったけど、maspyさんのツイートで理解しました。

・ボールの重み全部のxorは0である
・累積xorを考える
・ボールが合体することは、累積xorの一項が消えることに対応する

　というところまで気付けると、解説のような立式ができる。

　一つ目、二つ目は考えたが、三つ目に気付けなかった。
　ただ実験するだけでなく、「累積xorを使うと何か上手い性質が見つかるのでは？」と予想して実験するのが大切か。
時刻: 0 件のコメント:
ラベル:

Codeforces Round #835 (Div. 4)

　全完。Fでミスして時間かかってしまったけど、それ以外は良し。

コンテスト後のツイート


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

2022年11月12日土曜日

大和証券プログラミングコンテスト2022 Autumn (AtCoder Beginner Contest 277)

　Eまで五完。

コンテスト後のツイート

F - Sorting a Matrix

　解説AC。

　行については、最小値・最大値を見てソートするのはOK。
　その後、列について考えるとき、ある行の二つの列で大小関係があるときに辺を張り、ループしたらダメ、としたい。が、辺の本数が多くなりそうで困っていた。

　こういうとき使うのが、超頂点を加える手法ですね。
　ただ、最近、この問題で使った方法とは超頂点の使い方が違うのが難しい。「同じ数字たちをまとめるために超頂点を使う」という手法はなじみがなかった。
　（とはいえ、超頂点を使うこと自体を考えなかったのはダメ）

　なお、答が一致した後もTLEを取るために苦戦した。

G - Random Walk to Millionaire

　解説放送を見てAC。

　Xの二乗とは何か？　と考えたとき、「どこでレベルアップしたか？」の組み合わせと考えてDPへ持ち込む。
　考え方は分かるのだけど、この問題でこの手法を使うとは。

　ただ、この問題ではDPくらいしかやりようがないし、DPを高速化しようと思ったらXの二乗というところを上手く使うしかない。そう思えば、この変形をするしかない、と考えるのは自然だとは思う。

　しかし、元々積で与えられているものを分けて考えるというのはピンと来なくて。難しい。
時刻: 0 件のコメント:
ラベル: , ,

2022年11月8日火曜日

AtCoder Beginner Contest 276

　Fまで。

コンテスト後のツイート

G - Count Sequences

　解説放送を見てAC。

　単調増加な数列の個数を二項係数で考えるのはコンテスト中にも考えたが、二項係数でどうにかしようと思ったとしても、その後の処理もなかなか技巧的で難しい。
　かといって形式的ベキ級数を使う方法もそんなに簡単には見えないため困る。でも、形式的ベキ級数で立式はできるようになっておきたい。
時刻: 0 件のコメント:
ラベル:

2022年11月6日日曜日

yukicoder contest 367

　Bまで二完。


No.2119 一般化百五減算

　順番に中国剰余定理を使っていけば良いのは分かったが、TLEが取れなかった。

　TLEの原因は、割る数が大きくなり過ぎることを忘れていたため。割られる数が大きくなったときをケアするだけなく、割る数の方が大きくなったときについてもきちんと調べなくてはいけなかった。

No.2120 場合の数の下８桁

　教育的な問題。やり方を全然覚えていなかった……。

　2ベキ、5ベキ、それ以外で分ける。
　2ベキや5ベキを除いた部分は、$2^8$や$5^8$をmodとしたとき可逆になっているため、オイラーのトーシェント関数を使えば「何乗すれば逆数になるか？」が分かる（なお、Pythonならpow(x,-1,mod)でOK）ので、計算可能。それぞれ計算し、中国剰余定理によって復元できる。
時刻: 0 件のコメント:
ラベル: ,

2022年11月2日水曜日

AtCoder Beginner Contest 275

　Fまで六完だが遅解きだった。

コンテスト後のツイート

G - Infinite Knapsack

　解説放送を見てAC。

　凸包を使うのが久しぶりだったので、自分の昔の提出に取りにいった。（ライブラリに入れます）
　ただ、凸包の線分の両方の頂点が、y=xに対して片側にある場合に計算してはいけないことに気付かず、誤差のせいか？　などと思ってWAを重ねてしまった。何を求めているかちゃんと考えないと。
時刻: 0 件のコメント:
ラベル: ,

2022年11月1日火曜日

Codeforces Round #819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022

　Cまで三完。約20分遅れで書き終ったEはコンテスト後、ACしました。その後、剽窃が発覚しunratedに。

コンテストへのリンク
コンテスト後のツイート


 D. Edge Split

　解説AC。
　これを飛ばす判断は間違ってなかったと思う。

　赤、青それぞれが連結な木になるよう色を塗れば良い、と思い、それをどう実装すれば良いか分からなかった。
　が、実際は連結性はいらなかった！　赤、青それぞれが森になっていればOK。

　実装はDFS木の性質を使うと良い。
　DFSで全域木をとって、残り三辺がサイクルになると困るが、DFS木の後退辺が親子関係にあるので、サイクルの一辺の色を変え、代わりに根へ付け替えれば良い。
　（という説明は、tatyamさんのツイートそのままです。これを思いつかないと実装で迷走しそう）
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)