2023年5月25日木曜日

yukicoder contest 348 Early Summer Rain

　ACの二完。


No.1980 [Cherry 4th Tune D] 停止距離

　自力AC。

　二分探索するだけの問題だが、問題文を読み解くのがやや大変。解説では誤差を気にした方が良いと書いてあるが、気にしなくても通ってしまった。
時刻: 0 件のコメント:
ラベル:

2023年5月24日水曜日

トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)

　Fまで六完。コンテスト後50秒でGが通った。また、Fはafter contestのcaseで落ちた。

コンテスト後のツイート

F - Merge Set

　見直したら解法自体はあっていてほっとした。

　初期状態で1を含む集合がたくさんあったとき、それらの要素を全て初期状態に放り込み、重複をなくすことを忘れていたのがafter contestで落ちた原因だった。

　コンテスト中でTLEが返ってきたらどうだったろうか。解法自体はあっているので気付けばすぐ修正できただろうが、すぐ気付けたかは分からない。
　

Ex - Ball Collector 

　解説放送を見てAC。

　こういう問題でグラフへ帰着するのはよくあるのに、思いつかなかったのは反省。
　Roll-back付きUnion-findが思ったより簡単に書けることは勉強になった。

　なお、再帰で書いたらTLEしたため非再帰に書き直した。
　こういうdfsで帰りがけに処理をするのを非再帰でどう書けばいいか分からない部分があったのだが、その書き方が分かったのも良かった。
時刻: 0 件のコメント:
ラベル: ,

2023年5月23日火曜日

Codeforces Round 870 (Div. 2)

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

コンテスト後のツイート

D. Running Miles

　システムテストで落ちたのは、B[i]+iが同じならindexが大きい方から優先して調べるべき、ってところを考慮してなかったためでした。そこを修正してAC。

E. Walk the Runway

　bitsetを使うと聞いてもピンと来なかったが、こたつがめさんの実況放送の振り返りを聞いたら理解できた。

　ただ、Python通常のbitset（普通の整数をbitsetとして使う）では通らず、64個ずつに分けて、0～(1<<63)の数字の配列をbitsetとして使ったらACできた。

　この方法、書いたことなかったので勉強になった。面倒かと思ったけれど、意外と実装するのは簡単だった。
時刻: 0 件のコメント:
ラベル: ,

2023年5月22日月曜日

yukicoder contest 282

　ABの二完でした。


No.1391 ±1 Abs Sum

　解説AC。

・$x=A_i$のいずれかで最小値を取る
・$B_j=1$とすべきのは連続な区間で、Lを変化させたときは連続的に（つまり、凸に）変化しそう。

　なので、三分探索によりACした。

　ただ、そもそも、xとLを決めたときの答えは累積和を使えばO(1)で求まることに気付いていなかった気がする。そこは押さえた上で考えないと。



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

AtCoder Grand Contest 062

　A一完。

コンテスト後のツイート


B - Split and Insert

　解説AC。公式解説は理解できず、こたつがめさんの実況放送の振り返りで理解した。区間に分割していけば良いというのはなるほどです。

　また、類題（もしくは、この問題の簡単なバージョン）も解いたが、確かに類題ではあるものの、今回のAGCの問題には結構なギャップがある気がした。

　いや、今回のコンテスト中に、最小回数だけならlog2の何か（具体的には分からなかった）になるとか、マージソートっぽく再帰していく感じだな……とは思っており、最小回数を求める問題（つまり、この類題）であったなら後一歩のところまで来ていたと思う。

　だが、最小回数の導出方法が分かってもコスト計算をどうすれば良いかは見当も付かず、解説などを見てようやく理解できた……という感じだった。

C - Mex of Subset Sum

　区間で管理すれば通るという情報を得てAC。

　計算量の証明はよく分かっていないけれど、区間で管理するというのは思いつきたかった。コンテスト中、部分和問題だからDPしかないと思い、それを高速化する方法を考えていたのだから、ねぇ。
時刻: 0 件のコメント:
ラベル: ,

2023年5月21日日曜日

Educational Codeforces Round 148 (Rated for Div. 2)

　D1までと思ったら、D1がhackされてしまった。

コンテスト後のツイート

D1. Red-Blue Operations (Easy Version)

　二分探索の下限を小さくしたらAC。

　答えが負になる場合があると気付いていなかった。たとえばn=1の場合を考えると分かりやすいけれど、値は大きくなったり小さくなったりを繰り返すので、負になることもある。二分探索するとき、上限・下限の見積もりは気を付けよう。

　（この方針ではD2は解けなそう）

E. Combinatorics Problem

　解説AC。

　k=1のときの配列Bは、累積和を使えば求められる。
　kを明示的に表すことにし、b[i]をb(i, k)と表すことにすると、二項係数の性質から、b(i, k) = b(i-1, k-1) + b(i-1, k)となる。これを使えば解ける。

・k=1のときは配列Bを求められそうなので、実験してみる
・kが5以下という制約を利用することを考えると、k-1からkの場合が求められそう

　みたいな流れで解くのが理想的だったのかな。まず実験すべきでした。
　
時刻: 0 件のコメント:
ラベル:

2023年5月20日土曜日

Codeforces Round 874 (Div. 3)

　全完。システムテストも通っていました。

コンテスト後のツイート


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

yukicoder contest 389 (Until that day when "Cherry Month" is over.)

　B～Dまで三完。


No.2309 [Cherry 5th Tune D] 夏の先取り

　解説AC。

　（ツイッターで見た解法で）W全探索、Xを三分探索してAC。公式解説より計算量は悪いけど、この方法の方が実装はしやすいと思う。
時刻: 0 件のコメント:
ラベル:

2023年5月19日金曜日

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

　Eまで五完でした。

コンテスト後のツイート


F - Anti-DDoS

　DPとして、「何個の大文字が既に現れたか？」を持てば良いという情報を得て解いたが4caseでWA。他の方の提出と見比べて、大文字が出たときの遷移がおかしかったと気付いてAC。
　解法は、1<<26状態を持つのが無理なのだから、個数だけ持てば良いと考えるのは自然。コンテスト中も全く考えなかったわけではないはずなのですが……。


　自分が出したWAについて。

・……　A?B　……（"A"の前に大文字は現れない。なお、"?"は登場するので、"?"としての大文字はある。）

　のようなとき、最初のAが出たときは、

・今までに現れた大文字の個数がx個だったら、"DD"型に遷移するのはx/26通り

　Bが出たときは、

・今までに現れた大文字の個数がx個だったら、"DD"型に遷移するのは(x-1)/25通り（x個のうち、一つは確実にAなので、それを除いて考えなくてはいけない）

　なのですね。
　これに気付いていませんでした。

　結構本質的な間違いなのに4caseしか落ちないため、コンテスト中にこのWAを出したら修正が難しかったかもしれない。

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

2023年5月18日木曜日

Codeforces Round 873 (Div. 1)

　B1まで二完。良い成績じゃないけれど、どうにかB1を通せたのは良かった。

コンテスト後のツイート

B2. Range Sorting (Hard Version)

　解説AC。

　全然分からなかったけど、こたつがめさんの実況放送の振り返り部分を繰り返し聞いたら理解できた。

・（B1をやっているときに？）ブロックに分ければ良いと気付く
・ブロックの個数を数える方針にし、ブロックの左端がiになるような(l, r)を数え上げる方針を立てる。
・j<i<kで、A[j]>A[k]となるような区間が含まれるとダメ。
・iから左方向への累積maxと(i, k)の区間minがあれば数えられる。

　いや難しい。方針を理解するのも難しいし、おおまかな方針が立った後、実装方針を立てるのも簡単じゃない。（コード自体は結構短く書けるのだが）

　B1を通したときは、[l, r]が何個に分けられるか数えよう、という方針から、lを固定したとき差分計算でどうにかしよう、と思って解いたので、ちょっとこの解法からは遠かった。
　ある区間が何回数えられるか？（主客転倒）みたいな方針も最初は考えたのだけど、上手くいかない気がしてしまったからねぇ。


　解説を見てからも（少なく見積もって）数時間かかった問題が、コンテスト時間内に解けるようになるのか、というのは結構疑問なんだよねぇ……。

　ただ、「ブロックに分けられるときの数え上げ」に帰着できるような問題をまた見る可能性はあるだろうから、そのときこの問題を思い出せるようになっていれば良いかな。
時刻: 0 件のコメント:
ラベル:

2023年5月16日火曜日

AtCoder Regular Contest 160

　B一完で青に落ちた。

コンテスト後のツイート

A - Reverse and Count

　落ち着いたら自力でACできた。

　i番目の数字がxにできるか試すとき、x!=iなら、xにする方法は一通り。
　i=xなら、xにする方法は、L, Rとしてi+1以降の二つを選ぶか、L=Rとするか(*)。

　さて、前者ならそこで答えが求まる。
　後者のとき、Kがその場合の数以下であれば、ANS[i]=iと分かるので、そこを確定させ、次のi+1に移れば良い。

　方針はコンテスト中に立っていたけど、最後まで間違っていたのは(*)の場合の数の計算でした。0-indexなら、i+1+(N-i)*(N-i-1)/2なのですね。L=Rの場合の処理で混乱してしまった。最初にiを足すのを忘れてWAが取れませんでした。

C - Power Up

　自力AC。

　小さい方から合成していき、xがy個あるときは何通りか？　というのを順にDPしていけば良い（高速化に累積和を使う）。

　コンテスト中は問題文は読んだけれど解法は思いつかず、解けそうなAに戻りAに集中していた。Aを飛ばしていればコンテスト中に解けた可能性はあるけど、結果論だからねぇ。

D - Mahjong

　解説AC。

　けんちょんさんの記事を参考にしたが、形式的ベキ級数を導出する部分が理解できず、maspyさんの記事を参考にすることで何とか理解できた。Bostan-Moriのライブラリは作ってあったのだから、形式的ベキ級数に関する理解も深めたい。

　とりあえず、難しい問題は分からなくとも、maspyさんの記事の「例題」の部分はしっかり頭に入れ、使えるようにしておきたい。

　また、
・総和がMなどという条件は形式的ベキ級数を使いやすい
　ことは押さえておきたい。
時刻: 0 件のコメント:
ラベル: , ,

2023年5月13日土曜日

yukicoder contest 388

　Eまで五完。


No.2302 Carry X Times

　桁DPだという情報を得てAC。

　桁DPだと分かった上で見ると桁DPの問題にしか思えないし、桁DPとしてはかなり書きやすい部類の問題で、すんなり書くことができた。
　これを思い付けなかったのはまずい。

No.2303 Frog on Grid

　解説AC。

　縦・横それぞれについて、x回のジャンプで行く場合の数を計算し、それを組み合わせるという計算量H*Wの解法は分かったが、高速化が思いつかなかった。
　FFTはちょっと考えたが、二項係数をかけるので無理だろうと諦めてしまったが、それぞれの配列を予め割る数で割っておけば良いのね。
　FFTを使う問題での前処理としては難しくないものだと思う。こういう処理に慣れないと。

No.2304 Distinct Elements

　解説AC。

　slope trickの練習問題として解けるのだが、slope trick自体（DPテーブルが凸になっているという性質を利用する）も忘れていた。さらに、maspyさんの解説ツイートの、

・dp[x] = min_{y<=x}dp[y] + |x-a|

　という式にも納得ができず、長いこと悩んでしまった。

　いや、この式自体は分かっていたのかもしれないけど、この操作を累積minした後、|x-a|を加えるという操作で表せるということが納得できなかったのかもしれないけど……。

　どちらにしても、slope trickを理解できていれば自然なものなので、ここで悩むのはおかしい。
時刻: 0 件のコメント:
ラベル: , , ,

2023年5月11日木曜日

Codeforces Round 871 (Div. 4)

　全完できました。Div.4も最後の方に妙に難しい問題が置かれていたりするので、ちゃんと全完できると嬉しい。

コンテスト後のツイート


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

トヨタ自動車プログラミングコンテスト2023#1(AtCoder Beginner Contest 298)

 　Fまで六完。


G - Strawberry War

　解説放送を見てAC。

　最小値を固定すれば、最大値を求めるのはDPでできる……というのは言われれば自然。また、変わった制約ではあるけれど、何らかのDPをするのだろうと考えるのも自然ではある。

　けど、コンテスト中は何も思いつかなかったし、DPと言われても全く何をすれば良いか分からなかったね……。
　とりあえず、計算量はよく分からなかったとしても、「T回切断したときの最大値はDPで求められそう」と気付けなくてはいけなかった。
時刻: 0 件のコメント:
ラベル:

2023年5月6日土曜日

yukicoder contest 387 (Union Find Contest)

　Bまで二完。Bで一旦離脱するも、（Cを解き終るくらいには）余裕を持って帰ってきたつもりが、実装にハマってCが解き終わらず終了。


No.2291 Union Find Estimate

　時間はかかったが自力AC。

　大まかな解法は分かったのだが、いつUnionするかなどで間違い、矛盾する（答えが0になる）判定などが上手くいかず時間がかかってしまった。
　
　こういうので失敗しないコツってあるのかなぁ。落ち着いて、頭を整理して解く、くらいしか思いつかない。
時刻: 0 件のコメント:
ラベル:

2023年5月4日木曜日

Codeforces Round 860 (Div. 2)

　Dまで四完だったが、Cがシステムテストで落ちた。二分探索の上限をミスっていた。

コンテスト後のツイート

E. Multitest Generator

　解法ツイートを参考にAC。

・答えは高々２である
・0にできるかは、後ろからDPをすれば求められる
・1にできるかは、以下の二つで場合分け
  - A[i]自身を変更する：DP配列の後ろからmaxを取っておけば分かる。
  - 他の数字を変更する：DP2として、後ろからindex i までで一回だけ数字を変更したとき、最大で何個のtestに分けられるか？　を求めれば、それを使って答えが求められる。

　整理して考えればそんなに難しくないが、整理するのが難しい。


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

yukicoder contest 351

　A一完。


No.2001 Distanced Triple

　久しぶりに見たら自力AC。

　x, y, zの位置関係を図に描くと、R=R-L, L=0としても答えは変わらなそう。そして、z-xを固定して考えると良さそうに見える。
　その方針で立式すると、Σ((c-i)*i)という形になるので、Σの中身を展開してΣ計算は公式を使えばOK。

　今は苦戦せず解けたけど、こういうの解けないときは解けないんだねぇ。

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