最終更新: 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 点だけど難しかった。これが解けたのが嬉しくて今日の日記を書いているところがある。
とある赤い亀さんの日記を読みました。
学びのある問題だった。
俺も「とっぽい」って言ったら、どこの方言ですか❓って言われた事あるわ」ってコメントを見つけて笑っちゃったよ。自分が「とっぽい」という言葉を初めて見たのはスーパードクターＫで、それ以外では記憶にないよ。さておき、
「衒」は売る意」とあった。繋がりはない？ あ、『衒学始終相談』の２巻が来月発売です。これは競プロの話題なんですね。著者の人を知ったのが『レストー夫人』という別の作品を通してで、それをおすすめしていたのがたしか kinaba さんだったので。■以前にもちょっと書いたけど、自分は「
if is[is_j]<i%Sz に等号が付いていたこと。時間に追われる中でその微妙な差違に気が付くのは無理でしょう。なまじ解けただけに時間不足が残念でならない。■コンテスト成績証。青パフォでプラスではある。しかしものたりないなあ。このチャンスを逃した今、明日の ARC からまたもう何度目にもなる落ち目が始まる可能性だってあるのに。C*A[i]-A[i] で計算される。これの部分累積和が最大になる範囲を求める。場合分けはしない。判断をすれば判断ミスをするし、分岐すれば分岐した先それぞれでミスをするので。部分累積和の最大を求める方法だけど、名前が付いているらしかった。「Kadane's Algorithm | 最大部分配列 問題 - Ark's Blog」。名前で特定するより自分でひねりだすほうが簡単では？ ダイクストラ法もね、優先順位付き(重み付き) BFS という、実態に即した命名の方が理解を促す面があると思うんだよね、固有名詞で特定するよりもね。■B 問題「Bought Review」。星は増やすことしかできない。星を水増しして総数を増やすことに意味はない。それを確認すると無駄な情報が見えてくる。星３の数はいらない。星１２３を増やす選択肢もいらない。星１と星２を星４と星５で打ち消すための配分を考える問題。二分探索が頭をよぎって線形性を探したけど、実は星４を２つ増やすコストと星５を１つ増やすコストの大小で即座に優先すべき選択が決定する。ぴったり打ち消すのがいいか、１つ星を余らせた方が効率的にも絶対的にも得かは、条件次第で判断が分かれるところ。最適な式を探るより候補を３つ並べる方が簡単。■D 問題「Digit vs Square Root」。小さい N に対して答えを列挙してみると、答えが見つかる範囲が 10 の冪乗とそこからいくつか下った狭い範囲に偏っていることがわかる。1、10、9、8、100、99、98、1000、999、……といった具合。あとはがんばる。ランダム入力に対して愚直解法と答えを突き合わせて１時間20分かかった。つらい。実装しながら Project Euler の Problem 63 Powerful Digit Counts に似ているなと思っていた(20110308p01.02)。■日記を書いているあいだに結果が出た。コンテスト成績証。ARC にはレートを吸われるばかりなので、微増は勝ち。例えば 1,173,9090 は “Neq Number” です。」とあるが、１と１が並んでいるのに Neq Number であるとはどういうことかと、Neq Number の定義を何度も何度も読み直してしまった。この日記を書いている今気がついたことだけど、３桁区切りと４桁区切りが混在している不自然さを読み取らなければいけなかったのですか。■C 問題「Not Median」。どういうときに区間の幅が伸びていくかというと、ある数の左側にある数列が、ある数との比較において高低高低高低高低……と並んでいて、反対側には低高低高低高……と並んでいるときに、どういう区間を選んでもある数が中央値になることが避けられない。問題は、そういう均衡を破る最初の位置を効率良く見つける方法。過程を飛ばして結論を書くと、高高となる位置と低低となる位置を記録する２本の BIT を使った。高低は相対的なので処理順を１から N の順にした。そうすると最初は低低の位置はどこにもなく、すべての位置が高高の並びになる。これをスタートにして BIT を更新しながら答えを計算した。ところで、左右の端にある要素については効率良く数える方法がわからなかった。例えば入力が
4 3 5 6 2 1 7 で、４を中央値にしたくないとしよう。４との相対で数列を書き直すと 4 低 高 高 低 低 高 となる。高高や低低の並びを検索したとしても項数を奇数に揃えた途端に釣り合いがとれて４が中央値になってしまう。4 の左に低もしくは高のどちらでも存在していれば即座に答えが確定できるのだけど。だから両端の要素については線形時間を使って答えを出した。■B 問題「Make Many Triangles」はね、解ける人は 30 分くらいで解くみたいだけど(Ruby では２人)、自分にはさっぱりだった。３点以上が乗る直線を引いてグループを作ったとして、どういう規則でトリオを作っていけばいいのか、そういうやり方で答えが出せるのか、何もわからなかった。複数のグループに属する点の扱いもわからなかった。■■■@2024-03-14 B 問題。E8 さんの解説画像を見ました(それと類人猿の人の)。ダメなケースから考えていけば良かったみたい。たとえば、全てが一直線上に乗っているとき、三角形は１つも作れない。では１つだけ直線から外れていたら？ 直線上から２点を選んで１つだけ作れる。以下順々にくりかえし。直線上の点が先になくなったときは、直線上にない点を選べばいいんです(※)。テキトーに３点を選べば大体の場合において三角形は作れるんです。だから作れないケースから考えている。そのためには最も多くの点が乗る直線を１本見つければいい(※)。提出 #51223271 (AC / 272 Byte / 342 ms)。へー、なるほどねー。ネタバレを読んだあとではいくらでも知ったかぶりができますけどね。当日は早々に見切りをつけて C 問題に専念していたわけで、次にこのような問題が出るときも、やっぱり途方に暮れて全く手が出ないと思うな。■※を付けた２つの部分に飛躍がある。自分では超えられない飛躍が。たとえば直線上の点がなくなったとき、他に選べる点が他の１つの直線に乗っている点だけだった場合は？ わかりやすく２本の直線に半分ずつの点が乗っているとき、交互に２個と１個、１個と２個で組を作っていけば無駄なく三角形を作っていけることはわかるけど、いつでもこんな風にうまくいくだろうか。１本の直線にだけ注目して答えにたどり着くことが、やっぱりまだできない。",,,,,".split(',') は空になる。論理的な結果が欲しければ第二引数に -1 を渡せばいい。nil を足し算してランタイムエラーを出すのを避けるには .to_s する方法があるけど、自分の好みは文字列埋め込みかな。明示的な型変換はダサいと思ってる。他には文字列と配列の明示的な .dup も書きたくないものの例。なんでだろうね。文法的なキーワード(これも書きたくないもののひとつ)と同じく、形式的で冗長で、必要ではあるかもしれないけどノイズであり、自分が書いているロジックとは無関係だと思ってるからかな。もっとも、アプリケーションドメインとソリューションドメインの対比で考えると、形式的だろうが冗長だろうが足下の物理的側面を無視すべきでない状況があるのかもだけど。■B 問題「Delimiter」。Ruby が入力を改行区切りで与えてくれるので reverse して出力するだけ。■C 問題「A+B+C」。予め全組み合わせを試して作れる和を列挙しておける制約。判定は Hash で。Hash も二分探索も使わないのは横着なのよ。■D 問題「String Bags」。なんの工夫もなく試行して答えを出して許される制約。何回の操作で何文字目まで作れたかの DP。■E 問題「Insert or Erase」。効率的な insert/delete ということで、SortedSet がない Ruby の頼りになる味方 BIT の影がちらつくけども、次の要素/前の要素をポイントするリンクリストを構成すればいい。■F 問題「Earn to Advance」。制約が小さく見えるけど制限時間が４秒。パラメータが多くなりすぎるのをどうすれば良いのか。位置(i,j)、待機した回数、パス上の最大の P、所持金。所持金は必ず P 未満になるはずで、待機した回数が増えるほど所持金も多くないと割に合わないというあたりで候補を整理できそうに思ったが、それでは TLE×20 が TLE×14 になっただけだった。Array#bsearch_index と Array#insert でソート列を維持する仮実装でそれなのでまだ改善の余地はあるのだけど、それで TLE が完全に解消されるのかどうかがわからない。実装をがんばるより頭を使うべきところなのではないか。■■■@2024-03-13 F 問題。ルートを逆順に見ていきながら、待機数と残コストのペアを候補として記録していく DP をした。ゴールまでの残コストがわかっているので、各マスで即座に待機数を決めることができて、パラメータリストから経路上で最大の P というパラメータを消すことができる。提出 #51184903 (WA×9 / TLE×6) のち 提出 #51185273 (AC)。WA の原因は 22 行目と 25 行目にあって、十分に待機してみる候補が不足していた。TLE の原因は 26 行目にあって、配列を比較するソートが遅い。■十分に待機しない候補とは何かという補足。最初に候補として考えていたのは、まったく待機せずにコストを先送りする候補と、ゴールまでのコストを賄うのに１回だけ少なく待機する候補。これは何かというと、(1,1) から最大の P に到達するまでのパスで、待機して得た所持金と負担したコストの差分次第では、最大の P で待機する回数を１回だけ節約することができると思ったから。そういう例外的なケースに注目するあまり、最大の P で十分に待機するという当たり前のケースが抜けていた。■気になるのは、各マスにおける候補の数がどれだけ膨れ上がるかということ。22 行目と 25 行目を見て上か左に１マス移動するごとに３倍になると考えるなら破綻する。実際には待機数が増えたなら残コストは減らなければいけないという選択が働くので、待機数０の候補も残コスト０の候補もそれぞれ１つだけしか残らない。３つの候補のうち２つがそういうものだ。大体は効率的な待機と効率的なパスによって淘汰されると期待しているんだけど、待機数０、待機数１、待機数２、……と、ゾンビのように目のない候補が列をなして処理コストを引き上げる懸念がないではない。最悪の場合はどうなっているだろうか。ゴールまでのパスの数だけ候補があるという最悪のケースがありうるだろうか。その数は 2N から N を選ぶ組み合わせみたいな数になるんだけど。それよりは P や R、D の上限から待機数とコストの種類数が 10^9 に制限されている方が先に天井になるが、それでも解説と同じ O(N^4) にはならない。候補数の上限が N^2 で抑えられて初めてそう言えるが……抑えられるんですか？■さっき「待機数が増えたなら残コストは減らなければいけない」と書いたけど、現在のマスで待機して得られる所持金が p だとして、「待機数が ds 増えるなら残コストは p*ds 以上減らなければいけない」と主張しても良いのではないか。提出 #51204120 (AC / 1666 ms)。マイナーチェンジを無視すると実質的な変更は 26 行目のみ。条件式が２つ増えている。最初の AC が 2167 ms だったから、まあまあ早くなった。個別のケースを見ると４桁 ms かかっていたケースが１つを除いてほぼ 10 倍早い３桁 ms になっている。最後に残った４桁 ms が 1666 ms だということ。けっこう効いたね。そして、自分の解法はハックケースによって撃墜されうるものだったと、詰めの甘さが明らかになったような気がします。テスターさんの想定嘘解法に入っていなかったのでしょう。
require 'faster_prime' しているものを見つけた。なにそれ知らない。■E 問題「Last Train」。これは精進。パラメータが多くて頭が壊れてしまった。解法はすんなり出てくる。ゴールの N に到着する最も遅い電車を始点にしてプライオリティキューでダイクストラ法をする。しかしパラメータが多いのと、最短ではなく最遅を求めるというので、普段と勝手が違って無限にバグを生み出し続けて時間切れになってしまった。キューに入れるのは時刻と街のペア。たくさんあるパラメータはキューに入れる次の時刻を計算するために使う。あとはがんばって頭の中を整理すれば答えは合う。だけど昨日は、列車の運行を逆向きにたどっていることが合わさって、出発時刻と到着時刻の前後関係がどうあるべきなのかとか、判断をするその時刻に k 項ある等差数列の先頭末尾どちらの数字を使うのかとか、およそすべてのポイントで間違えた。■F 問題「Black Jack」。これも精進。昨日も今日も WA を出したがやっと AC が出た。まず、ディーラーの値 y が L≦y の範囲でどういう確率で分布しているかを知るために 0 から N まで DP をする。E 問題もそうだったけど、この問題も考えることが多くてこんがらかる。y<L の範囲ではサイコロを振るけど、L≦y の範囲では振らない。今 DP で求めようとしているある場所にいる確率というのは、同時に、サイコロを振って次の場所にいる確率を求めるために使う値にもなるのだけど、L を境界として両者が異なる値を取るということ。そこをきっちり区別しなければいけない。ところで、サイコロは D 面あり、DP のためには D 個の値の合計が知りたくなるが、愚直に合計するには D の数が大きすぎることがある。こういうことを１つのループの中で全部考えながら整理するのは非常につらい。今回も evall のとき(20240128)と同じように class を使った別解(#50640033)を書いた。解答の後半は前半とは逆に N から 0 に戻る逆順の DP をした。N にいるときがスタート。サイコロを振れば必ず負け、サイコロを振らないときは y=N の場合を除いて勝つ。y=N の場合の確率は前半の DP ですでに求めている。後半の DP でもサイコロを振った場合の勝率を求めるために D 個の値の合計が必要になるので、前半と同じ class を使って楽ができる。そのクラス(LastNSum)を読み直していたら、@first が完全に無意味なことに気がついてしまった。pop 操作があるなら意味があっただろうけど、ないのでいらない。■自分のすべての提出。レート遷移は知らない。どれだけ減ったかなんて知りたくない。x に隣接するいくつかの頂点からなる（空でも良い）集合 S であって、∑y∈SWy<Wx であるものを選び、S に含まれる頂点それぞれに 1 個ずつコマを置く」のシグマを見落としていて、Wy<Wx なるすべての y∈S にコマを配置できるものだと思っていた。残り 10 分でこの思い違いは厳しいが、幸いにもある頂点を選ぶ選ばないの愚直２乗 DP が許されていたので間に合った。うれしい。何番目まででいくつ選んだときの最大がいくつという DP が求められていたら無理だった。解法は、W が小さい頂点から順番に答えを計上する。それは配置されているコマ数×倍率。倍率を決めるために W が小さい頂点から順番に DP をしているし、ある頂点の倍率を決めるためにも W 未満の範囲でまた DP をしている。■自分のすべての提出。C 問題が解けていないことを除けば上出来。コンテスト成績証。1400 に復帰しました。1500 にもう一度のせて青を窺いたいところ。■C 問題。提出 #50395575 (C++ / AC / 637 Byte / 93 ms)。提出 #50396690 (Ruby / AC / 259 Byte / 66 ms)。Ruby が速すぎる！ コンテスト中にこれが通せないのはお前が抜けてるからだってはっきりわかんだね。■C 問題。Ruby で最初の AC であるこちらの提出 #50356929 を見ると、18 行目の
uniq! がポイントかなと思った。自分の TLE 提出である #50356164 が３行目でやってる文字列置換も目的は同じだけど、やり方が拙くて不十分。自分は経路の冗長性を取り除こうとしているが、経路をたどった結果の到着点の重複を取り除くことで冗長性を除くべきだった。だけどそのときは方法が思いつかなかったんだよ。理由もわかる。重複を取り除くためにはいったん配列などに溜めて並べて比較する必要がある。だけど自分の解答の構成はループを回して逐次的に移動先を更新していた。同時には１つの到着点しか存在していないのだから、それらを比較して重複を取り除くという発想が自然には出てこない。全体を俯瞰して最適な構成を考えることができなかったのは、問題の理解が浅かったからにほかならない。残念だね。