2022年12月28日水曜日

Codeforces Round #841 (Div. 2) and Divide by Zero 2022

　Cまで三完。Eは通したかった。

コンテスト後のツイート

D. Valiant's New Map

　二次元Sparse table（か、二次元セグメント木）でやるしかないと思ってコンテスト中書いたがWA。
　クエリ計算のところで、二点のminではなく、四点のminを取るよう修正したらMLEになりました。

　昔、二次元Sparse tableを書いたときそれだけで数時間かかったことを思えば成長。一旦Sparse tableを取ったあと、そのそれぞれの要素についてもう一度Sparse tableを取ると考えたら、それほど詰まらずに書けました。このままライブラリ化しても良いかも？
　この感じなら、二次元セグメント木も書けそうな気がしてきました。

　ただ、この問題はそういうデータ構造を使わなくても解ける問題でした。毎回二次元累積和を取る解法でAC。

E. Graph Cost

　約数包除くでgcdの個数を列挙した後、大きい方から貪欲にやればOK。
　という解法は分かっていたけど、約数包除の実装でミス。時間がなかったので、ベン図など書かずにこんなものかな、と実装したらダメ。ちゃんと図を描いたら解けました。
　
時刻: 0 件のコメント:
ラベル: ,

2022年12月25日日曜日

ユニークビジョンプログラミングコンテスト2022 冬(AtCoder Beginner Contest 283)

　E飛ばしてGまで六完。Eも最後に解法を思い付いたので、解きたかったね。

コンテスト後のツイート

E - Don't Isolate Elements

　自力AC。

　終了一分前くらいに、上の二行の表裏を管理してDPすれば良いと気付いた。結構実装の大変な問題なので、コンテスト中にACするのは厳しかったかも。
時刻: 0 件のコメント:
ラベル:

2022年12月23日金曜日

HHKBプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 282)

 　Fまで六完。

コンテスト後のツイート

　ツイートの「スライド最小値」は「Sparse table」の間違いです。

G - Similar Permutation

　解説AC。

　コンテスト中に、この問題の解説を見直し、同じようなDPをするしかないな、と思い、それを累積和か何かで高速化するんだろう、とは思った。
　ただ、高速化の方針が分からず、とりあえず計算量を無視して書いてみたが答えが合わず終了。

　答えが合わなかったのは添え字のミスで、自分のコードを見れば二次元累積和を使えることは分かった。考えていたときは、それでも計算量五乗になってしまい間に合わないと思っていたが、（解説および）自分のコードを見たら四乗にできることが分かった。

　正しい方針を思い付いているのだから、解き切らないと。

Ex - Min + Sum

　解説放送を見てAC。

　Cartesian Treeという単語は知らなかったけれど自然な解法ですね。計算量解析の部分はちょっと難しいですが。

　ただ、Cartesian Treeを使って分割統治する方針だと自分の実装だと通らず、

import pypyjit
pypyjit.set_param('max_unroll_recursion=-1')

　というおまじないを書いて通りました。この高速化を書いたの初めてです。
時刻: 0 件のコメント:
ラベル:

Codeforces Round #834 (Div. 3)

　Eまで五完。


F. All Possible Digits

　自力AC。

　少なくとも、p以内に答えが見つかる（１の位が一周するので）。今までに使った数字を範囲の形で持てば、全ての数字を使っているかをチェックすることはできる。
　ケアすべきは、「最初」「１の位が使われていない最大値に到達したとき」「繰り上がったとき」「繰り上がった後、１の位が使われていない最大値に到達したとき」。これらを実装すれば良い。

　コンテスト中は、パッと見て桁DPとか思って飛ばした記憶があるのだけど。全然違った。

G. Restore the Permutation

　自力AC。

　「小さい数字をできるだけ前に置く」という方針で考えたくなるがそれだと上手くいかず（この方針でも可能だと思うけど、実装の仕方が分からなかった）、「大きい数字をできるだけ後ろに置く」という方針を取ると簡単だった。

　小さい方から考えて上手くいかないなら大きい方からも考えてみよう、と思わなくてはいけませんね。
時刻: 0 件のコメント:
ラベル:

2022年12月20日火曜日

Codeforces Round #840 (Div. 2) and Enigma 2022 - Cybros LNMIIT

 　ABDの三完。Cを飛ばしたのは正解だったけど、Eを解き切れなかったのは良くない。

コンテスト後のツイート

C. Another Array Problem

　同じ隣接2マスに二回操作を行うと両方とも0になることを利用すると、配列の長さが4以上なら全体を最大値にすることができる……と気付けるかどうか。

　愚直を書けば気付けたかと思ったけど、愚直を書いたつもりで「同じところは二回やらない」みたいな実装にするとダメ。結構ハマりやすいかも。

E. Node Pairs

　たくさんWAを出したけど一応自力でAC。

　ツイートで方針はあっているけど、頂点数2だけでなく、もっと頂点数が多い完全グラフも複数回使うことがあるので、個数制限のないナップザック問題のようにして解けばOK。

　最初、頂点数の多い完全グラフから貪欲に使っていけば良いのでは？　と考えたため、大体一回ずつしか使わないという考えから抜けられなかったのがまずかった。

　
時刻: 0 件のコメント:

Codeforces Round #839 (Div. 3)

　全完。結構時間はかかったけど、まずまずの出来か。

コンテスト後のツイート


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

2022年12月14日水曜日

Codeforces Round #837 (Div. 2)

　Cまで三完。


D. Hossam and (sub-)palindromic tree

　解法ツイートを見てAC。

・二頂点i, jに対して、DP[i][j]=頂点iと頂点jを端点としたときの最大スコア

　として、頂点iとjの距離が小さい方から更新していけば良い。遷移も二乗で収まる。

　ただ、実装の仕方が悪いのか、PyPyでは通せず、Rustでも制限時間ギリギリの時間になってしまった。
時刻: 0 件のコメント:
ラベル:

2022年12月12日月曜日

デンソークリエイトプログラミングコンテスト2022 Winter(AtCoder Beginner Contest 280)

　Fまで六完。

コンテスト後のツイート

E - Critical Hit

　ACはできたけど期待値DPで立式できなかったのは反省。
　最初DPで解こうとしたのに、DP[i]=i回で倒せる確率　とか考えたせいもあって立式できなかった。

・DP[i]=体力iからの攻撃回数の期待値

　とするとよかったようだ。最初の攻撃がクリティカルかどうかで場合分けして立式することができる。

G - Do Use Hexagon Grid 2

　解説放送を見てAC。

　x, y, x-yを管理すれば二次元でマンハッタン距離を考えたときと同様にできることは分かったが、二次元のバージョンがそもそも分からなかった。

　「x座標の下限、y座標の下限」を固定して考えるのだけど、そのとき、下限上にある代表点を決めれば重複なく数えられる、というのがポイントか。
　これで重複なく数えられるというのは気付きにくかった。

　なお、実装も大変。
時刻: 0 件のコメント:
ラベル: ,

2022年12月11日日曜日

yukicoder contest 369

　Bまで二完。


No.2132 1 or X Game

　解説AC。

　二連続で「-X」を行えないというルールのため、愚直を書くのが面倒くさい。かといって、自力で周期を導出するのはなかなか大変。
　また、周期が分かっても意外と実装しにくく答えを合わせるのが大変。

　だから、難問とは言えないかもしれないけど、ACしにくい問題に思えるのだけど……。

No.2134 σ-algebra over Finite Set

　解説AC。

　集合の「かつ」「または」「補集合」という演算について閉じているので、それらに関して独立な要素の個数を数えて、その2ベキが答えになることは分かった。
　が、要素の個数の求め方で迷走してしまった。（xorの掃き出し法とか使えるのかと）

　実際は、各要素について、それを含むような最小の集合を求めれば良い。それらの個数を数えればOK。
　言われてみれば難しくないけど、線形独立性と混乱したのが敗因。
時刻: 0 件のコメント:
ラベル:

2022年12月10日土曜日

AtCoder Beginner Contest 281

　Fまで六完。

コンテスト後のツイート

G - Farthest City

　解説AC。

　頂点1に距離が近い頂点から決めていくDP。

・DP[rest][last]で、決めていない頂点がrest個で、最後に決めた（今までに決めた中で距離が最も長いもの）の頂点の個数がlast個であるようなものの個数

　とすると遷移が求められる。

　そういうDPだと言われれば解けるけど、コンテスト中は何をすれば良いか分からなかった。

　制約からDPを疑うのは自然で、DPしようと思うなら、1から近い距離の頂点から決めようと思うのは自然。そう考えれば、自然な解法のはずなのだが。
時刻: 0 件のコメント:
ラベル:

yukicoder contest 371 (Asakatsu Presents)

　Dまで四完。


No.2157 崖

　自力ACだけど時間がかかった。

　普通に考えると三乗のDPになるけれど、それをどうやって高速化するか、という問題。

　まず、各D[i]をソートしておき、

・DP[i][j]=D[i][j]を使うときの、最小のfの値

　としたとき、

・DP[i][j]のままいけるのは、D[i+1]の値が、D[i][j]以上D[i][j]+DP[i][j]以下のとき
・それ以降は、D[i]の差に従って増えていく

　なので、前者を（双対）セグ木を使って更新。後者は別の配列を用意して求めた。


　実装大変だった割にたくさん解かれているなぁ、と思ったら、答えで二分探索すれば実装が楽だった模様。答えで二分探索は最初考えたけれど、なぜかできない気がしてやめてしまった。
時刻: 0 件のコメント:
ラベル:

AtCoder Grand Contest 059

　B一完でした。

コンテスト後のツイート

A - My Last ABC Problem

　（ツイッターで検索した範囲では）他に誰もしていない誤考察をしていた。「二色の連続部分列があれば、その二色のうちどちらか一色へ一手で変えられる」という。はっきり間違いですね。
　これに基づいた愚直解法を書いていたので、合うわけがない。

　愚直を書くときは、変な考察を交えず、本当に愚直になっているか確かめるべき、というのが教訓かなぁ。しかし、実際のところは、初手でこういう勘違いをしてしまうと、コンテスト中に気付くのは難しい気もする。

　正しい解法は、色が切り替わる箇所を二つずつ減らせる、というもの。端点についての考察は必要だけど、直感だけでいったら初手これを考えるだろう（解けなかった人でもこれを考えた人は多いはず）、というものでした。
時刻: 0 件のコメント:
ラベル:

2022年12月6日火曜日

yukicoder contest 368

 A一完でした。


No.2125 Inverse Sum

　解説AC。

　整数問題なので因数分解して右辺を定数（今回なら、N, Mを含まないP, Qのみの式）にしたくなる気持ちは分かる。
　因数分解の難易度が結構高い気がするけど、大学受験数学で十分出題されうるものか。

No.2126 MEX Game

　これは自力AC。

　後手は、Aにxが一個だけあり、MEXがxより大きいとき、それを別の数にすることで、MEXをそこまで減らせる。
　逆に、先手としては、0, 1, 2, ...がずっと複数個存在するような操作をすれば良い。
時刻: 0 件のコメント:
ラベル:

2022年12月2日金曜日

yukicoder contest 370

　Dまで。

コンテスト後のツイート

No.2144 MM

　解説AC。

　一個おきの階差が+1, -1されるんだなぁ、というところから考察が進まず。
　交代和、もしくは偶数項・奇数項の総和を考えれば良かったのですね。一項おきの何かに注目するという着眼はあったのだから、もっとそこを追及しなくてはいけなかった。

　その後の解説の方法は綺麗だけど思いつくのは難しそう。DPでも解けるらしいので、そちらの方が現実的か。
時刻: 0 件のコメント:
ラベル:

2022年12月1日木曜日

Codeforces Round #836 (Div. 2)

 　遅刻してA一完。Bでハマってしまった。


B. XOR = Average

　nが奇数のときは[1]*nで良い。
　コンテスト中20分以上考えたが、nが偶数のときを思いつかなかった。最後の二要素で辻褄合わせをする……みたいな方針を考えたが上手くいかなかった。

　結論からいうと、[1,3]の後に[2]を続ければ良い。

　二要素で条件を満たすものがあれば、後にずっとその値を続ければ良いですね。言われてみれば当たり前。

E. Tick, Tock

　解説ツイートなどを見てAC。

・矛盾するかの判定→重み付きUnion-findで行、列ごとに管理
・答えを求める部分→A[i][j]が-1なら行iと列jをUnionして、連結成分数を見る。全体の連結成分が1よりいくつ大きいかを求めて、hをそのベキ乗したのが答え

　とした。

　矛盾するかの判定は自分で考えたこともあり、二度手間になっている気がするけどもっと楽にできるのかな？　よく分かっていない。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)