2023年4月30日日曜日

yukicoder contest 386

　Bまで二完。


No.2284 Assembly

　サンプル2の説明を誤読した（「i 番目の学生が前から Pi​ 番目の椅子に座る」を「Pi 番目の椅子にi番目の学生が座る」と勘違いしていた）のを修正できず、コンテスト後にTwitterで教えてもらいました。感謝。

　解説AC。
　なんとなく、大体貪欲にできるのでは？　というところから考察を進められず。逆から見れば良かったのですね。

　これ、この誤読自体はよくあるものだけど、誤読してるはずと思って読み返してもどこが間違っているか理解できない……というのは頭が働いていなかった一つの証拠という気もする。だから、こういうときはどうしようもない気もする。

　対策の立て方はあるだろうけど、調子がよければこういう誤読はしないはずだから、調子悪いときのために対策を立てても仕方ないかな、と思う。

No.2285 Make A Unit Square

　解説AC。

　Grundy数だと理解した後も、どんなゲームのGrundy数を調べるのか迷ったのは反省。
時刻: 0 件のコメント:
ラベル:

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

　Fまで六完。

コンテスト後のツイート

G - P-smooth number

　半分全列挙という情報を得てAC。

　最大でsample2の個数なら、上手く枝狩りすれば列挙できそうな気がして、どこかまとめて（メモ化再帰を使って）計算できるところがあるのでは？　という方向性で考えてしまった。

　言われてみれば半分全列挙も、劇的に計算量を改善するというよりは、全探索でも通りそうなものの計算量を減らす手段でしたね。ケアしないといけない。
時刻: 0 件のコメント:
ラベル: ,

2023年4月29日土曜日

Codeforces Round 868 (Div. 2)

　Dまで。EもFも復習しておきたい。

コンテスト後のツイート

E. Removing Graph

　解法ツイートを見てAC。

　Grundy数を使う問題で、一見この問題に似ている。ただ、サイクルから一回切り取るとpathになることに気を付けなくてはいけない。そのときは、この問題の簡単なバージョンだった。これらによりGrundy数を計算すれば解ける。

　ただし、それらを思い出せなくても、Grundy数は実験すれば求められる。
　実際私もコンテスト中に実験していた。しかしpath graphのGryndy数のみ実験し、cycleの場合を実験しなかったため解けなかった。path graphのGryndy数を使えば元のcycleのGrundy数もすぐ分かるのだから、ちゃんと実験していれば解けていたはず。pathの場合に何か規則性があるのでは？　などと考え（実際、0にならない、という規則はあったのだが気付けなかった）最後まで実験しなかったのはダメ。

F. Random Walk

　解説ACしたが今一つ納得できていない。類題が出たら解けない気もする……。

　公式解説よりもこのコメントの解説の方が分かりやすかった。s～t間のpathに含まれる頂点の期待値がdeg(v)*d(v)になるというのは納得。
　それ以外の頂点の期待値も似たように考えて求めることはできる……というのはそう。だけど、他の方のツイートとかを見ると、もっとすっきりとした理解の仕方がある気がする。
時刻: 0 件のコメント:
ラベル: ,

2023年4月27日木曜日

yukicoder contest 385

　睡魔に勝てずA一完。


No.2276 I Want AC

　自力AC。

　左側のいくつかを"A"に、残りを"C"にするのが最適。凸性がありそうなので三分探索（今回は中央の二点を調べれば二分探索でOK）。

　これくらいのことも思いつかない状態なら、寝て正解だったとも言える。

No.2277 Honest or Dishonest ?

　自力AC。これは手間取らずに解けた。

No.2278 Time Bomb Game 2

　解説AC。

　自分が最初にいるマスの幅以外関係ないのでは？　というのが直感で、大体それは合っていたものの、幅が1のときなどコーナーが多く、解き切るのは難しい。

No.2279 OR Insertion

　解説AC。

　桁ごとに考えるのは分かる。制約を見ると、その後DPすれば良さそうなのだが、どういうDPをすれば良いか分からなかった。

　DPで分割方法を求めようと思うのが重要。
　問題文に「分割の仕方は$2^{N-1}$」とある通り、分割の仕方はDPしなくても求められるが、DPでも求められるのは頭に入れておきたい。

　そう思えば、orの桁iが立っている/立っていないで場合分けして、Sのj文字目まで見たときのそれぞれの分割の仕方をDPで求めようという方針は立ちそう。

No.2280 FizzBuzz Difference

　解説AC。

　全く中国剰余定理を思いつかなかったが、分かってしまえば中国剰余定理の良い練習問題、という感じがする。適切に式を変形すれば中国剰余定理を使える形になるのだが、慣れていないと思いつくのも容易ではなさそう。

　こういうタイプの問題で中国剰余定理を使えることがある、と頭に入れておくしかないか。
時刻: 0 件のコメント:
ラベル:

2023年4月25日火曜日

Codeforces Round 867 (Div. 3)

 　G2が解けず。

コンテスト後のツイート

G2. Magic Triples (Hard Version)

　b（中央の要素）の大きさで場合分けするという解法ツイートを見てAC。a, b, cについて、b=a*x, c=b*xとなるxの大きさが10^3より大きいか小さいかで場合分けすると上手くいく。

　高速素因数分解などの方針が頭をよぎって思いつかなかったが、aが10^9以下という制約なら、三つに（10^3ずつ）区切ることは考えなくてはいけなかった。なお、PyPyじゃ通せずRUSTでAC。
時刻: 0 件のコメント:
ラベル:

2023年4月23日日曜日

東京海上日動プログラミングコンテスト2023（AtCoder Beginner Contest 299）

　Eまで。unratedになったこともあり、Gは見ずFを考えていたが分からずに終わった。unratedでやや集中力が途切れてしまったが、集中しても解けていなかっただろうと思う。


F - Square Subsequence

　解説AC。

　解説を見ると確かに典型の組み合わせなのだが、結構難しいと思う。

　制約を見ると、何らかのDPをするとは予想できる。
　また、重複して数えないため、できるだけ左にある文字で構成される「TT」を考えようとは思える。

　だが、二つ目のTの一文字目を決め、部分列DPを使って次の文字の位置を前計算しておくと、そのうちどういうものが「できるだけ左にある文字で構成される「TT」」二番目の条件を満たしているかが分かる……というのは言われてみれば分かるが思いつかなかった。

G - Minimum Permutation

　（デバッグでWAのテストケースを探すとき他の人のコードは見たけれど）解説は見ずにAC。

　一番はじめにおける候補（その後に、今まで使った以外の全ての数字が登場している）のうち最も小さいものを採用……というのを繰り返していけば良い。
　解法はそれで良いが実装がやや面倒で、BITやセグ木を使った。

　実装難ではあるけれど、解法を思い付く難易度はFより簡単ですね。

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

2023年4月22日土曜日

Educational Codeforces Round 147 (Rated for Div. 2)

　Dまで。

コンテスト後のツイート

E. Rearrange Brackets

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

　"("と")"の距離が最も離れたものから消していけばOK。あるカッコを消すときのコストは、その外側にあるカッコ達の個数により決まるので、逆にいえば、内側にたくさんカッコを含むもの（つまり、"("と")"の距離が離れたもの）から消していけば良いということになる。
時刻: 0 件のコメント:
ラベル:

2023年4月19日水曜日

第三回日本最強プログラマー学生選手権 -決勝- (オープンコンテスト)

　遅刻参加してA一完。

コンテスト後のツイート

B - Increment and Rotate

　解説AC。一応考えて分からず解説を見たのだけど、問題を誤読していた（先頭でなくても+1できる問題を考えていた）ことに気付いて愕然とした。

　また、解説の「～は有名問題で」の部分は理解できなかった。

　私は、解説のkを見つけて、B=（A[k:]+A[:k]）*2とした後、

・stackを使って、各index i に対して、j>iかつB[j]>=B[i]となる最小のjを見つける。（この配列をMAXINDと呼ぶことにする）

　とした。（これは有名問題っぽい。）

　これと累積和を使うと、x～x+Nにおけるmax($A_x$, $A_{x+1},..., $A_{x+N}$)の総和（解説で「以下の問題を解けばよいです」と書いてある部分）は、差分計算でO(N)になると思う。

　B[x]>B[x+1]のときの差分計算が一回で書けないけど、一回B[x]～B[MAXIND[x]]について足したものは二度と足されないので。

C - Not a Multiple of 3

　解説AC。
　同じ数字に注目すれば良いのか、なるほど。
時刻: 0 件のコメント:
ラベル:

2023年4月18日火曜日

Codeforces Round 863 (Div. 3)

　G1まで。と思ったが、FがHackされた。

コンテスト後のツイート


F. Is It Flower?

　全体の連結性のチェックが必要だった。
　さらに、実装ミスがあったのをTwitterで指摘してもらった。（ありがたかったです！）

G2. Vlad and the Nice Paths (hard version)

　解説AC。

　nice pathの長さがmaxのもののみを探すので、ツイートのDPのjは「そこまでのmaxとその一つ小さいもの」だけしか見なくて良い、ということを利用した。

　ただ、DPの値が0になるかをフラグに利用していたため、mod を取ったとき答えが0になる場合で引っかかってWAを出した。そこを修正してAC。
時刻: 0 件のコメント:
ラベル:

2023年4月17日月曜日

Codeforces Round 864 (Div. 2)

　Cまで三完。ARCの直後ということもあり、遅刻して今一つやる気が出ないままやっていたが、それとは関係なくDが分からなかった。

コンテスト後のツイート

D. Li Hua and Tree

　解法ツイートを見たら、愚直にやっても、三点更新くらいで済むのでできるらしい。
　このヒントを見てAC。

　ちゃんとクエリ2の様子を図に描いて観察すれば、子供の数も、子孫の重要度の和も高々三点しか更新されないことは分かったはず。これに気付かなかったのはやる気がなかったとしかいいようがない。反省。

　あとは実装問題。こちらは結構難しいし面倒くさい。

　heapqに（子孫の個数, index）を入れて管理したが結構制限時間ギリギリだったし、どんな情報を持ち、何を更新しなくてはいけないかも整理できておらずWAを出してしまった。
時刻: 0 件のコメント:
ラベル:

2023年4月15日土曜日

yukicoder contest 384

　Cまで三完。

コンテスト後のツイート

No.2270 T0空間

　愚直にやったらTLEした。解説にbit setを使うと書いてあったので、それでAC。

　bit set高速化は一回思いついたのだけど、なぜか違うと思って検証しなかった。もうちょっと掘り下げていれば解けたはずなので反省。
時刻: 0 件のコメント:
ラベル: ,

2023年4月13日木曜日

Educational Codeforces Round 146 (Rated for Div. 2)

　Cまで三完。unratedになったものの、普通にDもEも分かっていない。

E. Chain Chips

　コンテスト中、こういう問題はセグ木だよね……と思ったが何をセグ木に乗せれば良いか分からなかった。が、セグ木を使えばできるというツイートを見て、落ち着いて考えたら分かった。方針はあっていたのに、きちんと詰められないのはダメ。

　ただ、非可換のものをセグ木に乗せる実装が良く分からなくなったのは反省。非可換のときに対応できるライブラリになっていなかったのはまずい。セグ木に非可換のものを乗せたことはあったはずなのだけど、以前はどうやっていたのだろう？

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

2023年4月12日水曜日

AtCoder Beginner Contest 297

　Fが解けず。

コンテスト後のツイート

F - Minimum Bounding Box 2

　包除原理だという情報を得てAC。

　包除原理を使って、縦x横yの長方形となる場合の数を計算する……という方針を言われればそれほど難しくない。
　そして、H*Wの全探索をできる制約であることを考えれば、この方針はまあ自然か。

　コンテスト中は、縦・横を別々に考えようなどとしてしまい、全ての長方形を考えようとすら思わなかった。
　自然な方針を検討していないのはダメ。


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

2023年4月11日火曜日

Codeforces Round 865 (Div. 1)

　AB二完。

コンテスト後のツイート

C. Between

　具体例を考えたとき、色々間違えていた。
　n=3で、

2 1 3 2 2 3

　なら、2を二個にしたら3は一個にしなきゃいけないものと勘違い。これ、3は（二個どころか）三個おいても大丈夫だった。

・3 2 1 3 2 3

　で良い。

　n=3で、

2 1
3 1 3 2 2 3

　でも、

・2 3 1 2 3

　が最善。（2, 3の順番に注意。1の左右で同じ順番でなくてはならない。私は、左右で逆の順番にした方が良いと勘違いしていた）

　つまり、1からの距離だけ見ればOK。
　それさえ分かれば、1からの距離が偶数のものは、index 0, 2, 4, ...に割り振り、奇数のものはindex 1, 3, 5, ...に割り振る感じで構築できる。

D. XOR Counting

　解説AC。

　N=2以外のときは自明で、n=2のときは桁DPでできる、というような解法ツイートを読んだ。
　桁DPと言われてもぱっとは理解できなかったのだが、下の桁が1のときと0のときで場合分けを書いて見ると、桁で場合分けすれば再帰で計算できることは分かった。
　一番下の桁が0のとき、0,0と、1,1の二つに分かれるが、それらでは一つ上の桁が1変わってくる。なので、その二つで値がかぶることはないことから、場合分けして考えられる。

　ただ、その後の高速化ができず解説を見た。

　一気に再帰で計算しようとするのではなく、

・一番下の桁が1のとき、その桁に関するxorは1になるが、その値がどんな数字にかかってくるのか、個数を求める

　ものを再帰で書けば良かった。
時刻: 0 件のコメント:
ラベル: ,

AtCoder Regular Contest 159

　ABDの三完。

コンテスト後のツイート

C - Permutation Addition

　解説ツイートを見てAC。
　たとえば、

　1 2 3 4 5
　4 5 3 2 1

　のように操作すると、二つの要素を+1, -1と変化させられる。これに気付きませんでした。
　これを使うとあとは適当でも通った。
時刻: 0 件のコメント:
ラベル:

2023年4月8日土曜日

yukicoder contest 383

　Cまで三完でした。


No.2263 Perms

　解説AC。

　大きい方から貪欲に取ったりすればいけるのかな？→ダメ　フローを使う問題でした。
　言われてみればフローっぽい見た目なのに、全く思いつかなかったのは反省。

　この問題が類題だったらしい。解いていなかったので解いておこう。
　→解いた（解説AC）。フローを繰り返し使うというのは同じだが、どういう風にフローを使えば良いか分からず解説を見てしまった。どんなマッチングが欲しいかが分かれば良いので、落ち着いて考えればできそうなものなのだが、結構混乱してしまう。
時刻: 0 件のコメント:
ラベル: ,

2023年4月6日木曜日

AtCoder Beginner Contest 294

　Eまで五完。


F - Sugar Water 2

　解説AC。

　二分探索後の判定方法が分からず悩んでいたが、食塩水と同じで良かった。この問題をすぐ思い出したのに、判定方法が出てこなかっただけでなく、解説を見に行かなかったのは酷い。

G - Distance Queries on a Tree

　HLDとかオイラーツアーを使うのだろうと考えていたが、どちらでも解けたらしい。キーワードを思い付いているのに解けないのは良くない。

　随分昔に書いたHL分解のコードをもってきてAC。
　そのとき書いていたコードが頂点準拠なものなので、辺準拠に改造するのに戸惑った。

　自分のHL分解のライブラリが遅いのは分かっているので、それもどうにかしないとねぇ。
時刻: 0 件のコメント:
ラベル: ,

2023年4月5日水曜日

AtCoder Beginner Contest 295

　Fが解けず六完。

コンテスト後のツイート

F - substr = S

　桁DPでAC。

　桁DPで解けると知り自力で解こうとしたら非常に苦戦してしまった。下の桁からやったのだが、場合分けが難し過ぎる。（かといって、上の桁からやれば簡単とも思えない）
　愚直解を書いたり色々やり、一時間以上かけてどうにかAC。

　方針が分かってなおこれだけ苦労してしまったので、コンテスト中ACするのは困難だったか。桁DPになれれば速く解けるようになる可能性はあるのかなぁ……。

Ex - E or m

　解説放送を見てAC。

　DPだろうとは思えるが、どういうDPなのか気付くのが難しい問題。
　ただ今回は、左上から順に埋めていくという自然な解法で解けるので、自力で思いつかなくてはいけない範囲だったような……。
時刻: 0 件のコメント:
ラベル:

2023年4月4日火曜日

MC Digital プログラミングコンテスト2023（AtCoder Heuristic Contest 019）

 pretest50位→システムテストは49位。序盤に思いついたことを実装していっただけで、後に発想できたことがほとんどなかったため、あまり手応えはなかったけれど、順位はまあまあ良かった。手応えがあっても全然順位が伸びないこともあるので、それに比べれば良いか。
　以下は、大体ツイートのまとめです。

コンテスト後のツイート

　基本的な方針はビームサーチ。

　一番目のシルエット用に使っていない頂点(x1,y1,z1)と二番目のシルエット用に使っていない頂点(x2,y2,z2)と、回転方向directionを決めて、できるだけ大きくブロックを拡大させる……というのを一操作としたビームサーチ。
　あとは、一部のブロックと周囲のブロックを壊す操作を入れました。

・評価値は使えていないシルエットの頂点+Σ1/今までおいたブロックにの大きさ
・使う頂点は、シルエットで使っていない&角に近いもの優先（片方を1個、もう片方を5個採用。これが一番得点が高かった）
・方角は全24通り試しています。

　その中で評価値が良いものを最大850個（これがビーム幅？）採用しています。ビームサーチ（っぽいの）はじめて書いたので、語句とか間違っていたらすみません。最初（Pythonで書いていたとき）はもっとビームサーチしてたと思う（？）んだけど、時間使い切るならchokudaiサーチが良いって読んで、chokudaiサーチっぽい要素も取り入れました。

　この方法だと、二頂点を選んだ後、最大まで膨らませないときが最適だったときのケアができていないけど、どうすれば良いか分からず断念。
　焼き鈍しはしてみたかったけど、できた盤面から変化させる方法が分かりませんでした。

　結構序盤で探索ゲーだと思ったのですが、とりあえずPythonで書いてRustに直しました。書き直して結構順位が上がったのが嬉しかった。本質ではない（と思っている）パラメータを1変化させるだけでスコアが大きく変化するのが謎でした。

　PythonからRustへ書き換える際には、ChatGPTにお世話になりました。書きたい大まかな内容をPythonで書いて、「このPythonのコードをRustに直して」みたいな聞き方を何度もしていました。適切な答えが返ってくることが多かった。
　さらに、文法が分からないとき丁寧に解説してもらい、凄くありがたかったです。
時刻: 0 件のコメント:
ラベル:

Codeforces Round 862 (Div. 2)

　Cまで三完。Dで全方位木DPを使おうとしたら分からなくなって混乱していた。

コンテスト後のツイート

D. A Wide, Wide Graph

　全方位木DPでAC。復習になった。（結局、以前の自分の実装を元に書き直した）

　今の自分の実装（カッコ内は自分の実装での命名）では、

・単位元（unit）
・子たちの値をmergeするときの関数（compose_calc）
・子たちから計算した値からそのnodeについての値を出す関数（final_ans）
・子たちが存在しないときに入れておく値（no_composed_value）

　を決めれば答えが求まるようになっていると思う。多分、mergeの可換性も必要……というか、可換じゃない場合の求め方を理解できていない気がする。
　ただこの実装、四つ目が気持ち悪いねぇ……。なんとかしたい。


　全方位木DPが分かりにくいと思うのは、私が、「ある頂点に関する部分木に関するDP」ではなく、「辺に関するDP」だと思っているせいが大きい。

　私の実装では、UP[x], DOWN[x]で、「xとxの親を結ぶ辺」について、それぞれ、「子から親方向に見たときのDPの値」「親から子方向に見たときのDPの値」と考えている。
　ただ、これだとDOWN[x]の値が直感と一個ずれる（その親に関する部分木を考えているため）んだよね。だけど、一個ずらしてDPテーブルを定義したらもっと（自分には）もっと分かりにくくなってしまった。

　このあたりが毎回混乱の原因になっています。





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

2023年4月2日日曜日

AtCoder Beginner Contest 296

　Dを飛ばしてFまで五完。Dが分からず、頭が働いていないなぁと思い、AHCの途中だったこともあって途中で諦めてしまった。


D - M<=ab

　解説AC。

　aを√Mまで探索すれば良いという問題。
実は範囲が狭いため、何かを全探索できる……という系統だと思ったが、考察が進まなかった。

G - Polygon and Points

　解説AC。コンテスト中は凸包を作って、その後どうしよう……などと考えていたが、元から反時計回りに頂点が与えられているので凸包は関係ないですね。

　解説の通り、xでソートして平面走査した。
　ただ、y軸に並行な直線に関する処理でWAを量産。結局、最初にy軸に並行な線分を列挙して例外処理することでACできた。

Ex - Unite

　苦戦したが一応自力でAC。

　この問題の類題で、Union-findの状態を持ってDPすれば良い。ただ、先に挙げた問題より制約が厳しく制限時間も厳しいため、自分の書き方だとなかなかTLEが取れなかった。

　Union-findの配列をencodeするなど普通の工夫の他に、

・次の行を見る際、DPの値が（今までの最低値）+6以上だったら使わない

　という正当性の怪しい枝狩りを入れたら通った。
時刻: 0 件のコメント:
ラベル:

2023年4月1日土曜日

yukicoder April Fool Contest 2023

　AB二完。 


No.3100 始業式

　解説AC。

　先生の存在には気付いていたが、「嘘の報告」をするとは考えなかった。
　あと、解説を見た後も、「クラスで何人が春休み中に勉強したか」の何人の中に先生も含まれるんじゃないかと思って混乱してしまった。

No.3101 砂嵐

　解説AC。

　画像の分析を試みるのは良いけど、その後、何すれば良いかは難しい。解ける気がしない。

No.3103 Range Chmax and Maximize Abs Sum

　解説AC。

　元の問題の解き方が分かっていない。

　

No.3104 黒に近い、黒

　解説AC。

　oeisだとは思ったが、その後の考察は難しいなぁ。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)