2024年3月29日金曜日

第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023）

　pretest29位。最終27位。


　ツイートをまとめておきます。

第10回 Asprova プログラミングコンテスト（AtCoder Heuristic Contest 023） pretestは29位でした。今のところAHCでの最高順位!　システムテストで下がらないことを祈る！

・序盤はあまりやる気が起きませんでした。今週はWTFもあるのでほどほどに……という気持ちでやっていました。

・入口を根とするBFS木を作って、葉から埋める方針を考えていました。葉の方から順に埋めると、その先祖のノードでは何を置いて良いかを判定できるので。Sが小さく、D-Sが大きいものから埋める貪欲で30～31点

・それを、なんとなくDが大きい順にソートし直したら点数が31から39まで跳ね上がってびっくり。突然やる気が湧きました。これを山登りとかで改善すれば40はいきそう、と。

・WTF open一日目で青に落ちて二日目はAHCにあてることを決意。山登りするための高速化と、遷移を書いていました。

・遷移としては、「既においた作物を別の似た作物へ変える」「BFS木の親を別のものへ付け替える」の二つを実装。先祖のノードで使うことにしていた作物は一旦全部削除しなくてはいけない……といったあたりが分からず実装に苦戦。実装できたら40に乗りました。

・実行時間が伸びればそれなりに点数が伸びそう、と最終日にRUSTへ書き換え。Chat-GPTや自分の以前のRUSTの提出を見ながら実装して41まで伸びました。

・さらに、PyPyで試したときはあまり効果がなさそうだったけどRUSTなら、と焼きなましを試してみたら416まで伸びました。今まで、山登り→焼きなましではっきり点数が伸びた経験がなかったのでびっくり。嬉しかった！

・あとは温度調整などをして終了。
時刻: 0 件のコメント:
ラベル:

2024年3月25日月曜日

AtCoder Regular Contest 175

　二完でまた青に落ちてしまった。

コンテスト後のツイート

C - Jumping Through Intervals

　多少解法ツイートを参考したけど、概ね自力でAC。コンテスト後、一時間以上かかってしまった。難しい。

　LR[i]とLR[i+1]の位置関係を考える。x, y=LR[i],  z, w=LR[i+1]とし、y<wのとき、LR[i+1][1]=max(y, z)として良い。w>yのとき、LR[i][1]=max(w, x)として良い。まずこのように更新しておく。

　この更新で値が決まる箇所がある。i, j(i<j)の値が決まり、その間が決まっていなかったとする。このとき、ANS[i]<ANS[j]ならi+1の値を、ANS[j]<ANS[i]ならj-1の値をLRの値との大小を比較することで決めることができる。

　区間の片方しか決まっていない場合も似たようにやる。一つの値も決まらない場合はずっとある値を取り続けられるということなので、そのような最小値を探す。

D - LIS on Tree 2

　解説AC。

　難しかった。
　f(P)の最大値は分かるが、そこまでの値全てを取るのか？　またどうやって構成すれば良いかが難しい。根から構成するのか、子から構成するのか、（Pについて）大きい数字から考えるのか、小さい数字から考えるのか、があり悩ましい。

　結局、根から考え、その頂点により、「自分を含む部分木の大きさ」の分だけ増やせる、と考えるのが正しかった。ただ、この見方もなかなか理解できなかった。

　コンテスト中にこの問題を解けていた気はあまりしないので、Cに行ったのは正しかったか。
時刻: 0 件のコメント:
ラベル:

2024年3月24日日曜日

Codeforces Round 936 (Div. 2)

　Cまで三完。


D. Birthday Gift

　解説AC。

　全体のxorをXORとすると、区間を分けてxorを取ったときの値もXOR以上になるということに気付かなくてはいけなかった。

　あとは、上の桁から、XORのi bit目が0のときに、0のままにしなくてはいけないか、1にしても良いのかを考えていく。
　0にするときは、A_l^...^A_rのi bit目が0になったとき、その部分をA_l^...^A_rに置き換える……という貪欲を行って良いと気付くと実装しやすい。

　分かってしまえば難しくはないのだが……。

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

2024年3月21日木曜日

Codeforces Round 935 (Div. 3)

　Eまで五完。


F. Kirill and Mushrooms

　コンテスト中は取得するマッシュルームのindexが連続してなきゃダメと誤読して解法が分からず。コンテスト後、さらにPの意味も誤読し（P_iが小さい順番に0になると思った）ていたことが発覚。
　正しく読めた後も無駄にifをwhileと書いていた場所が悪さしてWAを重ねてしまった。

　解法は、(i,A[P[i]])を第二要素が大きい順に見ていき、heapqに突っ込み、今考えている長さよりiが小さければその要素を捨てていく……といった感じ。


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

yukicoder contest 422 (第１回 競技プログラミング講習会作問企画コンテスト)

　Dまで四完。


No.2683 Two Sheets

　自力AC。

　縦と横を独立に考えられると思ったが、コンテスト中は、そのまま（縦の期待値）*（横の期待値）になる気がし、答えが合わず混乱。
　落ち着いて見ると、重なっている部分が長方形になるので、そこを縦*横で計算できると気付いた。

　これがすんなり解けないのは、やっぱり確率/期待値が苦手なのかなぁ。

No.2684 折々の色

　自力AC。

　難しくはないけど、同じカードを二枚重ねる場合などに注意が必要ですね。

No.2685 Cell Proliferation (Easy)

　自力AC。
　これは簡単でした。シンプルな二乗のDPでOK。

No.2686 商品券の使い道

　解説AC。

　高速ゼータ変換について何も覚えていなかった。
　部分集合に関してのDPを考えれば結構自然な考え方に見えた。
　高速ゼータ変換は（他次元）立方体における累積和を考えている、というのも覚えておきたい。それが身に着いていれば、高速ゼータ変換を忘れたとしても、どんなDPを考えれば良いか？　と思考すれば思いつけるはず。
時刻: 0 件のコメント:
ラベル: ,

2024年3月20日水曜日

モノグサプログラミングコンテスト2024（AtCoder Beginner Contest 345）

　Eが解けずABCDFの五完。

コンテスト後のツイート


E - Colorful Subsequence

　解法ツイートを見てAC。

　色の異なる価値の高い二つを持つ（TOP2を持つ）のは典型だし、他の問題では自力で思いついたこともあった気がするのに、この問題では浮かばなかった。
　DPの枠組みの中でやらなくてはいけないから気付きにくいのかな……。

　Fより難しい気がしたけど、解法を見ればEも典型で、Fより前に置いた気持ちも分かります。

　なお、雑にsortを使って書いたらPyPyだとTLE、書き直したら微妙に間違えてWAをなくすのに苦労した。計算時間ギリギリそうなんだから、sortなんて使ったらそりゃダメですね。




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

2024年3月18日月曜日

Codeforces Round 934 (Div. 1)

　問題は解いていたのだけど、提出せず。
　コンテスト後提出したら、A:WA、B:AC、D1:TLE（ちょっと修正してAC）でした。

コンテスト後のツイート


A. MEX Game 1

　自力AC。落ち着いたらすぐACできたが、本番提出してWAが出た後だったらどうだったか。

　C=Counter(A)として、
・C[i]=1となる最も小さいiについて、C[i]=2とする
・C[i]<=1となる一番小さいiが答え。

　相手がスタートだとすると、相手が取ったものを自分が取る真似っこ戦略が使える。
　最初に自分が一手おけるので、C[i]=1のものを、真似っこできるように+1すれば良い。

　



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

AtCoder Regular Contest 174

　ABDの三完でレートを下げる。
　Cは絶対解けなくてはいけない問題だと思ったが、そう思ったのがプレッシャーになってしまったかもしれない。典型ではあるけど、苦手な問題ではあったよね。

コンテスト後のツイート

C - Catastrophic Roulette

　自力AC。

　コンテスト中は、各段階での先攻・後攻の確率（これは求まっていた）に加え、それまでの罰金が遷移に関係すると思い混乱していた。
　確率さえ求まれば罰金を足していけば良いと気付きAC。

　ただ、そう気付き、それなら実装も簡単では？　と実装を始めてからも30分くらいかかってしまった。

E - Existence Counting

　自力AC。

　ある桁がxの数列は何個あるか？　その中で、各数字は何回ずつ現れるかを考えて足し合わせていく。

　考察に詰まるところはなく、実装も、やや時間はかかったものの困るところはなかった。Cを捨ててこっちに集中していれば解けた可能性はそこそこありそう。とはいえ、Cも通せなきゃいけない問題に見えたから、Cを捨てる判断はできなかった。
時刻: 0 件のコメント:
ラベル:

2024年3月16日土曜日

yukicoder contest 421 (NUPC2023)

　AB二完でした。


No.2673 A present from B

　後ろから見ると良いというヒントを見てAC。

　次のように、答えを徐々に更新していく。

・最終手まで見て、そこから配列に何かを付け足すと考えると、最終手の後できている配列のindexにより答えを更新できる。
・その一手前を見る。そのとき、A[x]とA[y]がd個離れているとすると、そこにd個挿入してA[y]をA[x]の位置へ持っていくことができる。つまり、ANS[A[y]]をd+ANS[A[x]]で更新できる。

　以下これを繰り返すと、計算回数N*N*Mになる。解説を見ると、もっと速く解けるみたい……と思って考え直したところ、ここに書いた方法でも累積minを取れば計算量N*Mになりそうですね。

No.2674 k-Walk on Bipartite

　おおまかな方針はあっていたけどWAを取ることができなかった。テストケースを見ながらデバッグしてAC。

　難しい問題ではないけれどコーナーケースを探すのが難しい。コンテスト中にACした人はえらい。

No.2677 Minmax Independent Set

　全方位木DPというタグを見てAC。

　自分の全方位木DPのライブラリをほぼそのまま使えたにもかかわらず実装で混乱した。自分の全方位木DPライブラリが良くないのではないかという気持ちに。

　辺属性のDPと考えているので、UP[x]とDOWN[x]を同じ辺に関する値にしたくて、

・UP[x]:xをROOTとする部分木（xを含み、xおよびxより葉に近い頂点たち）に関する値
・DOWN[x]はParent[x]をROOTとする部分木（xを含まない。xより根を含まない頂点たち）に関する値。

　としていたのだけど、分かりにくくない？

No.2678 Minmax Independent Set (Hack)

　自力AC。これは簡単だった。

　横に1001個頂点をつなげておき、そのうち一個は、一個の頂点がx個ついているようにする。他の1000頂点は、二個連なった頂点がx+2個ついているようにする。(xは適当な数。4とか)

　すると、最適なのは、最初の一個の頂点を選ぶことだが、問題文で与えられた解法では他の次数の高い1000個の頂点の中から選んでしまう。
時刻: 0 件のコメント:
ラベル: ,

2024年3月13日水曜日

yukicoder contest 415

　Dまで。

コンテスト後のツイート


 No.2611 Count 01

　解説AC。

　セグ木を使うとは思ったが何を乗せれば良いか全く分からず解説を見た。
　こういうのを乗せれば解けるのかと結構驚いたのだが、解説を見ながら実装しても30分以上はかかってしまった。速く解けている人はどうやってるのかな。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 933 (Div. 3)

　全完。 あまり速くはなかったけど全完できて良かった。システムテストでG落ちている人が結構いるけど、なんでだろう？

コンテスト後のツイート


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

2024年3月12日火曜日

AtCoder Regular Contest 173

　Cまで三完。レートが上がって嬉しいけど、喜んでいい程の成績でもない……と思っていたけど、ARC/AGCで2200以上のパフォを出したのは去年一回だけだったらしい。なら、喜んでいいかも。

コンテスト後のツイート

D - Bracket Walk

　解説・解説放送を見てAC。
　コンテスト中は迷走していたが、正しい解法は非常にシンプルですね。

　ただ、負閉路判定にベルマンフォード法が使えることをちゃんと覚えていなかった。ベルマンフォード法自体のやり方自体は覚えていたけども……。負の辺があるときの最短距離ではベルマンフォード法を使うというのは覚えていたけれど、負閉路判定にも使えると覚えておきたい。

E - Rearrange and Adjacent XOR

　解説・解説放送を見てAC。

　最後に残る値を実験で求めるパートも難しいし、その後の実装も難しい。
　熨斗袋さんのツイートのように、「偶数個のxorで表せる」というのを、各A[i]に61bit目が立っていると考え、そのbitが0になるような答えを考えるというのが分かりやすいですね。



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

2024年3月11日月曜日

yukicoder contest 420

　Cまで三完。


 No.2666 Decreasing Modulo Nim

　解説AC。

　実験コードを書いたあと何も進まなかったけれど、「Aliceが最初にmの倍数を選択したらどうなるか？」と考えて、各A[i]をA[i]%mにしたものへ帰着できることは思いついて良かった。

　それ以降は難しいが、mで割った余りに帰着した後なら実験でどうにかなったかもしれない。



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

トヨタ自動車プログラミングコンテスト2024#3（AtCoder Beginner Contest 344）

　Eまで五完。

コンテスト後のツイート

F - Earn to Advance

　解法ツイートを見たが、大体コンテスト中に考えていた内容だった。

　所持金を増やす量を今まで通ったマスのmaxとして良いことには気付くのが重要。この値を使ってDPしようとも思ったのだが、dictでDPするのがちょっと不安で、座標圧縮しなくてはいけないのか？　などと考えてDPを避けてしまった。

　さらに、DP[それまでのmax]に対する値として、行動回数と所持金を両方持たなくてはいけないのか？　一次元化できるか？　と混乱してしまった。

　公式解説を見ると、(行動回数, 所持金)が最も良い値を持てば良いらしいけど、気付きにくいね。行動回数は多いけどお金がたくさん……みたいなことは考えなくて良いことの証明は熨斗袋さんのツイートが分かりやすいと思います。




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

2024年3月10日日曜日

Codeforces Round 931 (Div. 2)

　D2まで。Div.2で二桁順位を取ったのは久しぶり。2100には届かなかったがレートも回復して良かった。

コンテスト後のツイート

E. Weird LCM Operations

　解説AC。

　とりあえず、(x,y,z)という三つの数が互いに素なとき、この三つの数について処理を行うと、この三つの数について条件を満たすことに気付かなくてはいけなかった。
　さらに、(x,x+1,x+2)でxが奇数のとき、この三つの数は互いに素なことを利用したい。

　そう考えると、解説のような12で割った余りについて分類する方針にたどりつけそう。

　基本的には、色々実験して解法を見つけていくしかなさそうなので、コンテスト中に解き切るのは困難だったか。
時刻: 0 件のコメント:
ラベル:

2024年3月7日木曜日

Codeforces Round 932 (Div. 2)

　Dまで。
　このコンテストで久しぶりに紫から薄橙へ戻れた。紫に落ちていたときは非常に辛かった。戻れて良かった。

コンテスト後のツイート

E. Distance Learning Courses in MAC

　解法ツイートは見たけど、コンテスト中に考えていたことで合っていたのでほぼ自力AC。

　上位bitから見ていく。
　たとえば、あるクエリで、3つ目のbitについて考えているとき、[6,10]と、[9,11]のどちらから3つ目のbitを取るかというと、後者から取るべきである。そうすると、前者から7が取れるため、以下のbitは全て立てられることが分かる。

　こういう風に考えると、[6,10]から3つ目のbitが立っているものを選択するときは、他に3つ目のbitが立っている区間がないときである。そして、そのときは（3つ目のbitが立っている）[8,10]だけ考えれば良いことが分かる。
　なので、他に３つ目のbitが立っているときは処理を終わらせることにすれば、次、２つ目のbitを考えるときは、[6,10]を[8,10]に更新して考えて良い。

　そうやって更新していくと、ここでこの区間からこのbitを選択するのか？　ということを考えずに済む。

　というわけで、（こういう更新をした上で）

・ある区間にそのbitが立っているものが何個あるか？
・ある区間にそこで更新を終えてよいやつ（さっきの「7」みたいなものが含まれるやつ）があるか？

　が分かれば良い。

　これはセグ木を二つ使えばできる……と思って実装していたが、PyPyではTLEやMLEが取れなかった。
　落ち着いて考えると、両方累積和で処理できますね。セグ木なしで実装してAC。

　アイディアは間違っていなかったけど、コンテスト中はセグ木実装しか考えていなかったので、コンテスト中ACするのは困難でした。
　







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

2024年3月5日火曜日

yukicoder contest 419

　A一完で終了。Codeforcesと被っていて、現在、Div.2もRatedなのでそっちに集中したかったという事情もあるが、Bは結構考えたけど思いついていなかった。


No.2656 XOR Slimes

　隣接同士の合体しか考えなくて良いとどこかで見てAC。

　言われれば証明するのは難しくなかったけど、全く思いついていなかった。二乗の制約から思いつくこともできそうですね。

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

2024年3月3日日曜日

AtCoder Beginner Contest 343

　DまでとFの五完。Eが解けなかった。

コンテスト後のツイート

E - 7x7x7

　解法ツイートを見て理解、AC。

　a1, a2, a3を(0, 0, 0)に固定し、b1～c3を０～20あたりで全探索したがダメ。E869120さんのこのツイートを見て、負の数も考えなくてはいけなかったと知った。
　負の数も探索したらAC。

　いや、難しいね。
　正の範囲だけ探索して一般性を失わないのかと思ってしまった。立体感覚がないとこれに気付くのは難しそう。

G - Compress Strings 

　解説AC。

　少し解説を見てしまったけど、自力で解けなければいけない問題でした。ただ、解こうとしたら、「S[i]とS[j]で何個重複させられるか？」を前計算するパートで文字列アルゴリズムが必要がない気がしたりして混乱……。
　また、自明な枝狩りを入れないとTLEになってしまい、結構困りました。



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

2024年3月1日金曜日

Codeforces Round 930 (Div. 1)

　A一完。Bに非常に苦労し、コンテスト後にACコードを書き終った。でも、時間ギリギリで通していたとしても多分レートはマイナスですね。

コンテスト後のツイート

A. Bitwise Operation Wizard

　「? i i j j」
　とすることで、P[i]とP[j]の比較ができることが重要。

・まず、最大値を探す。
・次に、最大値|P[i]が最大になるiを列挙する
・それらの中で最小のiを探す

　として解いた。

B. Pinball

　実験すると、
　>で始まったのなら、次に反射するのは、それより右にある<、その次に反射するのは、一番はじめの>より左にある>……のようになる。

　これで何個の文字とぶつかるかは、累積和と差分計算を頑張ればできる。

　しかし、残り50分あたりで頑張ればできることに気付いたのに解き終わらなかった。コンテスト後15分くらいでようやくsampleが合い、それでACでした。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)