2022年10月10日月曜日

AtCoder Beginner Contest 272

　Fが解けず。

コンテスト後のツイート

F - Two Strings

　解説AC。

　コンテスト中、Suffix arrayを見てこれを使うのでは？　と思い、S、TをSuffix arrayを作るようにソートすれば、尺取りで解けそうと考えた。が、同じ文字が続く場合や、SとT（を回転させたもの）が一致するときの処理が上手くできなかった。

　Suffix arrayをもっと上手く使えないか？　と考えるべきだった。

　SやTを回転させたもの全てを調べたいので、S+S、T+TにSuffix arrayを使う。
　さらに、SとTを直接比較したいので、S+S+T+TにSuffix arrayを使う。
　そして、同じ文字が続くときの処理のため、S+S+"a"*N+T+T+"z"*NにSuffix arrayを使うと答えが得られる。

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

2022年10月9日日曜日

AtCoder Regular Contest 150

　Cまで三完。

コンテスト後のツイート

D - Removing Gacha

　解説AC。

　深さの逆数は考えたのに、(深さの逆数+1)を今までの答えに掛けるのかな？　とか考えて分からなくなってしまった。深さしか答えに寄与しないというのは、まあ直感に違わないのに、解けなかったのは悔しい。



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

2022年10月8日土曜日

Dytechlab Cup 2022

　Dまで四完。

コンテスト後のツイート

E. Ela Goes Hiking

　解説AC。

　左から１～x番目の蟻のうちx番目の蟻が勝つ確率を考えるのがコツ。この考え方は、漸化式を立てよう、という気持ちでも思いつくかもしれない。
　で、この確率は、x番目（が左端でないなら）が左を向いており、そのすぐ左に、右を向いた蟻が連続していて、自分と合わせて合計でx/2匹以上の蟻に合成されるような場合となる。

　さらに、x番目の蟻が全体で勝利する確率は、

・1～x番目で勝利する
・x+1番目以降で勝利する蟻がいない

　こと。

　ただし、x番目の蟻が1～x番目の中で勝ち残る、という条件の元では、x番目の蟻は左を向いているので、[x+1,2*x]番目の蟻が勝つことはない。ので、2*x+1番目以降の蟻が勝利しない確率を掛ければ答えが求まる。

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

2022年10月4日火曜日

yukicoder contest 313

 　Eまで五完でした。Fも解けなきゃいけなそう。方針は合ってそうだが……。


No.1677 mæx

　（今更だが）自力AC。

　構文解析＋DP（メモ化再帰）。
　昔書いたDPのコードがあったので、それを利用してACした。
　各"("に対応する","や")"がどこかを前計算しておけば、それを利用してDPできますね。

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

2022年10月2日日曜日

yukicoder contest 362

　Cまで三完。

　Dまでは、計算量云々するパズル的な問題ではなく、数学は知っているけどプログラムはしたことない人にも解いてもらえるような教育的な問題が出題されていました。
　Eはパズルっぽいですが、計算量ではなく、論理式に関するものですね。


No.2089 置換の符号

　置換「3 1 2」を見て、どういう定義だっけ？　と思い、やめてしまった。（いくらAHCで疲れていたとはいえ、ひどい）

　1 2 3が3 1 2へ移るような置換という意味ですね。
　置換を互換の積に直せば良いので、実装してAC。転倒数の偶奇と一致するのは知りませんでしたが、言われてみればなるほど。

　いや、それにしても置換が何なのか分からなくなったのはなぜなんだろう？　(3,1,2)みたいに書いてあれば分かったのか？

No.2090 否定論理積と充足可能性

　自力AC。

　手元で計算したら、

・$((\neg a \vee \neg b ) \wedge c) \vee ((\neg d \vee \neg e ) \wedge f) $

　のようになったので、左辺が$\bot $になるためには、$a=b=c$が必要（右辺も同様）と分かった。

　つい変形してしまったけど、プログラムで書くなら全部の真偽を試す方が早いですね。


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

estie プログラミングコンテスト2022（AtCoder Heuristic Contest 014）

　プレテスト114位、システムテスト126位でした。

コンテスト後のツイート



　この感想ツイートが長くなったので、こっちにまとめておきます。 


　序盤は、「オセロっぽいな」と思い、オセロの評価値として「自分が置ける位置の個数」が有名なことにならい、「次に作れる長方形の個数」を評価値にしようとしました。が、これで長時間回してもあまり伸びない。なので、それに代えて、

・長方形の周囲の長さ

・次におく頂点のweight

・長方形を作ったとき、新たに作れるような長方形の個数

　あたりを評価値に。


　最終的には、

・次におく頂点のweight/（長方形の周囲の長さ^(1～4のランダムな数)）

　にしました。（それをheapqに突っ込み、上位三つのうちからランダムに採用）

　解説放送を見ると、weightは取り入れなくて良かったらしいので、それを消して回して実行してみたけど、うちの環境だと点数は伸びません……。（PyPyだし、実行回数が足りないのか？　と思い、10倍の時間回したので比較したら多少は伸びたが、50ケースで+100万もなさそう）

　解説放送で言っていた「枠」という概念にはたどり着けなかったけど、まあそれっぽいことは考えていたとは思う。

　「枠」は思いつけたとしても実装に反映できたか自信ないし、評価値については及第点かなぁ。


　山登り・焼き鈍しについては、

・部分的に残して作り直す

　としていました。答えの列のある長方形を見て、それを作るのに必要なものたちだけでやり直す、という山登りです。


・最終スコアが大きい答えの、ランダムな長方形一つ

　を残すのに加えて、weightの大きい頂点までいったものを採用したいと思っていたので、

・（スコアは悪くても）weightの大きい頂点（長方形）

　を残してやり直すことも実装しました。

　解説放送では、部分的に壊してやり直すと言っていて、そっちかー、という感じに。

その方が自然な山登りだけど、大きいweightのものを残したいと思ったので、考えなかった。

　どのくらい差があるのかは分からないけど、weightが大きい頂点を残したい、と思ったのは筋が悪かったのかな……。


　感想書いたけど、何を反省すべきかよく分からない！

　高速な言語（C++かRustで書くのは考えた）で書いていれば気付けたことはあったかもしれないけど、気軽に色々試すなら慣れているPythonの方が良い、と思ってPythonで書いているので。

　最後、C++に書き換えようと思ったとき、書き換え時間の見積もりがまずくて終わらなかったのは良くないけど、そんなことを反省しても、という気がするので。

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

2022年9月26日月曜日

yukicoder contest 361

　B一完。


No.2078 魔抜けなパープル

　解説AC。

　魔法を使う回数で全探索というのを本当に思いつけなかった。kの魔法とk+1の魔法を使うとき～とかは考えたのに……。
　

No.2080 Simple Nim Query

　一番右端の1個じゃないindexを調べればいいよね？　と出したけどWA。
　結局、解法はあってて、全部1のときの答えを逆にしていたのでした。一番最初に書いたところなので、そこが間違っているとは思わなかった……。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)