最終更新: 2024-04-03T08:25+0900
AtCoder をプラットフォームとして利用する有志コンであり、AtCoder の問題ではないけども、競プロカテゴリとして AtCoder に分類しています。
リアルタイム参加はしていない。ABCDFHIE をこの順に解いたのでふりかえって書く。
出現数を数える。Array#tally そのもの。
２本の線が一致することはないので、必ず３つか４つに分割される。ソートするなりしてうまく分類する。
うまくできませんでした。
数列が a,1,b であるとする。そうすると、b=a+1、a=b+1、b=a+1 と操作を繰り返すことで無限に大きな要素を作ることができる。A[1]=1 の場合であっても、A[1] を無限大にすることができる。初期数列が１以上の要素を含んでいることが必要十分条件だと思いました。証明は知りません。
間違えました。最初は、２つの要素を足して１以上になることが必要十分条件だと思ったんだよね。証明は知らないとか言ってっからだよ。
すごーく難しかった。４回間違えた。順番に WA×13、WA×3、WA×2、WA×1。
まずは問題を理解する。X 座標と Y 座標について、正負どちら方向に移動することもできるけど、移動量の絶対値が一致していなければいけない。
どういう操作を構成するか。最初からずっと想定していたのは、まずは X 座標もしくは Y 座標の、ずれが小さい方の数字を一致させる。その後はずれが大きい方を、偶数回の操作で一致させる。偶数回というのは、先に合わせた方の座標をずらしたくないので、移動量を等分して打ち消し合わせるということ。
この考え方で WA×1 まで行ったのだけど、一方のずれに対して他方のずれが非常に大きい場合に答えが微妙に合わなくなる。
結論を書くと、最初に目指すべきポイントは近い方の座標ではなかった。偶数回の操作の折返し点を目指すべきだった。要するに、X 座標のずれが DX、Y 座標のずれが DY だとして、DX<DY なら最初に目指すべき点は DX+(DY-DX)/2 だったということ。DX だけ移動してから DY-DX を偶数回で移動するのではなく、DX+(DY-DX)/2 移動してから (DY-DX)/2 移動する操作を構成するのだった。
ARC で 400 点ぐらい配点してもいい問題だと思います。400 点というのは、数学的センスがある人は瞬殺するけども、自分は１時間以上苦しむという、そういう問題。
任意の部分列について成り立たなければいけないので、一番極端なケースを想定する。つまり、N=1 のケースと N=2 のケース、そして中央値に対して極端に平均を下げるような列を。
N=1 のケースでは中央値と平均値が一致する。N=2 のケースでは a1<a2 なる列の中央値が a1 なので平均値が必ず中央値を上回る。N>=3 の場合で N が偶数のとき、中央値より大きい値の数が小さい値の数より１つ多くなるので、平均値は大きくなりがち。だから N が奇数の場合だけを考える。もっといえば、N=3 で成り立つなら N=5 でも N=7 でも成り立つと思うんだけど、そんな気がするだけ。
N=3 のケース。a1<a2<a3 としても構わないのでそうする。平均を下げたいので a1 は最低の 0。a3 がいくつなら平均が a2 以上になるだろうか。2×a2 が最低ライン。N の制約が 20 万以下ということだけど、要素が倍々に増えていくなら ai≦10^9 の制約から実質的な上限は 30 程度になる。
問題文の表現にひっかかりがありますね。「氷の張ってある道をなるべく通りたくないです
」「氷の張ってある道を通る時間を最小化して街 N に移動するとき
」。要するに氷が張っている道を通ることもあると言っている。01BFS みたいに、氷が張っている道を０回通る場合の最小値、１回通る場合の最小値、２回の場合の……、を N にたどり着くまで繰り返して求めれば良さそう。うまくやればいらないかもだけどプライオリティキューを使ってダイクストラ法をした。
01BFS ということでこれは２本のキューを切り替えながら使った。
氷の上を何回通ったかと経過時間とを１つの値にエンコードすることで、キューを１本だけ使う普通のダイクストラ法になった。
まずは問題を理解する。ある要素を１つ後ろに移動し、その際に K を加算する、というのが操作。
最初は後ろにある要素に操作を繰り返して大きくすることで昇順の列を作ることを考えた。最低２つの要素があれば、交互に操作対象に選ぶことで任意の回数 K を加算することができる。２つの要素の初期の差を解消したり拡大したりすることはできないけど、１回の操作で昇順にできるので問題ない。
これの問題は K=1 で Ai が上限の 10^9 に近いとき。初期数列が A1=10^9、A2=1、A3=1 だったとして、A2 と A3 に操作を繰り返して A1 以上にすることは可能だけど、操作回数が 50 万を超えてしまう。
次に考えたのは、最小値を列の前に持ってくること。i 番目に最小値があるとして、i-1 から 1 まで下りながら操作することで A1 から A_{i-1} にそれぞれ K を加算しつつ、Ai を先頭に持ってくることができる。以降これより後ろの数列に対してどんな操作を繰り返したとしても、Ai より小さい値が後ろに出現することはなく昇順が保たれる。
初期数列が降順にソートされている場合が最悪ケースだけど、N*(N-1)/2 回くらいの操作で昇順になる。N≦1000 だからちょうど操作上限の 50 万回を下回るくらい。
しょうもないミスをした。
vector の任意の位置から値を追い出すときに、末尾の要素とスワップしてからポップするというテクニックがある。順番に意味がないときは使って損がない。
順番に意味はあったのだ。順番が保存されていないと正しい操作対象が選べない。いや、自分は壊れた順番の中で正しい対象を選んでいたのだけど、そのせいで勘違いしたのだけど、ジャッジが正しさを検証できなければ意味がない。
300 点だけど難しかった。これが解けたのが嬉しくて今日の日記を書いているところがある。
とある赤い亀さんの日記を読みました。
学びのある問題だった。
最終更新: 2024-01-18T16:02+0900
AtCoder の問題ではないが精進。ABCE の４問。
基本的にはカードを順番にスキャンして判断をする。ハッシュ表を使って自分が一番小さいカードである場合、２番目、３番目の場合の３パターンについてカードが３枚揃っているかを確かめる。もしくは、昇順にソートして自分が一番大きいカードであるケースについてカードが揃っているかを確かめる。
N 個の商品がありそれぞれの商品は M 種類の商品カテゴリのどれかに属している。M 日間のセールがあり、セール期間のある一日にはあるひとつのカテゴリの商品が半額になる。Q 人の客がそれぞれある日に訪れ、ある範囲の連続する商品を購入する。さていくら？ Q 個答えよ。
割引がなければ範囲の総和を知るのに累積和を引くだけ。しかしある日にはあるカテゴリの商品が半額になっているので、範囲内にそのカテゴリの商品がいくつあるか知りたい。カテゴリごとに位置を昇順に記録して二分探索をした。
カテゴリごとに累積和を用意しようとすると最悪の場合長さ N の配列が M 個になって、N×M は大きすぎる。更新のあったところだけ記録しようとすると、さっき書いた「カテゴリごとに位置を昇順に記録」する方法になる。
難しいね。いっぱい間違えた。制限時間が１秒とやや厳しめ。
３の倍数の長さ(0,3,6,9,...)の範囲を切り取ってみれば、左端の位置と右端の位置、それと RGBRGB...RGB 文字列との不一致の数からコストがわかる。不一致を単位時間で数えるためには３種類の累積和を用意しておけばいい。すなわち、RGB...RGB..、BRG...BRG..、GBR...GBR.. 文字列と S との不一致を数えた３種類。
ところで、N の上限が 20 万のときに範囲の両端を自由に選ぶと 20 万の２乗(割る２くらい)で間に合いませんね。範囲の左端を総当たりすることにして最善の右端をどうやって決めるかというところで３回 WA を出した。
最初の提出 #48448208 では左端を右に移動するごとに右端を左右に移動させてみる尺取りをした。特定の制約を追加したサブタスクはクリアしたが、N の制約を甘くしただけのサブタスクで一定割合の WA がある。時間は間に合っていて(局地的に)最適な答えを見つけることもできているが、最善の答えをときどき見逃しているということ。
次の提出 #48453131 は不等号にイコールを追加するような微修正で、３割くらい WA の数は減ったけど本質的な誤りは修正されていない。
３番目の提出 #48453143 は３つのサブタスクで２つずつ WA があるという結果で、ほぼ AC と同じ。実はこれまでの２つの提出ではケアしていた、左右どちらかから全ての文字列を削除するケースに対応したコードを削った結果 WA を生んでしまっている。正しい解法を見つけたときにもういらない気がしたんだよなあ。
これが AC。右端を見つけるのにスライド最小値(？)だと思うものを使った。実装はしなかったけど三分探索も検討していた。知っている解法を総当たりして正当性の判断をジャッジに委ねるのはやめようね。
時間に依存したコストをどう扱うか。t=0 となる位置を１から N へのパスの中のどこに置くかでコストが変わる。パスの外に置いても得をしないので考えない。どこに置くのが最善で、どうすれば最善が見つけられるか。
t=0 となる地点をあるパスの中のある辺に置くとする。１がある方のパスに A 個の頂点が、N がある方のパスに B 個の頂点があるとして、A<B なら t=0 の地点を辺上で N の方に近づけるのが良い。A=B なら辺上のどこにあっても同じ。なので、t=0 の地点をどこかの頂点から選んで良い。
t=0 となる頂点を決め打って、１からの最小コストと、N までの最小コストが求まれば良い。１からは順方向に探索し、N からは逆方向に探索すれば、２回の手間で答えが求まる。N 頂点全てを始点にして N 回の探索をすることは時間的に許されない。
提出日の開きを見るとわかるけど、この AC はほぼ一週間がかりだった。
探索は BFS。移動コストが固定値の C と、パスに含まれる頂点数に比例する L×K なので、BFS によって頂点数が単調増加だと想定できると、単純にコストの総和を比較するだけで最短経路が見つけられるし、頂点数に比例したコスト計算もやりやすい。
サンプルの４、５、６あたりの答えがいつまでも合わなくて、ああでもないこうでもないと試行錯誤していた。さっぱり見えていなかったのは AC 提出の 22 行目、頂点 N までのコストを探索する D 関数に与える初期値(DN = D[ヨ[N].group_by{|s,|s}.map{|s,stcs| [s,stcs.map{_3}.min] }.to_h,ヨ])。１からのコストを求める 21 行目(D1 = D[{1=>0},E])と比較すると長さだけ見ても段違いなのがわかる。この違いがさささっと把握できる人はすごすぎると思います。
N から逆向きにコストを計算するのに N の隣接頂点を始点にすればいいとはなかなか……全然わからない。そこにやっと気がついても N とその隣接頂点 V を端点とする辺が複数あるということがまた思い出せない。
たいへんだった。これ予選なんですって。
今３ページくらい E 問題の AC 提出があるんだけど、Ruby の 113 ms が最速だった。おもしろ。ただ、前回の言語アップデートから AtCoder のジャッジは、言語ごとに最初の１ケースだけウォームアップ時間が計測に含まれるみたいな雰囲気があるので(このときの話の関連>20230807)、ワースト１ケースのタイムが特異例である場合の比較に意味はない。
こちらの提出 #48433529 を見ると N×M のループを順方向と逆方向の２回回してるだけに見える。辺を端点ごとにまとめたりもしていない。どういうことなの？ 結局 L[j]*K に (i+1) を掛けるか i を掛けるかというだけの違いだったの？ そうみたい。
頂点数を１減らしてコスト計算する試みはけっこう初期にやっていて、でもたぶん他の部分のバグのせいで答えが合うところまでいかなかった。AC コードがある今同じ方針でやってみるとふつーに、よりシンプルに、答えが出た。なんだよもー。さっき書いた 21、22 行目だけど、こうなった。
D1 = D[1,1,E] DN = D[N,0,ヨ]
そう、これくらい単純に順方向と逆方向の探索ができると思っていたし、実際できるのに、どうして１週間も沼にはまりこむ結果になったのか、謎だ……。
最終更新: 2023-03-03T18:23+0900
赤になってから Z 秒時点でボタンを押したら X 秒後に青に変わるけど、最低 Y 秒間は赤の時間が確保されているように。[Z+X,Y].max
正整数 を 100 で切り捨て除算する。桁数が 50 万と 1 になることがあるのでうっかり gets.to_i してはいけない。いや、案外平気かも。文字列として２桁削るのが無難だけど N が２桁以下のときに 0 を出力するのを忘れない。
出目の和ごとに場合の数を記録する DP。6×6×6×18 程度の計算量。
辺の集合が与えられたときに多重辺と自己ループの有無を調べる。
強いて注意点を挙げるなら、多重辺を調べるときに文字列のまま比較すると 1 2 と 2 1 の同一性を見逃してしまうことと、隣接頂点リストを配列として持つと星型のグラフで多重辺のチェックが O(N) になってしまって全体が O(N^2) で TLE になってしまうこと。Ruby なら Hash で隣接頂点を管理する。
問題文に書かれている通りにスコアを消費していって、スコアに過不足がないかを調べる。
限られた数の薬と数限りないアレルゲンがある。薬が含むアレルゲンと人が持つアレルギーが交わらないようにするとき最も効果の高い薬の番号を答える。
制約を見ないと方針が決められない。薬は最大 100 種類。アレルゲン/アレルギーは最大 20 万種類。人は 10 万人。ただし人が持つアレルギーの総数が 10 万までに抑えられている。
人が持つアレルギーごとに使える薬を定数時間で調べて 1000 万の処理量。アレルゲンをキーにして 100 ビットのビットフラグで使えない薬を管理した。
N が 1000 以下、L と K が 10 以下に抑えられているので、一致しているべき文字のインデックス(L-K 個)を決め打ってから文字列の集合を分類して絞り込んでいった。考えるのではなくうまく実装する。
問題文から読み取るべきこと。銀貨が有限だが無数にあると考えていい枚数ある一方、銅貨は X 枚に限られている。両替はできない。金銀銅の価値は差が非常に大きく、価値の大きい貨幣の多寡を価値の小さい貨幣でひっくり返すことができない。
なので、X 枚の銅貨をできるだけ多くの金貨に変えることをまず考え、金貨の枚数が同じ場合に使用した銀貨の枚数を少なくすることを考える。
そこまで分かれば銅貨の枚数ごとに金貨と銀貨の枚数を記録する DP をやるだけ。
悲しさを考える前にまず m で割った n 個の余り a%m,2*a%m,3*a%m,...,n*a%m について考える。d = gcd(a,m) とおく。m 種類の余りは周期 c = m/d のサイクル(d 個)に縮約される。それは次のようなスクリプトで可視化すればわかる。問題を解くだけなら証明はできなくてもいいでしょう。
n,a,m = 10,6,10 # d=2
p (1..n).map{|i| a*i%m } #=> [6, 2, 8, 4, 0, 6, 2, 8, 4, 0] 周期 c = 5
n,a,m = 10,10,6 # d=2
p (1..n).map{|i| a*i%m } #=> [4, 2, 0, 4, 2, 0, 4, 2, 0, 4] 周期 c = 3
サイクルの和は初項 0、公差 d、項数 c の等差数列の和なので c*(c-1)/2*d。サイクル当たりの悲しさは、余りが 0 の項の悲しさが 0 であることに注意して m*(c-1)-(サイクルの和)。
サイクルから外れた n%c 個の悲しさをどう求めるか。一発で求まる式があるとは知らない。m が 300 以下の制約だから 10 万件のテストケースごとに最大 299 項の和を求めるとなると最悪 3000 万の処理量。Ruby ではちょっと厳しいかな。
n%c と c-(n%c) を比較して、n%c の方が小さいなら悲しさを足し上げる、c-(n%c) の方が小さいならサイクル当たりの悲しさから引き算で逆算することにして、最悪 1500 万の処理量ならまあまあありだと思う。同数ならどっちでもいいよ。
n%c の区間をどんどん割って余りを取って効率的に数えられるような気はする。ユークリッドの互除法くらいの効率で。でも数字が合わない。
長方形と円のどちらかがどちらかを含む場合を除けば、扇型の面積から直角三角形の面積を引いたり引かなかったりすることで水を撒く面積が求まる。
扇型の面積(s)の求め方。半径を r、弧を l とすると s = r*l/2。弧の長さ(l)の求め方。中心角(ラジアン)を θ として l = r*θ。中心角(θ)の求め方。三角形の３辺の長さがすべて分かっているので、余弦定理から中心角の cos が分かり、cos が分かれば acos 関数で角度が分かる。
ここまでわかればあとは場合分けを間違えないようにやる。
辺を繋いで連結判定をするのはおなじみ UnionFind で。辺を切断する方法は知らない。辺を繋ぐのが 10 回以下に制限されている一方、切断する回数はいっぱい。クエリを逆向きに処理すれば切断は接続に、接続は切断に変わる。10 回の切断をどうするか。UnionFind のデータ構造を丸々コピーしても 10 万×10 = 100 万だから許される。落ち着いて頭の中を整理して逆向きに考えられたら実装するだけ。
ヒントを見たよ。https://twitter.com/kyopro_friends/status/1630510505323540481
ポイントを抜き出せば「「最終的にmod3で何枚選ぶか」をkと先に決め打っておけば
」というだけのことが独力で解決できないのだな。
基本は絵画を順番に、選んだ個数を３で割った余りが 0,1,2 のときのおすすめ度の最大がいくつかを記録する DP をやる。ここに「最終的にmod3で何枚選ぶか」が関わってくるので、(最終的な余り 0,1,2)×(現在までに選んだ個数の余り 0,1,2) = 9 通りを記録する DP をやる。答えを表示するときは (最終的な余り,現在までに選んだ個数の余り) = (0,0),(1,1),(2,2) の３通りから最大値を選ぶ。
ある範囲のセット買いと単品買いを組み合わせて全 N 巻を揃えるのにかかる費用の最小値を求める問題。
i を増やしながら 1 から i 巻目までを揃えるのにかかる費用の最小値を記録していく DP をする。セット買いについては範囲の右端に注目する。
単巻買いの場合、1 から i 巻目までを揃えるのにかかる費用の最小値(C[i])は C[i-1]+A[i]。(A[i] は i 巻目単体の価格)
範囲の右端が i であるセット買いの場合、範囲の左端を l、セット価格を b とすると、i 巻目までを揃える費用の最小値(C[i])は min(C[l-1],C[l],C[l+1],...,C[i-1])+b。区間最小値はセグメント木にお尋ねします。
まだだよ。
まだだよ。
最終更新: 2023-07-22T23:29+0900
- タクシーが赤色の場合，乗車後の所持金が a−1 円になる．
- タクシーが青色の場合，乗車後の所持金が「a÷2 を整数に切り捨てた値」円になる．
町 1 から出発し，1 円以上の所持金を残した状態で町 Tj に到着するために，最初に少なくとも何円の所持金を持っている必要があるか
問題のこの部分は、まあ、逆に考えます。所持金が１の状態でスタートして、所持金が +1 になる、×2 になる、というように。そうすれば初期金額を探索しなくて良い。ただしそれぞれの町をスタート地点に設定して町１への最短経路を繰り返し求めるということは許されていないので、スタート地点は町１のままにしておきたい。
ところが町１を１円でスタートして、+1/×2 しながら各町に着いたときいくらになっているかをダイクストラ法で求めてもサンプルが合わない。合わなかった。
たぶん、-1/÷2 の逆計算は +1/×2 でいいのだけど、((((-1)-1)÷2)-1)÷2 の逆計算は ((((×2)+1)×2)+1)+1 ではないとか、合ってるけどその通りに計算できていないとか、そういう理由。
わからんなりにテキトーに 2×2 の正方行列に 2 とか 1 とか 0 を割り当てて実際に計算してみれば、必要な係数が２つだということと、それをどう変化させればいいのかがわかった。スクリプトの中の x,y = x,x+y と x,y = x+x,y というのがタクシーごとの変化。式を見ても意味はわからない。
逆計算がわかったからダイクストラ法で解けたかというと、小課題の４あたりから答えが稀にあわなかったり時間をオーバーしたりする。した。小課題の３までは問題のグラフが木だから複数の経路の競合がなかったのだな。
これはたぶん、ある町における状態というのが所持金というパラメータ１つで優先順位を付けられないせいだと思う。さっき x と y の式を２つ書いたけど、そして所持金というのが d = x+y で表されるのだけど、ある町からある町へ移動するにあたりどちらのタクシーを使っても所持金の変化は x+x+y == d+x で共通している。だけどその次の移動での増加量が x の値にのみ依存するので、x を増加させることで所持金を変化させたタクシーの方が分が悪い。
２つのタクシーの運賃を普通の経済感覚で比べてみると、どの場合でも所持金が１円減るだけの赤色のタクシーを利用できるときは利用して損をすることがないことがわかる。たぶん。01BFS みたいなステップを踏めば解けるような気がするなー。
頭の中が整理されていないので無駄がまだあると思う(嘘解法の可能性も大いにある)。でも１秒しかなかった JOIG-2021-F「デジタルアート (Digital Art)」(20211210p01) と違って制限時間が４秒もあったので間に合った。嬉しい。
D 問題まではやるだけだったけど、E 問題「エゴイ展 (EGOI Exhibition)」がまだ解けていない。価値の正負と絵の種類で場合分けとクラス分けをして DP をしようとしたんだけど……。
PQ#dn_heap がバグってるね。不等号の向きが逆。これは要するに、PQ には繰り返す幅優先探索の無駄を気休め程度に取り除く意味しかなく、実際にはその効果さえなかったということ。
PQ#dn_heap のバグをとったとしても定数倍が重いせいで、初期パラメータが異なる複数の地点をスタート地点に設定した幅優先探索のようなものを、距離の更新がなくなるまでぐるぐる回した方が速い。優先度付きキューを使うと確かに最短距離を複数回更新するという無駄はないのだけど。
Array をキューにするのと Hash をキューにするのでは Hash の定数倍が重い。キュー内で要素が重複することを気にせず Array につっこんだ方が速かったりする。
そんな(良くない)理由でメインループ内の前半のループのキューは PQ でも(後半のループのように) Hash でもなく Array になっている。
キューを２本持つことでプライオリティキューを使わないでもソート済みの状態を保ちながらキューを伸ばせる場合があるというのは、AtCoder について書いた２番目の日記に書いてある>20190916p01.01。今回もこれが使える。
863 ms というのは Ruby に限らない AC の中で１ページ目に入っているのだ(全部で９ページではあるのだけど)。
最終更新: 2022-01-03T13:27+0900
D と E についてはここに書いた>20211206。A,B,C については ABC-C までの難易度帯という感じで特に何ということもなく解けたので書いていない。最後に F 問題が残っていた。
色ごとにその色を完全に覆い隠せる矩形を考える。矩形は左上座標と右下座標で特徴付けられる。面積 S を超えない範囲でどのような矩形を選べばできるだけ多くの色を隠せるだろうか。
グリッドの一辺は最大 1000 なので、グリッド上の点は最大 100 万個。いくら面積 S を超えない範囲でできるだけ大きな矩形のみを考えるとしても、グリッドから２点を選ぶ組み合わせは１メガ×１メガに近い数になる。これは制限時間１秒で扱える数ではない。
色数の上限が 256 に抑えられている。256 の３乗は約 1600 万だから、Ruby の場合、定数倍が 1/2 とかなら３乗がなんとかなるかな、という雰囲気。
二次元累積和であるとか「Range Set Query」が思い浮かんだけど、どうにも(知っている)定型の処理に当てはまらない。
矩形の左上座標と右下座標を探索することが許されるなら、色を、その色を囲う左上座標と右下座標のそれぞれでソートしておくことで、うまく探索してマッチングして数を数えられると思う。
色を特徴付ける矩形の左上角と右下角の組み合わせを選ぶ 256 の２乗通りでは答えを漏らすのでよろしくないが、４辺を選ぶ 256 の４乗通りは許されない。困った。
矩形の縦の長さを固定して横方向に尺取りをした。
最後の小課題９のケースもいくつか通ってるので惜しいのかと思ったけど、実は遅いケースは 10 秒とかそこらかかっていた。
４重ループです。上辺について 256 通り。底辺について 256 通り。右辺と左辺について尺取りが 256×2 ステップ。その最深部で矩形に出入りする色が 256 個。だめじゃん。
定数倍の改善。Array#minmax の呼び出し回数を節約した。650 ms が 350 ms になるレベル。
定数倍の改善。上辺と底辺に関する第一第二ループを Array#repeated_combination(2) で横着せずに、尺取りっぽく遷移して重複する処理を減らした。550 ms が 450 ms になることもあるし、変わらないこともある、という変化。
ついに来た！ TLE は残り１ケース。
改善したのはやっぱり定数倍だけど、上辺に対する底辺の選び方を、尺取りの幅でグループ化して最も高さが大きくなるものに代表させることで、尺取りの回数が大幅に減った。
もうひとつ。ループをイテレータではなく while 文で書き直すことで Ruby の場合かなり速くなるんだけど、それに加えて、答えの候補を求めるループの途中で暫定的な答えにアクセスできるようになったのも大きかった。それにより答えを更新する可能性がない場合に最内ループをスキップすることができた>or ain.size<=max。
これも定数倍の改善。インチキをした。底辺を尺取りの幅でグループ化する部分が
i1s = I1s.group_by{|i1| i1<i0 ? 0 : [S/(i1-i0+1),W].min }
だったところを、次のようにした。
I1s.shift while I1s[0]<i0
i1s = I1s.chunk{|i1| [S&1|S/(i1-i0+1),W].min }.map{|_,as| as[-1] }
S&1| ってなんですかね？
とにもかくにも、(１差の偶数と奇数を同一視することで)４重ループのうちの２番目のループの回数が節約できたのはとっても効いた。
想定解法は３乗もしくは３乗＋logとかのもっとスマートなアルゴリズムを使っているのだろうか。それとも Ruby は想定外だからさっさと Crystal や C++ で出し直すべき案件だったのだろうか。3 MiB オーバーの入力ファイルを読み込むのにも、つまりはスクリプトの１行目の処理を終えるまでにということだけど、１秒しかない時間のそれなりの割合を使っているのだよね。
想定解法は上辺と底辺を固定しての尺取りだった。やり方は間違っていなかった。その計算量が O(HW+A^3) だというのがわかっていなかった。実際は A^3 でできていたのか、それとも何かおかしなことをして A^4 にしてしまっていたのか、どっちだろう。
ちょっとおかしなことをしていた。AC 提出の最内ループのこの部分。
ain.reject!{|wj0| wj0<=j1 }
尺取りから出て行く色を見つける部分で、尺取りの中にある色の全体を都度スキャンしていた。
尺取りの右がある座標に至ったときに入る色と、尺取りの左がある座標に至ったときに出る色は、それぞれの合計が最大で 256 個であり、一度の尺取りを通して合わせても 512 個という定数にしかならない。ある座標で入る色と出る色をそれぞれリストしておいて、ある座標に至ったときにそれらの色が尺取りの中にあるかどうかを確かめるべきだった。
このように>joig2021_f.rb27。あるいは最初に TLE をもらった提出 #27751046 のように>20211210p01.05。
だけどたぶんこれは TLE になる(OS が違うけどローカルで測定している)。定数倍の影響が大きすぎるのではないか。最後の TLE をクリアしたとどめの一手だって、尺取りのステップ数を随時削減することによる定数倍の改善だった(S&1| だけでは足りなかったのだ)。やはり Ruby で満点を取ることは想定されていないと思う。
日本情報オリンピック 第2回女性部門（JOIG 2021/2022） から「情報オリンピックに初めて参加する方は、出題形式・勉強法・講習会などに関する情報をまとめた「情報オリンピックの勉強法」をご覧ください」とリンクされていた(JOIの)ページから。
JOI 本選
本選は 2 月に実施されていて、4 時間で 5 問に取り組みます。上位者は春合宿に招待されます。
本選では二次予選と比べて難しいアルゴリズムの知識や、そのアルゴリズムを与えられた課題に適用させるための高度な発想力が問われます。
JOI 春季トレーニング合宿 (春合宿)
春合宿は IOI 日本代表を決めるための代表選抜会です。3 月に実施されていて、4 日間連続で毎日 5 時間の競技に取り組みます。上位 4 人は IOI 日本代表として派遣されることになります。
なお、春合宿で使えるプログラミング言語は C++ のみです
本選の後に春合宿があり、「なお、春合宿で使えるプログラミング言語は C++ のみです。
」 そうなのね。
最終更新: 2021-11-12T21:42+0900
解けなかった。
これはコンテスト中の提出。WA と AC の比率からして惜しいのかなという感じ。おそらく 0 を返すべきケースで 0 が返せていない。それはどういうケースか。連結成分が８の字になっていたりして輪っかが１つではないケース。
しかしそれをどうやって検出するのか解らなかった。
これはコンテスト終了後の提出。さっきの WA 提出では UnionFind で閉路の検出(だけ)をしていたのだけど、もうちょっと細かく、ノード数と辺の数の両方がわかるように記録をつけた。
辺の数がノード数より１だけ小さい連結成分は木であり、辺の数はこれが最小。辺の数とノード数が同じ連結成分はループが１つとオプションで突起をいくつか持っている。辺の数がノード数より多い連結成分は複数のループを持っている。
題意を満たせるような連結成分は３種のうちの１つだけ。他の２つが存在すれば答えはゼロだし、適合する連結成分のみが A 個あったなら答えは 2.pow(A,998244353)。
ここまで考えがまとまるのに２時間かかってるんだよなあ。
なんか「なもりグラフ」という名前があるらしかった。調べようとしたらゆるゆりの人と名前がかぶってて検索性が悪かったのだけど、別に間違ってはいなかった。なもりを検索してなもりが見つかるのは当然。
chokudai(高橋 直大)🍆@chokudai
F問題の由来です。（N頂点N辺の連結なグラフを「なもりグラフ」と呼ぶ人がいるのもこれが理由です。） https://t.co/saSTvA1lep
F 問題って、AGC の F 問題「Namori」じゃないですかー(やだー)。赤 diff の精進は 10 年後も手つかずの見込みですから。
これもあった。ARC079-F「Namori Grundy」。橙 diff は、どうかなあ。解説 AC が１つあるだけだけど、10 年後は。
最終更新: 2021-10-26T00:58+0900
D 問題で TLE に苦しんだ。E 問題も TLE に苦しんだ。そのまま E 問題が解けなかったので F 問題は読めなかった。
全探索が許されそうな制約。重複チェックのためのハッシュ表のキーを文字列にするか配列にするかで悩んだ。結果的に文字列ベースの探索で AC になった。
欠けてる数字を９番目の要素にするのがちょっとした Tips. TLE 解消の決め手にはならなかったんだけど。
現在の状態からありうる次の状態(のうち初出のもの)をすべて候補にするという意味で感覚的に全探索と書いたけど、そういうのは幅優先探索と呼ぶらしかった。
時間は１時間ほど残っていたのに、結果的に１時間と 10 分が AC までに必要だった。
D 問題の TLE×1 と違って全然惜しくない。どこの処理量が膨れ上がるかとソースを眺めてみると、遷移のための辺を逐一処理しているところがダメ。
遷移の方向は A の小さい方から大きい方に決まっているので、A の降順に遷移可能回数を数え、行と列にその回数をメモしておけばいい。今後この行(この列)から遷移先を探すものがあるならメモした回数だけ遷移できますよ、というメモ。A の降順に処理しているから参照したメモはいつでも有効。
ああいや、A の値が等しい別の点が書き込んだメモを参照しないようにだけ注意が必要。この辺の呼吸は珍しくないので心得たものである。
あと 10 分あればなあ。
不要になった処理を消し忘れてた。
レートはちょっとだけ上がってる☞。しかしもっと上がりたかった。
最終更新: 2021-11-23T22:07+0900
精進ですよ。水 diff だけど難しい(まるで水 diff が簡単かのような……)。考えがまとまるまで１日かかった。
隣接２要素をスワップして +1/-1 するというけど、考えやすいように複数の操作をまとめるとこう。
Ai の値は移動に伴って変化しているように見えるけど、実のところ位置に応じて決まった値をとっているに過ぎない。どういう値をとるかは、最初に位置 i で値 Ai をとっていた、ということで決まる。
A 数列の各要素が位置１でとる値をその要素のポテンシャルと呼ぶことにする。ポテンシャルから要素の位置を逆引きできるようにインデックスを作成しておく。
B 数列をスキャンしながら、要求するポテンシャルを計算し、該当する要素を A 数列の先頭に近いところから貪欲に引っぱってくる。
引っぱってくるに際していくつの要素と位置を交換することになるかは BIT で転倒数を管理することで数える。というか、知る必要があって管理している数字が転倒数と呼ばれている、が順序として正しい。
難しい。これが水 diff ってどうかしてる。ちなみに Swaps の１はこれ>「Swaps」。黄 diff です。解けるまで９か月寝かせました(20191111p01→20200826p01)。２は１日寝かせただけで解けたんだから、妥当なのか？
最終更新: 2021-11-15T21:43+0900
大反省回。未だに ABC で ABC の３完敗退を繰り返していることに驚きを隠せない。今回がそうだしついこの前の ABC219 もそうだった>20210918。ついでに言うと３年以上前の第２回参加回もそうだった☞。まるで成長していない……。戒めとして普段はとばす A 問題から振り返る。
20 年前の自分だったら N の常用対数から N の桁数を求めてくっつける 0 の数を決定していた。
だけどとある WSH 関連の掲示板で、十分な数の 0 をくっつけてから必要な文字数だけ切り出す方法を知った。
他の人の提出を見ると printf かそれに類するメソッドを使うものが多かった。Ruby で最初に提出した人は rjust を使っていた。目的にぴったりのメソッド(rjust)がある以上、それを使うのが最善だった。
こういうこと。
L = lambda{|n| Math.log10 n } # 正整数 n の常用対数
D = lambda{|n| L[n].floor+1 } # 正整数 n の桁数(10進表記)
p [D[99],L[99]] #=> [2, 1.99563519459755]
p [D[100],L[100]] #=> [3, 2.0]
p [D[101],L[101]] #=> [3, 2.0043213737826426]
学校で対数を習っても理解が伴わないと計算問題はできてもこういう風に実用できなかったりする。Project Euler の 62 問目を二重ループで解いたりもする>20110308p01.02。
実はまだよく分かっていないのは自然対数の底 e。なんだかこれを底にすることで累乗が掛け算になったり曲線が直線になったりして性質を変えずに扱いやすくなったりするらしいんだけど、そういうのは(文系学部に分類されるらしいことを少し前に知って驚愕した)経済学部の人に任せておきたい。
コメントのしようがない。スクリプトを読んで。
制約が小さいので愚直にシミュレーションをすれば良い。
解答を作成するのに 20 分かけたのが良くなかった。出力フォーマットを勘違いしていて、求められているのが順位で並べた人番号だったのに、人番号順に順位を表示しようとして余計な手間をかけ、余計な手間を実装するのにもやけに手間取ってしまった。
解けなかった。シンプルな DP。直前の項がとった値ごとに場合の数が記録してあれば、現在の項において取り得る値と場合の数が数えられる。それがわかっていて解けなかった。
もうね、「なんでなん？」という感想しかない。これが違うなら正解が正解ではないと言い張ることしかできない。
制約の下限が 0 なのは知っていた。知っていたしそのせいで Range の終端が -1 になることがあるのもわかっていたが、終端が始端よりも前にある「空の Range」で切り出した部分配列が、「空の配列」ではないことがあるだなんて想像だにしなかった。これは Ruby の罠である。こういうことだ。
range1 = 0..-1 # これで WA range2 = 0...0 # これで AC p range1.size #=> 0 p range2.size #=> 0 array = *0..9 p array[range1].size #=> 10 p array[range2].size #=> 0
配列の切り出しにおいて Range は単なる添字のペア [0,-1] として扱われている。Range としてのアイデンティティを奪われている。この仕様を知らなかったわけではない。ただ、認めがたい仕様なので自分では絶対に使わない仕様なのであり、意識の外だった。
D 問題を諦めたのに E 問題もコンテスト中の提出は叶わなかった。
やることははっきりしている。できるかどうかは別としてやるだけの問題。
「木において辺とは頂点集合を左右に分けるもの」だと前回の ABC に関連して書いたばかり。ある辺について注目したとき、A_i と A_{i+1} が異なる集合に属していれば A_i から A_{i+1} への移動に際してこの辺を通るのでカウント +1。
A_1 から A_2,..., A_m へと移動するとき辺ごとに何回通るかが数えられたら、今度は R−B=K を満たすような塗り方(辺の選び方)を数える。一度も通らない辺は青でも赤でもどっちでもいいので除外してあとで掛け合わせる。
原因は想像だけど、頂点集合の管理に 1000 ビットのビットフラグ×1000 を使って TLE。後半で謎の DP をして WA。
頂点集合の管理に UnionFind を使うことを思い出した。後半の DP はシンプルになって、辺を赤く塗った場合と塗らなかった場合を一緒くたにハッシュ表に詰め込むだけ。
1050 Byte は書き過ぎかなと思ったけど、他の Ruby での提出も軒並み 1001 Byte, 2162 Byte, 1019 Byte, 1776 Byte だったから別に突出してはいなかった。
前々回の ABC で見たのでこれを全方位木 DP と呼ぶことを知っている。そのときの経験でとりあえず根をとっかかりにすればいいことも知っている>20210928p01.01。根っこの特殊性は親がないことで、(子から親へ処理を積み上げているにも関わらず)親を参照しなければ求められない答えも、根に限れば求まる。そうすれば根を親に持つ子の答えも求まる。以下同様。
木 DP は処理の流れさえできあがれば、葉という一番単純で考えやすいところから差分で処理を積み上げていくと答えになるのでやりやすい。差分の部分の式が難しいことがあるし(20210909)、子のマージが難しいこともあるけど。
順調にジャッジが進んで行っていたのに最後の最後で次の一群のテストケースに阻まれた(06_n_eq_2_00.txt, 06_n_eq_2_01.txt, 06_n_eq_2_02.txt, 06_n_eq_2_03.txt, 06_n_eq_2_04.txt)。AC は近い。あそこが nil になりそうだなーと疑っている部分はある。
ABC が 12 時間のコンテストなら ABCDEF の６完も不可能ではない！(慰めはいらねーよ)
ゴルファー以外では Ruby で唯一の AC だった tinsep19 さんの提出 #26477920 を読んだ。
どうやら参照すべき日記を間違えていた。先月の 28 日(20210928p01.01)ではなくて、今月の 4 日(20211004p01)を参照すべきだった。全方位木 DP ではなく木の直径を解法とすべきだった。そっちの方が簡潔になるから。
関連問題である ARC022-C「ロミオとジュリエット」のスライドに２通りの解法が書いてあったらしいのをある参加者のブログで読んでいたが、わざわざややこしそうな全方位木 DP で木の直径を求める方法を知りたいとは思わなかったのだった。
知らずに実装していたし、知っていたのに(理解が浅くて)簡潔な手法を選べなかった。
振り返れば E,F がやるだけの問題だったこと、全方位木 DP、木の直径、どれも前回と前々回の ABC を彷彿させるものだった。どちらも復習はばっちりだった。その結果が３完とは泣かせる。
DFS ２回で直径を求めるバージョン。全方位木 DP バージョンと比べて、思ったより短くはならなかったけど速くはある。何より各ステップが単純でバグらせにくいと思う。
この単純さは、旅費が最大になる目的地の候補を予め２つに絞っているところから来ている。すなわち、直径(の１つ)の両端に位置する２つの街。
仮に木の中心がある辺にあるとしよう。すべての街が辺のあちら側かこちら側かに二分される。どの街をスタート地点に選んだ場合でも、中心を経由して、中心から最も遠く半径分だけ離れた街を目指すのが最も高くつく。中心を経由しないパスについては、中心に寄り道をするパスを想定して比較材料にすると、最も高くつくケースより安くなることがわかる。
最終更新: 2021-11-04T10:11+0900
精進ですよ。おとといあった ABC の F 問題。
コンテスト時間中は木の中心についての理解がぼんやりで解答に至らなかった。そもそも木の中心などというものを考えたことがなく、でもサンプルの２のような円形の木で制限時間内に答えを数えきるためには、木の中心を中心とした組み合わせを考えるしかなかった。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。後にそれが運任せではなく確かな手段らしいことを知った。証明は知らない。
木において辺とは頂点集合を左右に分けるものだということを知っている。どの辺でもいいので１本選んで真ん中に横向きに置いて形を整えるとアレイ(亜鈴)型になるイメージ。コンテスト中には思い出せなかった。そのせいで問題の木を具体的にイメージする力が弱かった。このことは今朝のトイレで考えるでもなくふと思い浮かんだ。
たとえば直径が偶数の時、直径の中心には頂点が１つある。問題は直径を与える頂点ペアが複数あるときに中心が複数あるかどうか。中心が仮に２つあるなら、２つの中心の中点が本来の中心であるべきであり、直径だと思っていたもの、２つの中心だと思っていたものは直径でも中心でもなかったことになる。だから中心は１つ。
たとえば直径が奇数の時。直径の中心には１本の辺がある。この辺は中心に位置する唯一の辺だろうか。仮に直径の中心に位置する辺が２つあるなら、２つの辺の中点が本来の……(略)。だから中心は１つ。
色の塗り方だけど、中心から最も遠く半径と同じだけ離れている点の集合を、中心から直接出るどの頂点の先にあるかで分類する(中心が辺なら辺が結ぶ２つの頂点を考える)。同じ頂点の先にぶら下がっている２点を同時に塗ってしまうと、そのあいだの距離は必ず直径よりも短くなる。直径より長くなることはありえないし、仮に直径と等しくなることがあるなら、真の中心はどこだ？という話になる。そんなものはない。
ここまでを今朝のうちに納得してから実装したのに、直径が偶数のケースで中心の求め方を間違えたり(提出 #26352819)、線形時間の集計を繰り返して TLE になったり(提出 #26353052)、無駄に長さ N の配列確保を繰り返して TLE になったり(提出 #26353383)、いっぱい間違えた。
配列アクセスとハッシュ表アクセスだと配列の方が断然速いのだけど、初期化が１度で済まないなら、ハッシュ表の初期化コストの低さが効いてくるみたい。
８問目の黄 diff AC。これより上は橙が１問だけだから、かなりのレア度なんだ。
ちなみに 水 diff だった E 問題 LEQ は、まだ TLE を回避する計算方法がわかっていない。
さっき書いた。
木の直径については知っている。(中略)。証明は知らない。
木の中心を念頭に置いて考えると直径を求めるアルゴリズムはこういうことだ。中心は、頂点の場合も辺の場合もあるけど、頂点集合を左右のどちらか(もしくは中心から直接出る辺のどれか)に振り分ける。任意の１点を始点に選んで最も遠い頂点を求める１回目の探索は、中心を挟んで異なる側にある、中心から最も遠い点を求めている。２回目の探索も同じ。同じ側に属する点が最遠点として選ばれることがないのは、中心に寄り道するパスを想定して比較材料にするとわかる。２回の探索で見つかったどちらの頂点も中心からは半径分だけ離れているから、そしてお互いに異なる側にあるから、合わせて直径になる。
さっき書いた。
木の直径については知っている。過去にある問題で満点解答のためのヒューリスティクスとして、深さを求める関数を２度呼び出して答えとしたことがあった。
エディタのログから「.max_by」を GREP したら該当するファイルが(たったの) 15 見つかったので、順番に調べてみた。「ある問題」とは ARC022-C「ロミオとジュリエット」だった。これが青 diff なんだからチョロい！(嘘です。調子乗りました)
最終更新: 2021-12-21T16:21+0900
昨日あった ABC。今回は全体に易化傾向で、D 問題がやるだけの茶 diff。F 問題でも水 diff。実は F 問題より E 問題の方が解かれていないけど、そちらも水 diff の範囲。ABC は５完６完を狙いたいところなんだけど、ABCD を 17 分４完(+うっかり余りをとり忘れて 1 WA)でレートは微減。あなたは残りの 83 分間何をしていたのですか？
こちらが先に解けた。やり方はすぐにわかる。１か所だけ素直に求めて、あとは辺の左右にあるノード数の差を見ながら差分を更新する。すぐに実装できたかというとそうはいかない。どういう処理をどういう順番で並べると答えが次々生み出されてくるのか、とっかかりが掴めなかった。結局、根を１つ決めると木に深さという概念が生まれて、根の深さを０にしておくと全頂点の深さの和が根にとっての答えになった。これがとっかかりになって最後まで書けた。
木の問題は深さと距離と子孫がそれぞれ Depth, Distance, Descendant なもんだから、いつも D が識別子として不足して困る。それに直径(Diameter)も追加で(ちなみにアクセントは i でも e でもなくて a らしいですよ)。
83 分間合わないサンプル２を合わそうとしていました。明らかに同じような計算がノードごとに繰り返されるので、累積和の累積和を表引きして TLE を避けるのだと思っていた。ところが実際は一番内部の式が定数になったので(たとえば 2^a × 2^{N-a} が a の値によらないようなこと)、愚直解だと思っていたものがそのまま答えだった。
しかしその愚直解を合わせるのにも一生分の時間がかかるように思われた。死ぬ前に解けて良かった。３つくらい勘違いポイントがあった。組み合わせを半分(それとも２倍？)扱いしなければいけないのはどういうケースか(同じ深さの２頂点を組み合わせて距離 D を作る場合ではない)、それは頂点何個分か(N,D に足し引きして求まる数ではないし冪(数)でもない)。
余りをとる数え上げ問題は正答までの距離が計れなくて途方に暮れがち。
愚直解っていうのは、深さごとに、頂点がいくつあるか、頂点１つが相対的深さ D の頂点をいくつ持っているか、相対的深さ 1 の頂点と D-1 の頂点をいくつ持っているか、相対的深さ 2 と D-2 ならいくつか……を数えて掛け合わせて足し合わせること。
E 問題も F 問題も青 diff でいいじゃないかというくらい苦労したけど、振り返ればどちらも考察は要求されていない(「すぐにわかる」「愚直解」)。ある意味やるだけの問題だった。やるだけ(できるとは言っていない)。
最終更新: 2021-09-30T13:08+0900
制約上の上限が 16 桁だっていうから、f の値の上限も 16。たとえば f(x) = 5 のとき、x は 11111 であるかプリフィックスが 111110 であるかのどちらか。f の値ごとに N 以下の範囲にそういう x が何個あるかを数える。桁数を固定すれば数えやすい。提出 #26096008
競プロ典型90問「025 - Digit Product Equation（★7）」の簡単バージョン。
頭の中がぐちゃぐちゃで解けなかった。終了直前の提出がこれ>提出 #26101512 (1 WA)。
とってもくやしいことに、１文字書き換えたら通りましたとさ>提出 #26105189 (AC)。２行目の N==1 を L==1 にしただけ。なんだよもー。もーもーもー。
一応考えたことを。最小化したい最大値の先頭の桁は２で決まっている。その後ろに０から N-1 までの N 個の数を３進数で表記したものをくっつける。これが２から始まる N 個の数。０から始まる N 個の数と１から始まる N 個の数は、桁ごとの制約を満たすようにテキトーに決める。これだけ。なんで書けへんの？ 他の人の提出を見ると tr で 0,1,2 をローテーションするのが簡単そうだった。簡単にできることをすごく難しく考えていた。
驚いたことに、このふがいない有様でレートは上昇しているのである(☞)。どれだけ低いレートに甘んじているかわかろうというもの。
最終更新: 2021-09-23T19:26+0900
昨日の ABC に続いて今日は ARC があった。
昨日と同じく ABC の３完(+2WA)。24 時終了でもう 27 時になりそうだけどまだ結果が出ない……(水色に戻れたの？どうなの？)
脳内で組み合わせを全探索して優先順位を付けて貪欲法で>提出 #25984785。
LIS が見えていなかったせいで配列に対して insert/delete_at を繰り返す効率の悪い実装になったけど、通るは通った>提出 #25988002 (911 ms)。
LIS ではないこの解答の形は「Shortest Path on a Line」と「蛍光灯」で書いていた>20200826p02。
LIS にすると倍以上速くなってこう>提出 #26015260 (440 ms)。
最初にサンプルの３にだけ答えを返すように if で処理を分けた。そうすると残りのケースで K の高すぎる上限を気にかける必要がない。
次に GCD について。砂で隙間を埋めるように１ずつの操作ができるとなると、GCD が取り得る値について A 数列の素因数から推測できることは何もないような気がしてくる。じゃあ探索しますか？
どうもね、N 回のループの中身を対数時間の処理にするということが、N^2 のループに対する高速化だという意識が強すぎて、N 回のループで前処理をして N 回の本番ループを定数時間で済ませる方が速いという感覚が持てない。N が２×N になってもオーダーは変わらないけど、ループを２本に増やすことに無意識の抵抗があるらしい。
残っていた 20 分で愚直解だけ>提出 #25995534。
RE と TLE の背後に WA が隠れている可能性がないではないが、「Shift and Inversions」でやったようにうまい遷移と、それと省略を見つけて高速化すればいいのかなと。