2021年11月30日火曜日

AtCoder Beginner Contest 223

　Fまで六完。

コンテスト後のツイート

G - Vertex Deletion

　解説放送を見てAC。
　全方位木DPで書いたけど、理解するのにも実装にも非常に苦労してしまった。全方位木DP自体は理解しているつもりだったけど、遷移式が分かりにくいだけで非常に戸惑った。
　ライブラリとはいえないけど、一応、以前に比べると書きやすい形にまとめた。（次回、全方位木DPを書くときはここで書いたものを元にしよう）
時刻: 0 件のコメント:
ラベル: ,

2021年11月29日月曜日

Deltix Round, Autumn 2021 (open for everyone, rated, Div. 1 + Div. 2)

　Eまで五完。Eに手間取り過ぎた……。

コンテスト後のツイート

　F以降を解かなそうな気がするので、ツイートだけだけど記事を公開。Eは類題経験が生きたといえなくはないんだけど、もっとすんなり通したかった。

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

2021年11月27日土曜日

Codeforces Round #757 (Div. 2)

　D1まで四完。

コンテスト後のツイート

D2. Divan and Kostomuksha (hard version)

　やり方はD1と同じ。（自分のツイートだけじゃ解法を理解するのは無理だろうけど、今回は省略）

　問題は約数列挙を高速にできるか？　というところ。
　エラトステネスの篩を使えば高速にできるだろう、とは思っていたけど、良い書き方が分かっておらず、一旦素因数分解してから約数を求めるという二度手間で書いていた。

　実際は、素因数分解を経由せずに書けて、その方が速い（その書き方に気付いておらず、他の方の提出を見て気付いた）。そのように書き直したらPyPyでもACできた。
時刻: 0 件のコメント:
ラベル: ,

2021年11月24日水曜日

AtCoder Beginner Contest 226

　Eまで五完。

コンテスト後のツイート

F - Score of Permutations

　解説放送を聞いてAC。

　i=P[i]となったらそこでボールが止まると誤読していた。ツイッター上で同じ誤読をしている人を散見したが、とはいえ良くない。最初誤読しても、Sample3の答えが合わなかったところで気付くべきでした。

　というわけでoeisを使うにしても、これではなく、こっちだったよう。

　ただ、本番は埋め込みしようとしていたわけなので、その後のDPによる処理が分かっていなかったのもまずい。

　DP[i][j]で、i人まで決まって、そこまでのlcmがjのときの場合の数、とする。遷移は、「まだどのグループにも属していない添え字最初の人がどのグループに入るか？」を考えることで求められる。

　これは、重複なく数え上げるときの典型手法の一つ。実験→埋め込みにいってしまったためまともに考えなかったせいもあるかもしれないが、思いつけなかったのはダメ。ちゃんと身に着けておきたい。

G - The baggage

　解説AC。Gに置かれているから難しそうだけど、CやDあたりに置かれていたらたくさん解かれていそう。
時刻: 0 件のコメント:
ラベル: ,

Codeforces Global Round 17

　Dまで四完。Eが解けなかったのは、Dで苦戦して頭が働かなかったため、という気もする。

コンテスト後のツイート


E. AmShZ and G.O.A.T.

　三個がterribleな場合に帰着されそうというのはそうなのだけど、そこから考察を進められなかった。

　badじゃない数列を構築していこう、と考えれば良かった。

　a, b, c （a<b<c）がbadじゃないとする。さらにd（>c）を付け加えたいなら、a, c, dの三つがterribleになってはいけないので、d-cがc-a以上にならなくてはいけない。なので、構築できる数列のサイズはlogで抑えられるので、計算量も大きくならない。

　これで十分条件も満たしている、というのに気付いていなかったのがマズかった。四個以上の数列がbadになるとき、terribleな三個の数列ができそうだけど、できるならどこにできるのだろう？　という考察ができていなかった。これは気付けなきゃいけなかったなぁ……。

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

2021年11月23日火曜日

AtCoder Regular Contest 129

　Cまで三完。

コンテスト後のツイート


D - -1+2-1

　解説放送を聞いてAC。
　一時間考えていたけど、累積和なんて全く思い浮かばなかった。（階差は考えたが……）

　累積和を取るということが思い浮かべば、「初項に+2」「末尾の項に+2」以外の全ての操作は、累積和を一つ後ろの項へわたすような操作と分かる。なので、

・累積和の和が0になるよう、「初項に+2」「末尾の項に+2」により調整。
・あとは、「初項に+2」と「末尾の項に+2」は同じ回数ずつ使う。実際に操作が行えるよう、これらの操作回数を二分探索で決定（解説では二分探索していないが二分探索でも解ける）

　とすれば良い。

　なので、「累積和を取る」というのをどう思いつくのかが大事だろう。これは、

・「総和は変わらない」「数列が円環じゃない場合は簡単だから端の操作を特別視できそう」

　といったあたりから気付けなくてはいけなかったのだろうと思う。

　このあたりにギャップを感じるなら、maroonさんの公式解説の方が良いのかな……。こちらだと、操作で$i$を選んだ回数を$a_i$として立式することで、まあまあ自然に解法へと辿り着いているから。とはいえ、式を見たときこの考察へたどりつくのは簡単ではないな……。
時刻: 0 件のコメント:
ラベル:

2021年11月6日土曜日

yukicoder contest 321

　ABの二完。C思いつかなかったのは大いに反省。


No.1730 GCD on Blackboard in yukicoder

　各A_iの約数を列挙できたら解けるな……と思い、エラトステネスの篩（に似た方法）で約数列挙を高速にするやつを使って通した。
　解説を見ると、エラトステネスの篩（に似た方法）を使うのは同じだが、約数列挙までする必要はなかったみたい。頭が固い。

No.1731 Product of Subsequence

　解説AC。
　Kの約数を使うだろうな、とは思ったのにDPを思いつかなかった。
　さらに、DPの遷移式を立てるとき、gcdを使うことを思いつかなかった。

　反省しかないけど、こういう、頭が働いているときなら思いつけたはず……って内容を思い付けなかったときって、具体的な反省をし辛い気がする。
時刻: 0 件のコメント:
ラベル:

2021年11月5日金曜日

技術室奥プログラミングコンテスト#6 Day2

　A一完で終わってしまった。そこそこ解かれている問題はACしたい。


B - Replace to the Other

　この前のAGCの問題の類題ということで見てみた。
　確かに類題なのだが、これを思い付くのも厳しい……。結局解説を見てしまった。

　「同じ文字達を変える」方が分かりやすいのに、その逆を考えねばならないのですね……。

C - Strange Paper

　これは実験一択でした。
　Nが8くらいまでは実験でき、それくらいまで実験したら答えに気付けそうです。ただ、N=6で解がないのがちょっと意外か。全探索じゃなくて、乱択で答えを求める実装をしたため、解がない場合に気付かずちょっと困りました。

D - NG Word Game

　解説を読んでもよく分からなかったけれど、このツイートを見てAC。"01"*Nは考えたんだけど、端から調べていってOKっていうのがパッと分からずつまった。
時刻: 0 件のコメント:
ラベル:

2021年11月4日木曜日

AtCoder Regular Contest 126

　AB二完で終了。悲しい。


C - Maximize GCD

　解説AC。

　Aの要素全てをmax(A)に揃えられるほどKが大きいときはOK。
　問題は、そうできないとき。
　普通に考えると、gcdをxにできるかどうか、の判定にはO(N)かかる。なので、gcdの候補をどうやって絞っていくかが問題。だけど、どう絞れば良いのだろう……？

　……と考えてハマってしまった。

　実際は、「gcdをxにできるかどうかの判定」の計算量を減らせる。

　あるxに対して、kxより大きく(k+1)x以下の範囲にあるものは全て(k+1)xにする。なので、「その範囲に何個あるか」「その範囲の総和」が分かれば良い。
　それらを予め求めておくことで、各xについて、O(max(N)/x)になり、（調和級数の）logの計算量で求められる。

　コンテスト中、「gcdをxにできるかどうかの判定」の計算量が本当にO(N)必要なのか？　を疑問に思った時間は確かにあった。だけど、gcdの候補の方が絞れそうな気がしたので、真面目に考えずに終わってしまった。

　候補を絞るのが難しそうと思ったときに計算量を減らせないか検討すべきだったんだろうけど、飛ばしてDへ行こうと思ってしまった（飛ばしたこと自体は悪いことではないけど）。
　まあ確かに、max(A)とかから候補を絞るのはいかにも嘘っぽいので、計算量削減を考える方が筋は良いんですよね。

D - Pure Straight

　（解説通りの方法ではないけど）解説AC。

　解説の「使う項と部分列の位置を固定した場合」の部分が非常に重要だと思う。コンテスト中、一応正しいことを考えてはいたようだけれど、答えは「転倒数＋何か」になるはずとは思ったけれど、「何か」の部分があやふやだった。

　あとは、区切り位置を決め、「その前の部分からどの数字を取ってきて、その後ろの部分からどの数字を取ってくるか？」をbit全探索すれば計算量は悪いが答えが求まる。自分の書き方だと定数倍がきついため、bit全探索の部分を枝狩り（区切りの直前の数字は必ず前におく、など）してAC。
時刻: 0 件のコメント:
ラベル:

2021年11月3日水曜日

AtCoder Regular Contest 127

　AB二完でレートを落とす。

　コンテスト終盤、Eのサンプルが合い、舞い上がって提出したときREが二個返ってきて、焦りに焦ってしまった（指が震え、汗がたくさん）。そのせいで結局通せず。
　こういう時間ギリギリのやつは、最終的にはACできていたことが多いのに、今回は失敗してしまった。まあ、最初二問で時間かかってしまったのもまずいんだけど……。


C - Binary Strings

　解説AC。

　大体、Xが全体の半分以上か以下かで、最初の文字が分かりそうだなー、とは思う。
　その解法であっているのだけど、詰めるのはなかなか大変。
　特に、Xが2進法で与えられるということを活用する部分は難しい。

　実装にも苦労した。
　解説通りに実装したつもりだったが、X=0になったかどうかの判定の仕方が分からず困ってしまった。
　立っているbitの個数を持つという方法に気付きどうにかAC。

D - Sum of Min of Xor

　解説AC。
　なかなか解説が理解できず苦労したが分かってしまえば単純だった。

　xorの問題だし、制約を見ても、桁ごとに考えるのが良さそう。
　最上位の桁について、ABそれぞれのbitが立っている/立っていないの四通りで場合分けできる。それを00、01、10、11の四つで表すことにする。たとえば、Aでビットが立っていて、Bで立っていない場合10で表す。

　この四通りの、何と何でxorを取るかで場合分けして考える。

　この桁で決着がつかないのは、00^00、00^11、11^11、01^01、01^10、10^10のとき。このときは、一つ下の桁を見る再帰を使いたい。このままだと再帰できないようだが、公式解説のように、S=00+11、T=01+10とすると、S内、T内で再帰することができる。

　それ以外、この桁で決着がついた場合は、一番下の桁からこの桁まで、それぞれの桁についてbitが立っているものの個数を調べておけばよい。
　たとえば、01^11ならAの方がBより小さいので、（01のもののうちk桁でAのbitが立っているものの個数）*（01のもののうちk桁でAのbitが立っていないものの個数）+（01のもののうちk桁でAのbitが立っていないものの個数）*（01のもののうちk桁でAのbitが立っているものの個数）に1<<kをかけたもののを加えれば良い。

　個人的には、この、「ある桁で決着がついた場合の処理」では全部の桁を見るというのが分かりづらかった。確かに、そうしても計算量は間に合うのだけど、他では再帰で一桁ずつ見ていくのにこっちでは下の全桁を見て処理するというのは分かりにくい気がする。
時刻: 0 件のコメント:
ラベル:

2021年11月2日火曜日

AtCoder Grand Contest 055

　一問もACできず終了。残り30分ほどでBの解法が分かり、実装、提出してみたがTLE。その後、TLE解消方法に気付くも実装でミスってWAのまま終了。レートは落ちたけど、noSubしなかったのは良かったかなぁ……。


A - ABC Identity

　解法ツイートなどは見たけど、概ね自力でAC。

　文字列を三つに分ける、という解法はコンテスト中から考えていた。最初の1/3のうち、文字数が一番多いものを取ったらどうだろう……いや、それはできないか、などと考えていた。

　大体の気持ちはそれで良いのだが、「一ヶ所の文字数を0にしよう」と考えるのがポイント。

　三か所に分けていて、一ヶ所にAとBとCが含まれるので、計９個消さなくてはいけないが、ある箇所の文字数が0個になったとき、他の二か所も同じ文字数ずつ減ることを考えると、一ヶ所が一文字のみになったとき、他の二か所はその文字以外の二文字以下になっており、あとは二回で全て消せる。
　そこまでは高々四回（＊）で消せるので、これで六回以下になる。

　……ところで、実験するとこれで五回になっているみたい。
　確かにそうなりそうだけれど、証明できない。

B - ABC Supremacy

　ABCを0, 1, 2で置き換え、(S[i] - i) mod 3で考えれば分かりやすい！　と思いついたのは、コンテスト二時間以上経過してから。それも、この問題（類題かと思って見にいったがあまり似ていなかった）の解説の一行目に、「まず入力から1を引きます」と書いてあったため思いつけた模様。

　その後、同じ数字三つ（つまり、元の問題の"ABC", "BCA", "CAB"）は自由に移動できると気付き、残ったものが一致するかどうかで判定すれば良いと気付いたのが30分前あたり。

　そこからコードを書き、ランダムテストし、提出した……が、TLE。

　ちゃんと計算量を見積もっていなかったのですね。焦っていたせいか、なぜか計算量は大丈夫という気持ちになっていました。
　定数倍効率化するコードをいくつか投げ、その後ようやくどういうとき二乗になるかに気付く。これはdequeを使えば計算量改善できる、と気付いたのは終了五分ちょっと前。

　時間が足りないか、と思いつつ書き直して提出したがWA。直せず終了。

　同じ処理を二回やっていたのだけど、二回目のところで初期化忘れをしていたためWAが出ていた……と気付いたのはコンテスト終了後に冷静になってからでした。
時刻: 0 件のコメント:
ラベル:
登録: 投稿 (Atom)