2023年2月20日月曜日

Toyota Programming Contest 2023 Spring Qual B（AtCoder Beginner Contest 290）

　Eまで五完。予選Aで通過していたから良かったけど、予選Aで通過していなかったら、予選Bでは多分通過していなかった。

コンテスト後のツイート

F - Maximum Diameter

　解説放送を見てAC。

　解説を聞けばたいして難しくないように感じるが、本番では何も思いつかなかった。

G - Edge Elimination

　貪欲で解けるという解法ツイートを見てAC。

　コンテスト中は、「できるだけ小さい（葉に近い）部分木」を取った後、貪欲に頂点を削除していくコードを書いたがWA。
　そうではなく、X個以上の頂点を含む部分木に全てに対して、貪欲に頂点を削除していけば良かった。

　WAが出たとき、最初の方法でダメな例は思いついたが、全ての大きさの木を試すという方法を思いつかなかったのは反省。
時刻: 0 件のコメント:
ラベル:

2023年2月18日土曜日

Educational Codeforces Round 143 (Rated for Div. 2)

　Dまで四完。コンテスト終了後にEを思い付いた。

コンテスト後のツイート


F. Blocking Chips

　解法ツイートを見てAC。

　答え二分探索。木の深さが大きい頂点から貪欲に採用していくと考えて判定を行う。

　ただ、この判定の際に、chipと繋がっているか/いないかを考えて木DPしなくてはいけない。おおまかにどう書けば良いかは分かるのだが、実装は非常に大変。デバッグの仕方が分からず、WAが出たtestcaseを見て（提出して出力させて）デバッグしてしまった。

　それでも二時間以上かかっていて、どうしようもない……。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 377

　のんびりやって4完でした。


No.2220 Range Insert & Point Mex

　解説AC。

　イベントソート（平面走査）して重複度を管理すれば解ける。言われてみれば簡単（だし、似た問題を解いたことあったはず……）なのに解けなかったのは反省。

No.2221 Set X

　解説AC。

　各Xに対して二分探索を使って計算できることに気付き、解けたと思ったのだが、A[i]の範囲が10^9以下なので、さらに枝狩りをしなくてはいけなかった。
　調和級数のオーダーになるはず、と思って書き始めたのに、実際はなっていなかったのは良くない。落ち着いて計算量解析をしていたら解説を見ずに解けただろうに。
時刻: 0 件のコメント:
ラベル:

2023年2月13日月曜日

AtCoder Grand Contest 061

　A一完で青色に落ちました。時間ギリギリでAを解けたのは嬉しかったけど……。

コンテスト後のツイート


A - Long Shuffle

　考察過程を書いておきます。

・実験する。N<30くらいについて、手順が終わった後Aがどうなるかを見るが、何も分からない。

・さらに、どんな交換が行われているかも出力してみる。すると、部分部分が打ち消し合いそうだと分かる。

・打ち消し合っているところを消去するコードを書く。すると、交換が各index iについての交換が高々一回だということや、偶数のときは偶数番目しか交換されないこと、2ベキ+2のNについては、最初と最後の二回の交換で表せることに気付く。

・（xをxとx+1番目の交換とすると、たとえば「1 3 1 3」という交換なら打ち消し合う、と思っていたが、間違いなのでは？　という疑問が生じる。最初に出力したAの配列と照らし合わせたら、間違いではありませんでした）

・偶数の場合を考える。交換されるindexを書くと、
-N=10：0 8
-N=12：0 8 2 10
-N=14：0 8 4 12
-N=16：0 8 4 12 2 10 6 14
-N=18：0 16

　のようになっている。
　よく考えると、これは全て偶数なので、ソートして良い。

　そして、10<=N<18ならば、k=8として、(N-2-k) & y != 0 or y=0となるようなyとy+kで交換されるのでは？　と予想。
　上の例だと、

-N=10のときk=0：0, 8
-N=12のときk=2：0, 2, 8, 10
-N=14のときk=4：0, 4, 8, 12
-N=16のときk=6：0, 2, 4, 6, 8, 10, 12, 14

　となりOK。

・Nが奇数の場合は、N-1のときの交換の後で、「N-1の交換場所たちに+1した場所」で交換されると気付く。
→これで解けた！　と思うがWA。

・間違っていたところ一つ目。y<=x-kという条件が必要だった
→まだWA

・二つ目。(N-2-k) & y != 0ではなく、(N-2-k) & y == yが条件だった。これはN=28で実験して気付いた。
→やっとAC

B - Summation By Construction

　解説放送を見てAC。

　この問題はコンテスト中読んでいないので何ともいえない。思いつけるかどうかなので、コンテスト中この問題にかけて勝つ可能性もあったとは思うけど、そういう賭けに勝ったことってあまりないからねぇ……。Aが速く解けていたらそういう賭けをしても良かっただろうけど。
時刻: 0 件のコメント:
ラベル:

2023年2月12日日曜日

Codeforces Round #849 (Div. 4)

　全完と思ったらG2をHackされてしまった。

コンテスト後のツイート

G2. Teleporters (Hard Version)

　解説AC。

　ツイートで書いたのは本質的に間違っていた。（大枠はあっているので、このツイートの解法だけ読むと正しいようにも見えるが、正しい解法を理解はしていなかった）

　ツイートの通り、

・0もしくはn+1から行ってテレポートするまでのコストを前計算し、小さい順に取っていく

　として、0から行ったものが一つでもあればOK。問題は全てn+1から行っていた場合。

　一回だけ0から行き、他はn+1から行くことになるので、n+1だけから行ったものだけをソートし（Bとする）、累積和を取っておく。その上で、

・0から行ってi番目のものを取ったとする。すると、残りは、c-(A[i]+i+1)。これを累積和に対して二分探索し、そのindexをxとする。xより前にBにA[i]+(n-i)があるか調べ、あればx-1が答えの候補。なければ、xが答えの候補。

・さらに、xの前にA[i]+n-iがある場合は、c-(A[i]+i+1)+(A[i]+n-i)まで使えるので、これを累積和に対して二分探索する。似たような場合分けして、答えの候補が得られる。

　という感じで解ける。
　後半の処理がDiv.4にしてはかなり難しかった。
　また、この説明では添え字をいい加減に書いているが、添え字を合わせるのも大変。
時刻: 0 件のコメント:
ラベル:

Ｓｋｙ株式会社プログラミングコンテスト2023（AtCoder Beginner Contest 289）

　Eまで五完。

コンテスト後のツイート

F - Teleporter Takahashi

　解説AC。

　コンテスト後、乱択で良いのでは？　と思って実装するもWAやTLEがでてしまい、解説を見た。

　結論からいうと、乱択でも解けるが、結構ケアしなくてはいけない部分が多かった。

・二回の操作をセットにする。二回操作した結果、近付いていたら採用する
・[a, b], [c, d]の範囲で乱択しても上手くいかない。[a, a+1], [c, c+1]で乱択すると良かった。（2*2の範囲があれば偶奇が一致する点ならどこへでもいける）
・a=bやc=dについてケアしなくてはダメ。奇数でないとたどりつけないなら、最初に一回処理しておく

　とすればACできた。
　ただこれでは、解説にある内容大体が分かっていないと書けないので、乱択のうまみはあまりない。

G - Shopping in AtCoder store

　Convex Hull Trickという情報を得てAC。ただ、書き方を忘れていて実装に苦戦した。

　今回は、はじめに必要な直線群が何かを調べ、その後、三分探索によって答えを求める、という方針で解いた。直線群を求めるところ（外積を使って不要な直線を消去する部分）は同じ処理でできることに気を付けよう。
　その上で、max/minを知りたいindexが単調ならdequeを使って処理することができる。（今回も、クエリソートすればそうやって処理が可能）
時刻: 0 件のコメント:
ラベル:

2023年2月11日土曜日

yukicoder contest 376

 　Dまで四完。


No.2212 One XOR Matrix

　解説ツイートを見てAC。

　sampleから再帰的に構成しようとは思ったのだが、構成方法が思いつかなかった。

・縦横のxorが0になる4*4行列はすぐに見つかる

　ことを利用して、sampleのものと二つで構成しようと考えると良かった。
　sampleのようなxorが1になるようなものを左上、右下に。0になるものをそれ以外におき、上の桁は適当に作れば条件を満たす。

No.2213 Neq Move

　一応自力AC。

　適切にDFSしたら通ったが、実装に時間がかかったし、一回WAも出してしまった。

No.2214 Products on Tree

　解説AC。

・積の和は計算しにくいので、組み合わせの問題に味方を変える

　は典型だが、どう読み替えればいいのか、なかなかコツが掴めない。
　その後の木DPの遷移は自力で考えたが、遷移を導くまで苦労してしまったのは反省。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Round #851 (Div. 2)

　ABCEの四完。解かれた人数を見ると、Dは解かなくちゃいけなかったみたい。

コンテスト後のツイート

D. Moving Dots

　解法ツイートを見てAC。
　主客転倒っぽくやるのだろうとは思ったけど、考察が進まなかった。

・二点を全探索し、その二点が一点で交わる条件を考える

　とすれば良い。

　A[i]=xとA[j]=yが一点に集まるとすると、dis=y-xとすると、[x-dis,y+dis)にはこの二点しか存在してはダメ。逆に、他の頂点は存在してもしなくても良いので、2^(他の頂点の個数)を足せば答えが求まる。
時刻: 0 件のコメント:
ラベル:

2023年2月10日金曜日

Toyota Programming Contest 2023 Spring Qual A（AtCoder Beginner Contest 288）

 　Fまで六完。決勝進出。予選Aで決勝進出できたのは嬉しい。（予選Aで進出できる確率は１割程度、予選Bなら５割程度、と見込んでいました）

コンテスト後のツイート

G - 3^N Minesweeper

　解説放送を見てAC。

　「軸ごとに同じ計算をすれば良い」というのは思いつきたかった。
　ただ、そう思いついたとしても、実装はできなかったと思う。方程式を解くときと同じことを各軸についてやるのだが、その書き方も結構技巧的。
　畳み込みのときはこういう風に書くもの、と慣れるしかないね。

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

2023年2月9日木曜日

AtCoder Regular Contest 155

　Bまで二完。

コンテスト後のツイート

C - Even Sum Triplet

　解説AC。
　難しい問題だとは思うけど、色々と間違った考察をしていたのがひどい。

　たとえば、

・奇数同士の交換ができる場合、奇数を左側に集めて比較して良い

　は検討したのに、ダメだと結論してしまった。一度くっついた奇数同士は距離2以上離れない……などと考え、実装に苦戦したが、その考察自体が間違っている。

　まあこれは、

A=[2, 2, 3, 5, 2, 2, 2]
B=[3, 2, 2, 2, 2, 2, 5]

　みたいなとき、AからBは作れないよね、といったあたりが根拠だった。

　つまり、解説の最初の部分、

・奇数2項、偶数1項に対する操作が（一回でも）可能だった場合、その操作可能性は操作前後で変化しないので、AとBで一致している必要がある

　というのを見逃したのが敗因か。この部分を思い付ければ違った可能性はある。

　ただ、それ以外でも、解説の[1]の場合、偶数は多重集合と一致していれば良いと思っていたりと色々ひどかった。

　なんらかの標準系（今回なら奇数を左に寄せた形）にした後で比較して良いのは、（標準系にするまでの）操作が可逆なときなはず、というのは頭に入れておこう。
時刻: 0 件のコメント:
ラベル:

2023年2月7日火曜日

Codeforces Round #846 (Div. 2)

　Cが出題ミスでunratedになった。

コンテスト後のツイート

F. Three Chairs

　自力AC。

・各iについて、「gcdがiの倍数になる組み合わせ」を求める。
・上で求めたものをSCOREという配列とすると、j : iの約数 に対してSCORE[j]-=SCORE[i]　というのを大きい数から行う。これで、SCOREという配列が、「gcdがiになる組み合わせ数」となる。

　という流れ。

　大体こういう流れだとは思ったのだが、一つ目のやり方が分からず時間がかかってしまった。SUM[i]で、i以下に存在するAの個数とすると、
　iの倍数についてi, 2*i, 3*i, ...　と調べていくとき、

・j in Aであるようなjが何回登場したか
・それらについてのSUM[j]の和

　をもっていればSCOREを計算できる。
時刻: 0 件のコメント:
ラベル:

2023年2月4日土曜日

yukicoder contest 375

 　途中で睡魔に襲われたりして、Bまで二完で終わってしまった。Cは終了後すぐAC。


No.2204 Palindrome Splitting (No Rearrangement ver.)

　一応自力AC。

　DPだが、計算量見積もりを誤り、毎回愚直に回文判定をしても間に合うと思ってしまった。TLEが返ってきてダメだと気付いたのはひどい。反省。

No.2205 Lights Out on Christmas Tree

　自力AC。

　トポロジカルソートして葉から貪欲に処理していけばOK。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)