2024年4月28日日曜日

AtCoder Regular Contest 176 （Sponsored by Mynavi）

　Cまで三完。ARCでこれくらいの順位が取れると嬉しい。

コンテスト後のツイート

D - Swap Permutation


　解法ツイートで行列累乗で解けるというのを目にしたが、ある(a,b)というペアが最終盤面でどのような位置にあるか？　という遷移を考えてしまい、上手くできなかった。

　index i, i+1が最終的にどの数字になっているか？　に着目するのは言われてみれば自然。コンテスト中に解けなかったのは仕方ないにせよ、行列累乗で解けると言われたら思いつきたかった。
時刻: 0 件のコメント:
ラベル:

2024年4月25日木曜日

Educational Codeforces Round 163 (Rated for Div. 2)

　Eまで五完。

コンテスト後のツイート

F. Rare Coins

　解説AC。

　自分になじみのない解法が必要かと思って解説を見たのだが、普通の方法で解けた。

　ちゃんと問題を整理し、1/2の確率で自分のお金が増える、相手のお金が増える、というのを元のお金を調整して、「1/2の確率で差を減らす」と解釈するとシンプルな二項係数の和になる。










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

2024年4月23日火曜日

Codeforces Round 940 (Div. 2) and CodeCraft-23

　Dまで四完。ARCの後だったこともあり、前半は休み休みやっていた。

コンテスト後のツイート

E. Carousel of Combinations

　解説AC。

　Combi(n, k)*(k-1)! mod k の和を求める問題。実験コードを書いてこれを計算してみると、k=4と素数のとき以外は0になること、かつ、規則的に値が変化することが分かる。ｋを固定したとき、最初に値が正になるのはn=kのときで、k-1。そこからkごとに-1し、0になったらまたk-1に戻る。（これはkが素数のとき。k=4は2と0を交互に取る）

　これが分かった後、埋め込みか？　などと考えてしまい解説を見てしまったが、累積和を二回やるのが正しかった。規則的に値が変化するのだから、累積和を考えるのは自然。

　大体解けたけどTLEが微妙ってとき、変な手法を考えてしまうのは悪い癖。まともに計算量を減らす手法を考えるようにしないといけない。






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

2024年4月22日月曜日

AtCoder Beginner Contest 350（Promotion of AtCoderJobs）

　G解けず。Fで苦戦したため順位は悪い。

コンテスト後のツイート

G - Mediator

　解説AC。

　マージテクで解いた。コンテスト終盤にマージテクが使えるんじゃないか？　というアイディアは思いついたけど、具体的な解法には思い至れなかった。
時刻: 0 件のコメント:
ラベル: ,

2024年4月20日土曜日

yukicoder contest 428

　Dまでの四完。Eが解けそうで解けず、FはTLEに苦しむ。



No.2732 Similar Permutations

　4で割った余りで分類し、同じものが二つあれば1,2を入れ替えて置けばOK。
　ただし、Nが5以上ならこれでOKだが、Nが小さいときはこれだと答えが探せない場合があるため全探索。

　コンテスト中、こういう解法を考えたがWAが出たので、何か考察ミスがあるのだろうと別の解法を探してしまった。
　が、コンテスト後、改めて考えて見ると正しそうな気がし、コードを見直したら実装ミスに気付いた。（Nが小さいとき全探索する部分でミスがあった）

　これで提出したがWA。
　Xで割った余りが3や4の場合は、1,2を置くのではダメですね。2,3を置くようにしてAC。

　解説を見たら、2で割った余り（つまり偶奇）が同じものが二つあれば、上と同じような議論ができるらしくびっくりした。

No.2733 Just K-times TSP

　各頂点を何回通ったかと、最後に通った頂点を持ってDPすれば良い。PyPyだと制限時間が厳しく、コンテスト後に定数倍高速化を頑張ってなんとか通した。

　しかし、writer解がPyPyで、シンプルかつ高速に書けていた。こういう風に書けば良かったのか……。
　同じような風に書こうとして上手くできず、itertools.productを使ったのだが。

No.2734 Addition and Multiplication in yukicoder (Hard)

　自力AC。

　ちょっと実験してみると、最終的にできる数字はA[i]たちを適切に並び替えたものになると分かった。
　なら、A[i]を文字列とみてソートし、その順に置いて行けば良いのかと思ったがこれだとWA。

　よく考えると、"2"と"21"なら"21"の方が先に置いた方がお得。

　じゃあ、"2"は"22222222222222222"として"21"は”212121212121212121"のように元の数字を繰り返したものとして判定すれば良さそう。こうみなしてソートした後、並べていったら（TLE、MLEにちょっと苦しんだけど）ACできました。
時刻: 0 件のコメント:
ラベル:

2024年4月18日木曜日

AtCoder Beginner Contest 349

　Eまで五完。Eまでが速かったのでギリギリ黄色に復帰できました。

コンテスト後のツイート

F - Subsequence LCM

　素数の個数でいけるというのを手掛かりにAC。

　ゼータ変換を使う方法は思いつかなくても、DPで素数の個数^2でやる方法は難しくなかった。これはコンテスト中に落ち着いて考え直していたら通せていたはず……。

　



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

2024年4月15日月曜日

Educational Codeforces Round 164 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Chain Reaction

　解説ツイートを見たところ、√max(A)回加算するというところは合っているみたい。
　→落ち着いて書き直したら答えがあった。

　ただし、PyPyだと制限時間が厳しく、PyPy2で2999msでACした。ルートだけでなくlogもかかっているからねぇ。二分探索使わない方法はあるのだろうか……と書いていたら、使わなずにできそうな気がしてきた。

　a/xの繰り上げが変化する場所をメモしていけばいい（後で累積和を取る）ので、前半はxを一個ずつ増やし、後半はa/xの値を一個ずつ減らしていけば良さそうです。
時刻: 0 件のコメント:
ラベル:

2024年4月14日日曜日

Codeforces Round 939 (Div. 2)

　Cまで三完。

コンテスト後のツイート

D. Nene and the Mex Operator

　コンテスト五分後くらいに実装終わり、そのコードでACできました。
　この問題の実装に時間がかかったのは良くない。


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

2024年4月13日土曜日

yukicoder contest 427 (ゲーム問題コンテスト)

　Cまで三完。


No.2724 Coprime Game 1

　解説AC。

　N/2以上の素数は使えないけど、それ以外の数は使えるはず→WA
　解説を見たら、Nが素数の場合後手必勝と書いてあった。これを忘れていました。直してAC。

No.2725 Coprime Game 2

　自力AC。

　未証明で投げたらACした。解説を読むと、この証明は自力でできた気がする。（まあ、直感が正しいというのも大事なことだと思う）

No.2726 Rooted Tree Nim

　解説AC。

　「個数制限付きNim」と、「Staircase Nim」に関する知識があれば解ける。後者についてはyukicoderの問題で見た記憶があったけど、覚えていなかったなぁ。

　この問題の後に書かれた記事のようだけど、kobaeさんの記事でNIM問題をまとめてある。頭に入れておきたいね。


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

2024年4月10日水曜日

Codeforces Round 938 (Div. 3)

　Gまで六完。

コンテスト後のツイート

H. The Most Reckless Defense

　解説AC。

　タワーごとに独立でやれば良いのでは？　と思ったが、よく分からず解説やこたつがめさんの放送を見た。（独立にやれば良いというのは正しかった）
　bit DPを使って解けば良い、というあたりで問題文を誤読していたことに気付いた。……というか、その部分以外も、問題文を正確に把握できていなかった。

　難しい問題ではないのだが、問題文の内容を理解するのが難しいと思う。
時刻: 0 件のコメント:
ラベル:

2024年4月8日月曜日

yukicoder contest 426

　AB二完。


No.2716 Falcon Method

　自力AC。
　二分探索だとは思ったが、添え字で混乱したりしてコンテスト中に通せなかった。

No.2717 Sum of Subarray of Subsequence

　（一応）自力AC。

　立式して、Wolfram alpfaに突っ込んだら正しい式を返してくれたので解けたが、式変形まで自分でやれと言われたらできる気がしない。

No.2718 Best Consonance

　解説AC。

　gcdを使えば立式できるがgcdはA[i],A[j]を決めないと計算できない。
→gcdの代わりに約数を使っても答えは変わらない！　約数なら予め列挙できる！

　と、gcdを公約数に緩和するのがポイント。

　解説を見ても理解できず、解法ツイートをいくつか見たら理解できた。

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

2024年4月4日木曜日

ユニークビジョンプログラミングコンテスト2024 春（AtCoder Beginner Contest 346）

 　Fまで六完。

コンテスト後のツイート

G - Alone

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

　各数字のx個目を見て、その数字を一つだけを含む区間がどこなのか？　というのを求める方法は分かっていたが、重なる区間の処理をどうすれば良いかが分からなかった。

　それが長方形区間に対応する→平面走査　と考え、遅延セグ木を用いれば処理できる。
　ただ、平面走査した後も、どう遅延セグ木を用いれば良いかは解説を見なければ分からなかった。ただ、ここは典型問題で、 （公式解説にも書いてある通り）Library Checkerにもあった。




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

2024年4月3日水曜日

AtCoder Beginner Contest 347

　過去最高順位で黄色に復帰！

コンテスト後のツイート

F - Non-overlapping Squares

　解説AC。

　長方形三つは「品目」と覚えると良いらしい。知らなかった。
　これを知っていれば多少実装は大変だが難しくはない。
時刻: 0 件のコメント:
ラベル:

April Fools Day Contest 2024

　遅刻参加してABFの三完でした。FでQRコードを思い付けたのは嬉しい。


C. They Have Fooled

　解説AC。
　コンテストに関連するのか？　とはちょっと考えたが、問題数とは気付かなかった。

D. Are You a Procrastinator?

　解説AC。
　時間が影響するとは考えなかった。Procrastinatorという単語になじみがあれば思いつけたんだろうか。

G. Mathematician Takeover

　ヒントを見てAC。
　なるほど、確かにコンピューターサイエンスではlogといえば底が2のlogを指しますね。
時刻: 0 件のコメント:
ラベル:

2024年4月2日火曜日

AtCoder Grand Contest 066

　一問も解けず青に落ちた。

コンテスト後のツイート

A - Adjacent Difference

　解説AC。

・市松模様に分ける
・片方を0, もう片方をd (mod 2*d)にする

　どちらも考えたはずなのに、一次元でも上手くいかない気がして捨ててしまった。上手くいかなかったのは、mod 2*dで良いと明示的に考えられていなかったのと、例で計算するのが下手だったせいか。

　ただ、公式解説の、これで良いという証明は自分には思いつきにくいものだった。これを思い付ける数学的証明能力があれば解けていたかもしれないので、そこを反省しよう。

B - Decreasing Digit Sums

　解説AC。

　5ベキに注目するのは全く考えなかった。N=3となる小さい数として625にはちょっと着目したけどそこから考察を進められなかった。

　単純にその数のNの値を考えるのではなく、二倍していったときに桁和がどう変化するかに着目するのが大事だったのですね。

　答えを直接求める実験をするのではなく、ちょっと一般化したような内容で実験をするというのはしばしば必要となる手法。直接答えを求める実験しかせず何も情報を得られず失敗したことは結構記憶にある。そのあたりが反省点か。

　なお、コンテスト中は、あるSにx*2ベキを文字列として足したものを繋げていってNが大きくなるものを探すような実験をしていた。（これでN=19まで見つけられた）
　この実験コードの2ベキの部分を5ベキに変えたら（理由はよく分かっていないが）N=51のものが見つかった。
時刻: 0 件のコメント:
ラベル:

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 件のコメント:
ラベル:

2024年2月29日木曜日

ユニークビジョンプログラミングコンテスト2023 クリスマス (AtCoder Beginner Contest 334)

　Fまで六完。連敗は止めた。

コンテスト後のツイート

G - Christmas Color Grid 2

　解説AC。

　lowlinkでできるらしいと聞いて、lowlinkのライブラリは持っていたし、コンテスト中にも考えたのに……と思ったが、何個の連結成分に分かれるかは考えたことがなかった。
　さらに、実は自分のlowlinkライブラリが間違っていたことが判明。AOJでは通っていたので安心していたが……。

　コンテスト中に通せる可能性はほぼなかったし、lowlinkライブラリの間違いを直せたので良かった。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Round 929 (Div. 3)

　全完。
　最近、Div.3も全完できていなかったので、全完できて嬉しい。

コンテスト後のツイート


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

2024年2月28日水曜日

yukicoder contest 418 (Re: start!)

　Dまで四完。


No.2651 [Cherry 6th Tune B] Complex комбинат

　解説AC。

　複素数の式変形を頑張るしかない。

　解説を見て式変形を追うこと自体は難しくないが、自分でやるのはかなり厳しい……と思って、他の人がどうやって通したのかとTwitterを見たら、Wolfram alphaを使っていた人が多そうだった。
　とはいえ、Wolfram alphaに入れれば解説の式変形をすぐやってくれるという感じでもないので、何をWolfram alphaに入れるか？　また返ってきた式をどう捉えるかといったあたりに習熟する必要がありそう。


No.2652 [Cherry 6th Tune N] Δρονε χιρχλινγ

　解説AC。

　問題を見て、焼きなまし？　と思い、本当にそれで良いのか解説を見たら、Mo's algorithmを使うと条件を満たすと書いてあった。

　Mo's algorithmは思いついたけれど、それで条件を満たすとは思わなかったなぁ。ちゃんと検討すべきだった。

　なお、まず山登りを書いてみたが（PyPyでは）TLE、その後Mo's algorithmでACしました。

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

2024年2月27日火曜日

鹿島建設プログラミングコンテスト2024（AtCoder Beginner Contest 340）

　Fまで。

コンテスト後のツイート

G - Leaf Color

　解説放送を見て、 Auxiliary Treeを使ってAC。

　仕組みは理解したが、汎用性のない実装になってしまった。
　ライブラリ化はしていないけど、一応このときの提出にコメントをつけたので、後で見ても分かるといいな。


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

2024年2月25日日曜日

Educational Codeforces Round 162 (Rated for Div. 2)

　Dまで四完。さらにレートを落とした。ひどい。

コンテスト後のツイート

E. Count Paths

　マージテクでAC。

　最近のABCで似た問題が出題されていることに引きずられてしまったが、マージテクでも解けると言われたら普通に解けた。
　コンテスト中もマージテクを検討したので解けておかしくなかったはずなのに、なぜかライブラリを持っていない解法に突撃したのがひどい。
　このABCをまだ復習していなかった、というのも反省。
時刻: 0 件のコメント:
ラベル: ,

HUAWEI Programming Contest 2024（AtCoder Beginner Contest 342）

　Eまで五完。

コンテスト後のツイート

F - Black Jack 

　解説AC。

　コンテスト中は三分探索に固執してしまった。
　解説を見たらすぐ理解＆ACできたので、解けなくてはいけない問題だったのは間違いない。

　ただ、今見ても三分探索で通りそうに思えるので、三分探索に飛びついたのは仕方ないかな、という気もする。方針転換できなかったのは反省。

G - Retroactive Range Chmax

　自力AC。

　双対セグ木にheapqを乗せるだけで簡単だった。ちゃんと順位表を見てこっちから解くべきだったけど、Unratedだったからまあ良いか。




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

2024年2月23日金曜日

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

　Fまで。

コンテスト後のツイート

G - Highest Ratio

　解説放送を見てAC。

　「凸包」というキーワードを見ても分からず解説放送を見た。

　式から図形的性質を読み取るのは昔から苦手だったので解けなくても仕方なかったかな……とも思わなくはない。しかし、実験して、左端lに対して、右端rがどの位置で最大値を取るか？　と考えていれば凸が見えなくても解けて欲しい気もする。

　いずれにせよ、難しい問題ではなかった。

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

2024年2月21日水曜日

think-cell Round 1

　D1まで。D2もEも分からず、またレートを下げる。

コンテスト後のツイート

D2. Sum over all Substrings (Hard Version)

　解法ツイートを見てAC。

　大事なことを見逃していた。「1、010、001100、……のいずれかを置く」と考えていたが、置くのは基本的に「010」だけで良かった。
　これに気付かなくてもD1がACできてしまうから、DPの遷移について考えなかったなぁ。

　そう気付けると、D2のDPは自然に書けた……のだが、思いつくまで結構時間がかかった。時間がかかった原因は「配るDP」が頭にあったせいかなぁ。「もらうDP」で書こうとすると簡単に書けた。

E. 2..3...4.... Wonderful! Wonderful!

　解説AC。

・出来上がりったsequenceがgoodになる条件を見つける
・goodでないsequenceの数える

　の二つができなくてはいけなかったが、どちらもできていなかった。

　できなかった一因は、実験して数を数え、oeisなどでどうにかしようとしてしまったことか。二項係数の和みたいになることは分かったが、そこから考察が進まなかった。

　実験すること自体は間違っていないので、そこから情報を得ようとするところに問題があった。自分には、実験した後、頭を使わずどうにかしようとしてしまう傾向がありそう。実験の結果を眺めて、なんで二項係数の和になるんだろう？　という方向で考えなくてはいけない。（そういう風にしたら思いついていたかはまた別の話だが）


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

2024年2月20日火曜日

AtCoder Regular Contest 172

　体調が悪かったのと、AHCの途中ということもあってUnrated参加で三完。Ratedで出ていたら+10くらいだったみたい。

コンテスト後のツイート

D - Distance Ranking 

　解説AC。

　解説を読むとこの問題も解ける可能性がある問題だった気もしてしまうが、本番中は立方体で正三角形を作るということすら全く思いつけておらず、焼きなましなんかしようとしていたんだよね。惜しいところは全くなかった。

　二次元でも解けそうな問題（実際、サンプルは二次元で解を作っている）のにN次元で出題されているのだから、それを利用した解法がないか考えなくちゃいけなかった。それで発想できたかはともかく、そこは反省点。

E - Last 9 Digits

　解説AC。

　実験して予想する方法も、10=2*5を利用する方法も、思いついて良いものだった。こういう、色々試してちょっと強引な方法でも解ける方法で解ける問題は取らなくてはいけないのに。




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

2024年2月16日金曜日

Codeforces Round 926 (Div. 2)

　Dまで四完でさらにレートを落とす。問題を理解するのに時間がかかったのが敗因の一つだけど、他の人も読解には苦戦してそうだねぇ。考察速度も遅かった。

コンテスト後のツイート


F. Sasha and the Wedding Binary Search Tree

　大小の配列が一意に決まるという情報を得てAC。

　これ、言われてみれば当たり前なのにコンテスト中に気付かなかった。そして、ただdfsする感じで良いのに、しばらく考えないと復元方法も分からなかった。



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

2024年2月14日水曜日

Codeforces Round 925 (Div. 3)

　全完。と思ったらシステムテストでDが落ちた。

コンテスト後のツイート

D. Divisible Pairs

　dictのハッシュ衝突対策で、randomな数をdictのキーとxorしなくちゃいけないのに、値とxorしていた。
　多分、このミスをしたのは初めてですね。そんなにしないミスだと思うけど、まあ気を付けよう。

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

2024年2月10日土曜日

yukicoder contest 417

　Eまで五完。

コンテスト後のツイート

No.2626 Similar But Different Name

　解説AC。

　ローリングハッシュ（など）を使えば大文字小文字の違いを区別しない場合の一致できるかは判定できる。問題は、大文字小文字が異なる箇所が1文字以上K文字以下という方。bisetか？　と思ったが、あまり時間に余裕がなさそうで止まってしまった。

　FFTを使うとは思いつかなかったが、言われてみると典型っぽいので、この手法は覚えておきたい。SとSより短いTに対して、Sの全ての連続部分列とTを比較するときにFFTは使える。
　ただ、FFTを使うとしても、使い方がすぐには思いつかなかった。色々な解法ツイートを見て、大文字=1、小文字＝-1とするのが分かりやすく感じ、その方法でACした。
時刻: 0 件のコメント:
ラベル: ,

2024年2月7日水曜日

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

　Eまで五完。

コンテスト後のツイート

F - Usual Color Ball Problems

　解説放送を見てAC。

　Kがなかったら尺取りで簡単なのに……から進まなかったが、

・どの色を何箱使うか、さえ分かれば答えは計算できる

　ことに気付けば、Kがあっても尺取りでやることができた。

　確かにちょっと気付きにくいけれど、尺取りでやるしかないと思えば十分思いつける内容だった。
　コンテスト中はGばかり見てたから仕方ないけど、これは自力で解けても良かったね……。

　

G - Tree Inversion 

　解説放送を見てAC。

・木において、部分木は区間で表せる

　を利用し、あとは差分計算で解く問題で、難しい知識は必要なかった。そういう意味では解けなくてはいけない問題だった。ここで既出だったようだけど、既出じゃなくてもまあまあ解かれていた気がする。

　しかし、解説を理解してからも答が合わずかなり時間を費やしてしまった。
　値の足し引きをどこで行うかにかなり神経を使った。

　実装の仕方が悪いんだけど、おとなしく再帰で書いた方が良いのかなぁ……。

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

Codeforces Round 923 (Div. 3)

　Fまで六完。FでLOWLINKを持ち出すまで迷走したのが痛い。

コンテスト後のツイート

G. Paint Charges

　一応自力AC。

　まあDPするしかないけど、同じやつを左右両方に使うと困る。なので、左方向に使ったやつだけ特別扱いする別のDPテーブル用意して、そこからは右に遷移しちゃいけないよ、とした。

　なんか無理矢理やった感じが強いけど、これ良いんだろうか。
　→Hackされたが修正してAC。
時刻: 0 件のコメント:
ラベル: ,

2024年2月5日月曜日

AtCoder Regular Contest 171

　AB二完。まあまあ速かったのでレートが減ることはなかったが、難しい問題が解けないなぁ。

コンテスト後のツイート

C - Swap on Tree

　解説AC。

・どの辺について操作するかを決めたとき、「各頂点で、どの順番で辺を消していくかを決めるかと操作終了時のAが定まり、それらは全て異なる」

　ということに気付かなくてはいけなかった。

　コンテスト中は、ある頂点をどこへ移動させるか……というようなことを考えていて、順番が大切だということは分かっていた。そこから類推して、順番さえ決まれば数列が定まるのでは？　と思わなくてはいけなかった。

　その後の木DPも結構難しいが、ここまで分かっていれば遷移式は立てられるか。

D - Rolling Hash

　解説AC。

　コンテスト中は問題を読み、ニ十分くらい考えたが何も思いつかなかった。BがPの生成元になっているかで条件が変わってくる？　とか考えていた時点でダメ。まず、B=1のときに解けるかを考えるべきだった（今回は、それが答えになっている）。Bが本質的には関係なさそうなのはまあそうなので、B=1で考えるのは自然。

　B＝1のときはグラフの彩色数を求めれば良い、というのもしばらく納得できなかったのは、彩色数の定義が頭に入っていなかったせいか？

　グラフの彩色数自体はこのFを解いていたのだが、このときは彩色数とはあまり考えなかったからねぇ。

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

2024年2月4日日曜日

日本レジストリサービス（JPRS）プログラミングコンテスト2024（AtCoder Beginner Contest 339）

　Fまで六完。

コンテスト後のツイート

D - Synchronized Players

　コンテスト中は、四方向の移動を愚直に書いていた（四回コピペ）したらTLEして困っていたのだけど、for文で

・for dx,dy in [(1,0),(-1,0),(0,1),(0,-1)]:

　みたいに書いたら700msになった。

　PyPyのforは遅いからコピペした方が速いと思ってたんだけど、今は違うのかな……。

F - Product Equality

 何個かmodを取り、乱択するのが想定だったらしい。なるほど。

G - Smaller Sum

　コンテスト中、wavelet matrixで解ける気がして検索したらけんちょんさんのこの記事が出てきた。

　ここにあるコードを使って通そうとしたが修正に時間がかかり通せなかった。C++のコードを改造する力も付けたいね……。

　公式解説のmerge-sort treeを使う方法も理解しないとね。


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

2024年2月3日土曜日

Codeforces Round 922 (Div. 2)

　Dまで四完でさらにレートを落とす。

コンテスト後のツイート

E. ace5 and Task Order

　コンテスト中提出したコードをPython3で出したらあっさり通った。

　PyPyのprint(flush=True)が遅いというのを忘れていたのが敗因。こどふぉでは、「PyPy3でTLEしたらPyPy2やPython3でも試してみる」というのも重要ですね。PyPy3-64ができてから、PyPy3-64とPyPy3しか試さなくなっていた気がする。

F. Caterpillar on a Tree

　解説AC。

　解法ツイートで貪欲でいい、というのを見てもどう貪欲すれば良いか分からなかった。

　全ての葉を通れば良いので、葉の順番を考えれば良いというのは分かったが、その上で、

・子の中からmax深さが低い順にたどって、葉をつないでいくのが最適

　と気付くと、そのうちどこかの葉で親まで戻ったとき、何歩省略できるかが分かる。
　あとはソートしてやっていけばOK。

　E捨ててFいっていれば良かったかな、とコンテスト直後は思っていたけど、これだと無理だったかな……。
時刻: 0 件のコメント:
ラベル:

2024年1月28日日曜日

Codeforces Round 921 (Div. 1)

　A一完で紫に落ちた。

コンテスト後のツイート

B. Space Harbour

　等差数列をセグ木で扱えることは知っていたが、どうすれば良いか覚えていなかったので、検索するとstoqさんのこの記事が出てきた。
　等差数列を足し込む遅延セグ木があることを知り、そのコードを拝借して解こうとした動き自体は良かった。遅延セグ木を使う問題だとPyPyじゃ間に合わないことも多いしね。

　しかし、C++に慣れていないためコードを直すのに時間がかかり、WAが出た後の修正もできなかった。

　結局、間違っていたのは、「upper_bound()をそれ以下のindexが現れる最大のindex」だ
と思うという勘違いのため。

　lowerとupperで対称的なのかと思ってしまったんだねぇ。そして、それでもtest7まで通ってしまったため、定義を確認したり色々なケースを試そうという気持ちになれなかった。せめて他のケースを試していれば気付けて時間内に修正できた可能性はあるね……。そこも反省。

・lower_boundはbisect_left
・upper_boundはbisect

　胆に銘じておこう。

　なお、その他に添え字ミスもしていて結構ACは遠かった。test7まで通ってるから本質的なミスじゃないはず、と思ったのがはっきり間違いでした。

　

　


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

AtCoder Beginner Contest 338

　Eまで五完。

コンテスト後のツイート

F - Negative Traveling Salesman

　解説AC。

　ワーシャルフロイド法により、二点間の最短距離を全て求めておく。その距離を使って、全点を巡る距離をbit DPで求めれば良い。
　x→zよりx→y→zが短いとき、前者で計算してしまうのが問題になる気がするが、結局後者でも計算することになり、通った集合が後者の方が優れているのでこれで答えが求まる。

G - evall

　解説放送を見てAC。

　解説放送を見たときは実装が大変に思えたが、そこまで大変な実装ではなかった。なお、再帰で書いたらPyPyではTLEになり、Pythonで提出したらACした。
時刻: 0 件のコメント:
ラベル: , ,

2024年1月27日土曜日

yukicoder contest 416

　AB二完。C分からず眠ってしまったが、眠くなくても解けなていなかった可能性が高い。


No.2616 中央番目の中央値

　解説AC。

　計算量が二乗になるところまでは良くて、そこからの式変形が難しい。ヴァンデルモンドの畳み込みを知っていれば思いつきやすかったらしい。解法ツイートを見てもこれを使っている人が多い。
　自力で解くなら、ちゃんと式に書く→検索する（Wolfram alphaを使う）という感じだったかなぁ。二乗方針を思い付いてはいたが、式に書き下していなかったのはまずくて、手間を惜しまずちゃんと式にして考えるべきだった。

No.2617 容量3のナップザック

　一応自力AC。

　最初、貪欲に価値が高いものを詰めていけば良いのでは？　と実装してWA。価値3の個数を三分探索し、価値2のをいくつ取るか全探索したらACしました。
　多分、価値2のやつも三分探索で大丈夫そうですね。

No.2618 除霊

　解説AC。

　何か難しい考え方を使うわけではなく、適切に場合分けして、適切にまとめれば解ける。そういう問題こそ実力が問われるねぇ。
　解けるまで自力で考えるべきだったか。

No.2619 Sorted Nim

　解説AC。

　最初、解説を読んでも意味が分からなかったけど、この問題と本質的に同じだという言及を見て考えたら、なるほど、という気持ちになった。
　
時刻: 0 件のコメント:
ラベル:

2024年1月22日月曜日

AtCoder Regular Contest 170

　Cまで三完。

コンテスト後のツイート

D - Triangle Card Game

　解説AC。

　コンテスト中は、同じカードを二度出して良いって条件で考えていたことに気付いた。自分の実装だと、簡単には修正できなかった（頑張れば修正できそうだが……）のだが、noshi91さんの解説を見ると、「Aliceが最初選ぶ手は、min(B)に関する条件を満たすもののうち最大のものとして良い」とあり、これを使ってAC。実装が大分楽になりました。

　A[i]を全探索という方針に走ってしまうと思いつきにくいけど、これ自体は言われてみれば確かに……という感じ。

　誤読してなかったとしても、実装に苦戦してACできなかったと思うけど、Cを飛ばしてDにいっていたらACできた可能性はあるかなぁ。
時刻: 0 件のコメント:
ラベル:

2024年1月20日土曜日

Codeforces Round 920 (Div. 3)

　遅刻してEまで。

コンテスト後のツイート

F. Sum of Progression

　自力AC。

　平方分割で、最近のABCに出た問題とほぼ同じ考え方で解けますね。ただ、こっちは、累積和に加えてx+2*x+..ももたないといけないのがちょっと難しかった。

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

2024年1月19日金曜日

AtCoder Beginner Contest 335（Sponsored by Mynavi）

　Fまで六完。黄色に復帰できたのは嬉しかった。

コンテスト後のツイート

G - Discrete Logarithm Problems

　解説AC。解説放送も見ました。

・素数pについて、Z/pZに積を演算としてみたものは元の個数がp-1個の巡回群になる。
・各要素の位数はp-1の約数になる。

　あたりは知識としてもっていたかった。（もっていたはずだが、よく覚えていなかった。コンテスト中に一応理解できたが）

　そのうえで、

・位数が約数・倍数の関係になっているとき、今回の問題の条件を満たす
・各要素の位数を求めることができる

　ことが分かれば解ける。

　整理して考えればそこまで難しい問題ではないのだが……。
　ただ、各要素の位数の求め方はちょっと思いつきにくいので、次出題されたとき解けるようにしておきたい。








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

2024年1月14日日曜日

Codeforces Round 919 (Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Counting Binary Strings

　ツイートした方法で通った。

　D通した時点で残り時間が少なかったけど、そこまで難しくないDPなので20分あれば通せて良かった。DPの高速化する問題だろう、と思うなら、dict（Counter）でDPを実装したのは筋が悪かった。dictで実装すると高速化が必要なとき手間が増えてしまう。
時刻: 0 件のコメント:
ラベル:

2024年1月13日土曜日

yukicoder contest 414

　Cまで三完。


No.2603 Tone Correction

　解説AC。類題

　こういう区間に関する問題で階差を取るのは結構何度もやっているのに、身に着いていなかった。

No.2604 Initial Motion

　最小費用流の問題だとは思ったのだが、各点から各点への最短距離を前計算しなくてはいけないと思ってしまった。グラフを直接利用して最小費用流へ持ち込むことができる。（が、自前の最小費用流ライブラリだとTLE。うーん）
時刻: 0 件のコメント:
ラベル: ,
登録: 投稿 (Atom)