2024年10月31日木曜日

Codeforces Global Round 27

　Cまで三完で過去最悪の成績で紫に落ちた。

コンテスト後のツイート

D. Yet Another Real Number Problem

　コンテスト中の最初の提出を修正してAC。最初に考えていた、dequeを使ってうまく後ろ二つをmergeしていく、という方針が正しかった。

　ただ、mergeの条件が間違っており、修正に10WAを費やしてしまった。ちゃんと立式すれば良いはずなのだが、立てた式で計算ミスをしていたりして……。

　ちゃんとやれば解けたはず、と言っても間違いではないだろうが、実際のACは非常に遠かった。
　

E. Monster

　コンテスト中に提出したもののパラメーターをちょっと変えたらAC。

　コンテスト中は、最大値が10^8なのに、10^5ごとに計算してその付近の上位三つを探索していた。平方分割を意識しているのなら10^4ごとに探索する方が自然だし、その方が適切に探索できるだろう、と変更（上位10個を探索）したらAC。

　7ペナもしているのに、この変更を思いつかなかったのはおかしい。焦って頭が働いていなかったんだろうなぁ。

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

2024年10月30日水曜日

Educational Codeforces Round 171 (Rated for Div. 2)

　Dまで四完。

コンテスト後のツイート

E. Best Subsequence

　「燃やす埋める問題」というキーワードを見てAC。

　コンテスト中、フローは少し考えたはずなのだが、ちゃんと追及しなかった。
　DPなどでは指数時間の解法しかないときにフローを疑うのは大事で、特に、「燃やす埋める問題」を疑ってみなくてはいけない。

　フローを考えた時間はあったはずなのに、「燃やす埋める問題」ではないかと考えなかったのは反省。





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

2024年10月29日火曜日

yukicoder contest 449

　Dまで四完。


No.2914 正閉路検出

　解説AC。

　コンテスト中に解けなかったのは仕方ないとしても、解説読まずにACしたい問題でした。
　重み付きUnionFindを使うというのは自然なのに、ちょっと捻った形で出題されると気付けないのは情けない。

No.2915 辺更新価値最大化

　解説AC。

　最短経路問題におけるポテンシャルは、最小費用流のライブラリを作ったときしか勉強しておらず、全く忘れていた。こういうときにも使えるのか。復習になった。

No.2916 累進コスト最小化

　自力AC。

　各cごとにダイクストラをするだけでした。
時刻: 0 件のコメント:
ラベル: , , ,

2024年10月27日日曜日

yukicoder contest 293

　A一問しか解けなかった。ひどい。


No.1492 01文字列と転倒

　一応自力AC。

　Tester解説と同じ方法だと思うんだけど、計算量がよく分からなかった。
　五乗じゃないの？　と思ったけど、ちゃんと解析したら四乗になりそうな気もしてきた。
時刻: 0 件のコメント:
ラベル:

トヨタシステムズプログラミングコンテスト2024（AtCoder Beginner Contest 377)

　Fが解けず六完。Eが難しかった。

コンテスト後のツイート

F - Avoid Queen Attack

　クイーンを置くごとに、置けなくなるマスが何個増えるか数える……というのはコンテスト中に考えていたが、setで管理すると書きやすいという情報を得て、その方針でAC。
　いや、今思うと、重複をどう処理するかはコンテスト中ちゃんと考えられていなかったね。既におけなくなっている座標をsetで管理するという方針は、実装面だけでなく、重複を取り除くという点でも大切だった。

　ただ、その方針でも実際に実装するのは苦戦した。





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

2024年10月21日月曜日

yukicoder contest 450

　ABCEの四完でした。


No.2940 Sigma Sigma Div Floor Problem

　解説AC。

　コンテスト中は、各i(<=N)について大体√iの計算時間で計算できるので、それをN回やっても間に合うか？　と思ったがTLE。埋め込めばACはできそうだけど実装しなかった。

　解説を読むと、シグマを交換するのが本質だった。
　割る数を固定するのではなく、割られる数を固定すると約数を考える問題になる。

　割る数を固定しても良いところまでいくこともあって思いつかなかったけど、頭の柔軟さが足りないね。

No.2942 Sigma Music Game Level Problem

　一応自力AC。

　セグ木を二本立てれば簡単にできる問題に見えたがWA。配列Lおよび三つ目のクエリの意味が分からないので、どこか誤読しているのかも……と思ってDへ戻ったが、単純な実装ミスでした。
　Aを回数順にしてからセグ木に入れなくてはいけないのにAをそのままでやっていた、セグ木の内部をちょっと書き換えたとき間違っていた、クエリ1でAに何か付け加えるときのupdateの仕方を間違えていた、と三ヶ所。

　こんな短い中で三つもミスしているのは良くないねぇ。

No.2943 Sigma String of String Score Problem

　自力AC。

　DPして部分列の個数を求めて、他の箇所を使うか使わないか決めれば良い。計算量10^8がPyPyで間に合うのか分からないまま提出しましたが、1sもかかりませんでした。

No.2944 Sigma Partition Problem

　しばらく考えた後、これって分割数ってやつでは？　と気付き、検索し、ここを参考にしてAC。

　分割数のDPを自力で導出するのは難しいけれど、有名な概念だということはすぐ気付きたい。
時刻: 0 件のコメント:
ラベル:

2024年10月20日日曜日

AtCoder Beginner Contest 376（Promotion of AtCoder Career Design DAY）

　Eまで五完。

コンテスト後のツイート

↑ツイートのFの位置が間違っています。

F - Hands on Ring (Hard)

　既にあるACコードとランダムテストなどしてAC。

　本質的なやり方は正しかったが、場合分けが足りていなかった（目的地の場所に別の手がある場合、二通り押し出すことを考えなくてはいけないのを忘れていた）り、既に目的地に手がある場合にも押し出すことを考えて答えが減ったりし、非常に苦労した。

　コンテスト後に一時間以上かかっている。本来ならランダムテストを書く時間も必要だったからもっとかかっただろう。解法は分かってもACは遠い問題ですね。

G - Treasure Hunting

　解説放送を見てAC。

　解法を思い付くのは難しいかもしれないけど、解法を教えてもらったとき理解するのは難しくない。
　ただ、実装方針はやや難しい。トポロジカルソート順にマージするのか？　などと考えてしまいダメだった。
　平均重みが大きいものから、親と比較し、マージしていくというのが正解。方針が分かってしまえば実装も重くない。

　類題（元ネタ？）というこれも解いておきたい。→ACしたけど結構実装に時間かかってしまった。maspyさんが類題をまとめてくれているので、これも解いておくべきか。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 979 (Div. 2)

　Dまで四完。Eを考えていたら寝てしまった。


E. MEXimize the Score

　自力AC。

　0から順に、部分列に何個採用するかを考える。

　たとえば、2をk-1個採用したときよりk個採用した方がスコアが上がるのは、0や1がk個以上含まれているときである。

　なので、今までの数字について、全てk個以上もっている場合の数は何通りか？　もっておき、それを利用して、k個採用したらスコアが上がる場合の数を計算、和を取る。

　一応、主客転倒の考え方を使っているのだが、最初それをしなくても間に合う気がしてDFSを書いてペナを出してしまった。主客転倒自体は思いついていたため、再度考え直してACした。
時刻: 0 件のコメント:
ラベル:

2024年10月17日木曜日

AtCoder Regular Contest 185

　AB二完。

コンテスト後のツイート

C - Sum of Three Integers

　解説放送を見てAC。

　FFTは全く考えなかったが、登場回数の配列同士を畳み込めば、二つの配列の和の要素の登場回数になる……というのは初見ではなかったかもしれない（よく覚えていないが）。これは身に着けておきたい。

　ただ、解法が分かった後もACに非常に苦労した。ランダムケースで実行しても何で落ちているのかが分からず、かなりたくさん提出デバッグをしてしまった。

・PythonでFFTを使うなら、配列をnumpy.arrayで書き、np.fft.rfft(A,k)やnp.fft.irfft(f)を使うと速い。
・畳み込み後の要素の値が大きくなることがあるため、np.fft.rfft(A,k)のkの値をギリギリに取るのではダメ。最大値をきちんと見積もる。

　このあたりが問題だった。気を付けないと。

D - Random Walk on Tree

　解説放送を見てAC。

　解説放送で一番難しいといっていたパートは、ChatGPTに「ランダムウォークで、スタート地点からn歩の点にはじめて到達する歩数の期待値を教えて下さい。」と聞いたら、「スタート地点 0 から n に初めて到達するまでの期待値は、1次元ランダムウォークでは次のように表せます:

・En=n^2　つまり、最初に n に到達するための期待歩数は n^2  です。」と正しい返事がきた。

　また、コンプガチャについてはけんちょんさんの記事など詳しいものがある。

　どちらも、自力で導出できると良いけど、覚えておいても良いくらいの内容な気がする。

　なので、対称性に関する考察さえきちんと行ってどんな問題に帰着できるか分かれば、あとは知識（もしくは調べて）で解けたんですね。

E - Adjacent GCD

　解説放送を見てAC。

　約数包除を行うとき、各素数についての他次元平面と考えると分かりやすい、というのは知っていた（が、コンテスト中は出てこなかった）。
　
　で、約数包除のとき、あるxについて、その約数に関する値の総和を取るとxになるような値があると良い。そういうのがあれば、毎回包除をして約数の個数^2の計算時間をかけず、約数の箇所にある値の和を取る/値を書き込むさえすれば、毎回約数の個数回の計算時間で済む。

　それを実現するのが、オイラーのトーシェント関数だった！

　オイラーのトーシェント関数の定義を考えれば簡単に分かることなのだが、はじめて知りました。
　約数包除に関して理解できた気がするので、もう忘れないといいな……。

　なお、今回の問題は、100000までのトーシェント関数の値と約数のリストを予め列挙してACしました。
時刻: 0 件のコメント:
ラベル: , , , , ,

2024年10月14日月曜日

パナソニックグループ プログラミングコンテスト2024（AtCoder Beginner Contest 375）

 　EとGが解けず。

コンテスト後のツイート

E - 3 Team Division

　解法ツイートを見てAC。

　部分和問題に近いからDPだろうと思ったのに、どういうDPをすれば良いか見えなかった。だからといって、フローを疑ったりしていたのはダメ。

　DP[Aの和][Bの和]=そのときのペナルティ

　のようにすれば良かった。Bの総和に制約があるのも不思議なので、そこからDPを見破ることもできたはず。

G - Road Blocked 2 

　解法ツイートを見てAC。

　スタートとゴールからダイクストラして必要な可能性のある辺を求めるところまではOK。あとは橋を探せば良かった。

　何度もランダムに進ませればどの辺が必要なのかは分かるのでは？　と思ったが、片側だけ二方向に分かれていく木を考えればすごい低い確率でしか到達しない頂点は作れて、それ以外の頂点を別の一つの頂点につなげる……みたいにすれば、そこから出た辺は非常に高確率で通りますね。


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

2024年10月11日金曜日

丸紅プログラミングコンテスト2024（AtCoder Regular Contest 183）

　Bまで二完。

コンテスト後のツイート

C - Not Argmax

　解説放送を見てAC。

　区間DPだと気付くことさえできれば難しくないと思う。問題はどうやって見つけるかだが……。手を動かして実験すれば見えてくるのかなぁ。

　なお、メモリ制限が結構きつい。各[l, r]に対してどのindexがmaxを取れるか？　を愚直に持とうとすると、500^3の配列が必要になり、PyPyだとMLEした。あとちょっとメモリを減らせばいいだけなのだが、そこに結構苦戦した。




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

2024年10月7日月曜日

キーエンスプログラミングコンテスト2024（AtCoder Beginner Contest 374）

　Fまで六完。

コンテスト後のツイート

G - Only One Product Name

　解説放送・解説を見て、けんちょんさんの記事も参考にAC。

　SCCして、DAG の最小パス被覆に帰着、という解法はちゃんと勉強していれば思いつけそう。（コンテスト中、自分も一瞬フローでは？　とは思ったので。その後違う方向に行ってしまったけど）

　ただ、実装が難しい。SCCで頂点と頂点とを同一視できても、そこから出ている辺は同一視できない、というあたりが混乱を招く。

　たとえば、AとBには両向きの辺があり、CとDには両向きの辺がある。さらに、AからCへ、BからDへそれぞれ辺があるとき、この二つの辺は区別しないといけない。

　このあたりに注意するのが非常に難しく、たくさんのWAを重ねてしまった。解法を詰めてからやればできるのかもしれないけど、解法の概要が思い浮かび、細かいところは実装しながら詰めよう、とすると非常に難しい気がした。
時刻: 0 件のコメント:
ラベル: , ,

2024年10月4日金曜日

Codeforces Round 974 (Div. 3)

　G以外六完。

コンテスト後のツイート

G. Milky Days

　自力AC。

　dequeを使って古いミルクを管理していけば良い。たいして難しくはないのだが、二度も誤読した。

・一度目の誤読：古い順に飲むと誤読
・二度目の誤読：milkがmに足りないとき、消費しないと誤読

　誤読したせいで非常に長い時間（一時間以上。二時間くらいかも）かかってしまった。
　





時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)