Eが解き終わらず終了したが、コンテスト後提出したらWA。その後、約一時間かかってようやくpretest全完。
ツイートに加えて書くことはなさそう。
Gは最初、フローに見えて悩んでいたのは良くなかったね……。正当性がやや不安だったけど、どうやら正しそうで良かった。
2021年6月11日金曜日
2021年6月8日火曜日
AtCoder Beginner Contest 204
Eまで五完。Fはキーワード的には分かっていたのだが……。
E - Rush Hour 2
ダイクストラ法。
$\sqrt{D}$よりtimeが小さいときは、$\sqrt{D}$を調査、そうでなければ普通にtimeのときにかかる時間を計算。
$\sqrt{D}$あたりが極値になりそうなことは、最初は微分しようとしたが面倒くさくなって、
$x+\frac{d}{x+1}=x+1+\frac{d}{x+2}$
を計算した。
これは、$x$が1ずれても同じ値になるところを調べているということ。こういう$x$で極値になるはずなので。
F - Hanjo 2
解説AC。
うーん、行に関する部分集合たちについてDPをして、行列累乗だろうとは思ったし、横2マス見れば現在の状況が扱えることもコンテスト中に考えたはずなのだけど。
しかし、解説をみても、「列iまでみて全ての行ではみだしている場合」と「列i+1までみてはみだしが一つもない場合」は同一のものなのに、DPするとき両方を状態として持たなくてはいけないことにピンと来なかったし、自分にはちょっと分かりにくいDPだったのかもしれない。
遷移の行列を作るところは再帰で書いたけど、これもどう書けば良いか結構迷ってしまった。
2021年6月7日月曜日
Codeforces Round #724 (Div. 2)
全完35位！ Div. 2全完は初めてなので嬉しいです！
こういう、ちょっとギャグっぽい問題が多い回だと、良い順位を取れることがあるみたい。
ツイートで書いた解法に加えて書くことないので、ツイートの補足的なものを少しだけ。
E. Omkar and Forest
問題を見て、最初は全然分からなくて、諦めようかな……と思い横になって直線状の図を考えていたら、「0でないマスの値は決定される」と気付きました。
F. Omkar and Akmar
nが6や7の場合まで図で描いていたら、ABABAB……と一周するしかないことから後手必勝と分かりました。
その後の計算も戸惑ったけれど、数字が書かれるマス二つの間の空のマスは一つなので、「数字が書かれる1マス」と「数字が書かれるマスと空のマスのペア」を考えれば二項係数が使えそう、ということから立式できました。
終了間際でギリギリだったけど間に合って良かった。
NOMURA プログラミングコンテスト 2021(AtCoder Regular Contest 121)
Cまで三完。Cで苦戦してしまったが、レートはそこまで落とさずに済んだ。
C - Odd Even Sort
三文字以下なら、交互に操作し続けることでソートになる、というのは気付かなければいけないけれども、後は大きい数字を右に移動させていくだけで良い。そうすると、自然に規定回数以下に収まる。
後は実装問題なので何を反省すべきかね……。
とりあえず、WAやTLEがでたときにすぐにcheckerを書いて（結局、何回かペナを出した後で書いた）いれば、ペナルティ量産は防げたと思う。
D - 1 or 2
解説AC。
ツイッターなどでヒントを見ていたのでどこまで自力かは分からないけど、常に二つ選ぶなら、ソートして大きい方と小さい方から取っていくのが最適、というのは気付いた。
あとは、一個だけで取るものをどう選ぶかだけど、ソートしたものの中である区間になっているはず。その区間全探索を普通にやると三乗だけど、何か差分計算とかで高速化するのかなぁ……とか考えながら解説を見たら、思った以上にシンプルでした。
なお、解法ツイートを見ると、（高速化は分からないけれど）正負などで場合分けして一個取る場所の範囲を絞れば通るみたいですね。
E - Directed Tree
解説AC。
……といっても、公式解説を読んだだけではなかなか理解できず苦労してしまった。
木の問題で、木DPをするのでは？（制約を見ると、二乗の木DPかも？） 使ってはいけない数字が指定されるので、包除原理を使うかも？ といったあたりは考えた。が、そこで詰まってしまった。
キーワードはこの問題と共通ですね。そして、今回の問題はこの問題よりDPを立式するのは簡単なはず。とはいえ、なかなか立式するのは難しい気がする。
結論からいうと、解説の通り、
・$DP[i][j]$を$i$を根とする部分木に$j$箇所条件に違反するように書き込む方法の個数
とするのだけれど、この「部分木」というのは、その部分木の祖先がどうなっているのか、とかとは全く関係ない、本当にただの部分木です。その部分木に関する入力が与えられたら、その答えを求めるものです。
……いや、素直に解説を読めばそう（だし、二乗の木DPを使う問題ではそういう風に置くものなのかも）なんですが、私は、祖先のノードが何個あるから禁止すべき個数は……などと考えてしまいました。
それだと遷移が上手くいかなくて、ただの部分木に関する問題のDPテーブルが求まっていたら遷移が上手くいく、というのは不思議です。
あと、この問題の難しさは、包除原理を使うなら、$DP[i][j]$の$j$は必要なさそうなのに、$j$を明示的にしなくてはいけない、という部分だと思います。最終的に、$j%2$によって足すが引くかを決めるので、$DP[i][2]$で良いのでは、と思ってしまいそう。
ただ、$DP[i][j]$の$j$があっても二乗に収まる、というのが二乗の木DPなので、二乗の木DPを使おうという気持ちで臨むとDPの立式もしやすいのかもしれない。
どうDPテーブルを置くかが難しい問題な気がしたけど、二乗の木DPに慣れていれば分かるのかも？ とも思えてきました。
練習すれば、DPの置き方も含めて典型と思えるようになるのかな……。
（FはACした後書くつもり。）
2021年6月5日土曜日
Educational Codeforces Round 110 (Rated for Div. 2)
数分遅刻してDまで四完。今回のえでゅふぉC～Eは教育的な出題だったと思う。Cは尺取り法の、Dはセグ木の、Eはダブリングの、本質的な理解を問うている感じがします。
普段のえでゅふぉは、educationalという名前の割に教育的とは思えない問題が多い気がするけど、今回は良かった。
C. Unstable String
尺取り法で良いのだが、左端を動かすときの条件がやや書きにくい。
dequeを使うと尺取り法を書きやすい、というのを目にしていたのを思い出し、この問題で試してみたのだけど、「左端の条件の書きにくさ」はこの方法では緩和されず、時間がかかってしまった。
でも、普通に（whileとかで）書くよりはちょっと楽だったかも？
D. Playoff Tournament
図の通り、セグメント木みたいなことをするのだけど、普段多くの人が書いているセグメント木とは添え字の順番が違うことに注意。
そこを補正するため、普段の順番と今回の順番で、添え字の対応表を作れば良い。
私は、対応表を作るときのfor文の範囲を間違えて、対応表に-1を残してしまったためTLEが出てしまった。原因特定に苦労した。
E. Gold Transfer
コンテスト中は、$C_i>C_{p_i}$を見落としていたのでどうしようもなかったが、この条件をちゃんと理解すれば、一番祖先から貪欲にとっていけば良い。
なら、ダブリングするのかな、というのは思いつく。
ということは、金がなくなっていない祖先のノードを見つけて、そこから自分の方へ降りていけば良いのだけど、降りるときどうすれば良いの？ というところで詰まった。
LayCurseさんのツイートで理解。
落ち着いて計算量解析をすれば分かりますね。
なお、実装したけどPyPyだとTLEだったのでKotlinでACしました。ただ、今見ると何人かPyPyで通していますね。
AtCoder Regular Contest 119
ABCEの四完。現在の主戦場であるはずのARCでレートを上げられて嬉しかった。
D - Grid Repainting 3
解説AC。惜しいところまでは自力で考えられたのだけど結局解説を見ないとACできなかったので、コンテスト中に飛ばしたのは正解でした。
自分で考えたのは、
・Rのマスを頂点とし、縦横で繋がっている頂点を辺とするグラフを考える。
・辺が一本だけ出ている頂点があれば、X方向かY方向かどちらに消せばいいか決定できる。
・ということは、最小全域木を取れば良さそう。
・全域木を取って、辺が一本だけ出ている頂点についてはX方向かY方向かで色を塗っていく。そして、最後に残った頂点たちは、「全てX方向に塗る」か「全てY方向に塗る」が最善。
という感じ。この考察自体はあっています。
ただ、このグラフで全域木を取るのが容易ではない。上手い実装が思いつかなかった。
なので、自分にとっては、公式解説の「考察１」が胆でした。
(x, y)をグラフの頂点とみなすのではなく、各行や各列を頂点とみなし、頂点「x行」と頂点「y列」を結ぶ辺(x, y)と考える。
そうしても、全域木を取って云々という他のステップについては同様にできます。
この考察自体は珍しいものではないけれど、一旦、別のグラフで考察した後、グラフ自体の変更を考える、というのは思いつきにくい気がします。
E - Pancakes
ツイートした通り、Codeforcesで出た問題の類題でした。「区間の交わり方は3通り」は頭に叩き込んでおこう。
（FはACしたら更新する予定）
2021年6月3日木曜日
Codingame「Spring Challenge 2021」
Codingame「Spring Challenge 2021」に参加しました。前回はGold Leagueまで行けたので、今回はLegend League入りを目標にしました。
結果は、195位/ 6867人で、なんとかLegend Leagueに入れました！
目標達成できたので嬉しいのですが、今回はLegendの人数が多かったこともあり、やや微妙な気持ちもあります。
ルールはいなにわさんの日本語訳が分かりやすいです。（コンテスト中も参考にしました）
また、色々な方の参加記がshirakiaさんによってまとめられています。非常にありがたい。
（ツイートした通りですが）私がやったことは、適当に評価値を作って、「Possible moveの中で評価値が一番高いのを選ぶ」というだけです。
本当は、
・評価値を作る→探索する（たとえば二手後の評価値を調べる、など）→やっぱり時間制限が厳しいから他の言語に書き換え
のようにする予定だったのが、最初のステップで終わってしまった感じです。それはちょっと悲しいですね。
ただ、元々今回は、「評価値を頑張りたい」という気持ちが強かったです。
前回のCodingameに参加した経験で、終了後に他の方の参加記を読むと、探索以前に、ゲームへの考察が不足しており、評価関数にまだまだ改善すべき点があったことが分かりました。今回はその点では後悔したくない、と思っていました。
それに、良い評価関数を作ることは、後で探索を行う場合でも枝狩りに役立ったり、無駄にはならないはず、と。
その点に関して言うと、他の方の参加記を読んでもそこまで考察不足だった、と感じる点はなかったので良かった。
あと、koyumeishiさんの記事を参考にローカルでの実行環境を作れたのは良かったです。前回はローカルでの実行環境を作れなかったので……。100回とか300回実行して、勝率が高い方を選ぶ、というのができ、このおかげで評価関数を調整できました。
この、ローカルで実行しながら色々パラメーターを調整している間に暇な時間があったんですよね。その間に探索を実装したら良かったのですが……。サボってしまった。
次回は考察した上で、探索も実装したいですね！（NNを勉強するのは無理そうですが、普通の探索は）
評価値について
ツイートしたことをもう少し詳しく書きます。
・最初の五日は（どこにseedするか以外）他の人の真似をしています。
・250*score、100*sun
最終的に1 point = 3 sunになるので3:1を目安にしました。ただ、sunが多いことが（特に序盤は）重要なのでこの値に。
なお、score pointが重要になるのは後半なので、9日目までは0、10～19日目は上記の値、20日目以降はこの二倍にしています。
・木のsize別値を[5,115,245,420]として、(23-day)*本数*size別の値
後者の式は、日が経つほどにscore（COMPLETE）の重要性が増すことからこうしました（日に関する一次関数で良いのかには議論があるだろうけど）。
その後、ローカル対戦により調整したのが、この木の評価値です。たくさん自己対戦を行い、一番勝率が高そうなものを選んだというだけで、あまり根拠はありません。
・翌日～六日後に影がかかってsunがもらえない場合に-(7-day)*10*size
六日後まで見て、（現状のままだと）陰に入ってsun pointが得られない場合にマイナスポイントをしました。
・自分の木同士が長さ3の線分範囲にある場合10*そういう木の本数分マイナス
上位陣の対戦を見て、桂馬に木を配置しているのを見て、評価値に組み込みました。自分の木同士で陰になるのは避けた方が良いので。
・Richnessを補正（+Richness*1）
木を植える場所はRichnessが高いところになるようにしました。ただ、陰に入るか、という方が重要なようだったので、気持ち程度の補正です。
登録:
投稿 (Atom)