"月 日" という文字列の配列を全部生成してから真ん中を選んだんだけど、そこはさ、単に通年での day-of-year を数えておいて、文字列を生成するかわりに適切なタイミングで答えを出力すれば良かったじゃない。■C 問題「Flavors」。フレイバーごとにおいしさを記録してから異種組み合わせと同種組み合わせを考えた。ツイッターを見てると最大のおいしさが必ず採用されることに着目した解法が目立つ。そのアイスを２回食べてしまうミスにだけ注意すれば配列１本で処理できるのが魅力的な解法だと思う。ミスへの対処法は、必ず選ぶ１つを配列の先頭もしくは末尾の要素とスワップして、先頭もしくは末尾を探索範囲から外すのがいいかな。■D 問題「Magical Cookies」。最終的に E 問題の３分の１くらいしか正解者がいないいわくありげな問題。下手をするとすぐ TLE になるみたい？ 自分も 35 分と、E 問題より時間をかけて慎重にやっている。TLE 以外に小さな罠もあるにはあって、問題文に書いてある通りの手順を守らないと最後に残るクッキーが違ってくるような気がする。行を取り除くには２列以上、列を取り除くには２行以上残っていないといけないという条件から、残り２行もしくは残り２列付近で手順が最終結果を左右するのではないかと思う。手順を守るように途中で書き直したおかげかは知らないけど、というか書き直しだけなら５回も６回もそれ以上でも行きつ戻りつしていたのだけど、ペナルティを出さずに AC だった。TLE を回避する手段は、まだ残っている行番号と列番号を記録して使用することと、行と列にある文字の種類と数を記録して使用すること。■E 問題「Prerequisites」。スタックに積んで順番に読むだけ。WA を出したのはひとえにあほだからです。もう読んだフラグを立てるタイミングを間違えた。そのタイミングで何かするのを帰りがけ順っていうらしい(聞いたことはあるよ)。■F 問題「Shortcuts」。とりあえず DP で解けるのはわかる。制約が１万以下とよくあるものより１桁少ない。２乗で１億、定数倍２分の１で 5000 万。言語アップデートにより「倍早い」こともある Ruby-3.2 ならワンチャンあるかという数字。時間内に提出したものは TLE だった。ああ無情。■F 問題。悪いのはもちろん Ruby ではない。実は途中で必要に迫られて DP 配列の次元を増やしていた。O(N^3) にはどんなチャンスもない。ツイッターで見ちゃったんですよ、ペナルティは 50 回まで考えれば十分だと。見積もってみれば 28 ビットで上限を突破しそうだったので 30 を上限にしてみたら通った。O(30*30*N) だから 900 万のレベル。大枠は完成していたんだから時間内に通したかったねえ。SyntaxError: invalid identity escape in regular expression editor.bundle.min.js:1:882506」というエラーが出るのはブラウザが古すぎるせいかもしれないけど、ページのつくりとして、静的に完成したページを出してからデコレートしてほしい。そしたらデコレート部分がシンタックスエラーで壊れていても影響がない。提出結果ページにおいて不可欠のコンテンツが提出内容であるソースコードだということを忘れてほしくない。そして、コンテンツはマークアップ対象としてあるべきであって、属性値に置くのは筋違いだというのが原理主義的な意見。スクリプトがなくても、スタイルシートがなくても、タグがなくても残るのがコンテンツ。もっとも、最近そういうのは API をたたいて JSON なりなんなりで取得するみたい？■Twitter でも提出結果ページが壊れてるって報告が見えるので流動的だとは思うけど、とりあえずこれで>AtCoder-Submission-Page-Fix.txt。以前の提出結果ページとくらべて copy ボタンは機能しないし行番号もなくなったけど、それでも、最低限はある。ソースコードが読めるようにはなった。
4 4／1 2 R／4 3 B／4 1 B／3 4 R／RRRB。１と２の頂点は１番の辺で両方とも満足している。３番の頂点を満足させられるのは４番の辺だけ。４番の頂点を満足させられるのは２番と３番の辺だけど、２番の辺を使ってしまうと３番の頂点を満足させる方法がなくなってしまう。２番の辺と４番の辺は同じ２頂点を結んでいてそれぞれ異なる側を満足させる対称的な辺だけど、これに正しい優先順位を付けて使用しなければ答えを誤る。小数第 N+1 位で切り捨て」と書かれているのがミスリーディングだと思う(やつあたり)。切り捨てであってもないもの(N+1 桁目)を操作することはできないじゃない。考えちゃうよ。提出 #44490051 (AC / 142 Byte / 43 ms)。■B 問題「Roulette」。制約は小さいしやるだけではある。でもあまりやりたくない気分になる。見通しよく素直に実装すると３パスの操作になる。すぱっときれいに片付ける方法はないものか。考えた結果ソートなんてしてしまう人間(私です)は計算量についてイチからやり直そうな。提出 #44494576 (AC / 235 Byte / 44 ms)。■C 問題「Rotate Colored Subsequence」。色ごとに文字を積んでローテートして取り出すだけではある。でもケチなことを考えた。総要素数が N 個になる M 個の配列を作りたくないなと。要素数 M 個の文字配列だけで済ませたいなと。それで TLE を出しているのはただの間抜け。4-7 行目が良くなかった。提出 #44500699 (AC / 220 Byte / 158 ms)。TLE の解消方法がまだいまいち。reverse_each をやめても前から順に常に上書きするなら同じ結果が得られる。■D 問題「LOWER」。クエリ２と３があると文字列の大文字小文字がすべて決まってしまうのだから、文字列を直接書き換える他に、クエリ２と３の後のクエリ１についてだけ記録を残して上書きすればいい。例によって toupper やら tolower やら locase やらを試してとうとうリファレンスを調べた。upcase の反対は downcase らしいです。提出 #44506770 (AC / 266 Byte / 666 ms)。クエリ先読みが有力だったっぽい。■G 問題「Amulets」。問題の構図は比較的理解しやすく、データ構造の知識が問われる問題だった。持ち込むアミュレットの種類は後出しで選ぶ。どのように選ぶか。n 体目のモンスターまでで総ダメージが sa になるとする。モンスターのタイプ別でも総ダメージを記録しておく。タイプ別総ダメージが大きい方から k 個を選んでアミュレットでダメージを無効化するのが最善。その結果総ダメージが H 未満になるならいいが、H 以上になるなら n 体目のモンスターは倒せなかった。アミュレットの個数と倒せるモンスターの数は比例関係にあるので、アミュレットの数とモンスターの数を増やしながら答えを記録していく。たぶんだけどアミュレットは増加していく単一の集合ではないと思う。つまり、k=2 で選ぶアミュレットは k=1 で選ぶアミュレット＋１ではないと思う。だから BIT で都度都度最適な k 個を選ぶようにした。top k の総和を効率良く求めることがこの問題の中心だった。BIT にたどり着く前にはプライオリティキューを貼り付けたりしていた(でも行き止まり)。BIT で個数と総和を管理するのはついこの前 ABC312-F Cans and Openers でやったばかり>提出 #44067838。その問題にその解法は log が余分に付くうまくない解答だったのだけど、それが今日の解答のプロトタイプになったのだから怪我の功名。提出 #44529976 (AC / 1412 Byte / 1731 ms)。べつに今回が２回目ってわけでもない。ABC287-G Balance Update Query への提出 #38427641 でもやってる。
あくまで推測だが、おそらくこの誤タップ広告システムでサービスを提供している会社が存在し、」と第三の存在が推測されている。
require 'prime' とだけ実行してみたら 2525 ms かかって「マジかー」となったのだけど、その後は 55 ms 程度で落ち着いている。インタープリタ起動のオーバーヘッドがおよそ 40数 ms なので、require 'prime' にかけている時間は 10 ms 程度。まあ妥当。他にも require 'openssl' が数百 ms かかったのも確認したんだけど、次に確認したときは 55 ms になっていた。その次は 80 ms。require ひとつのために確率的に TLE になってペナルティを食らうのは嫌すぎる。■magurofly さんの全く同一ソースの２つの提出がこちら。#44334461 (1897 ms)、#44345492 (66 ms)。一度も呼び出されていないメソッドはコンパイルされないだろうから JIT ではないよね。じゃあ rubygems なのかと思うけど、require 'prime' にネットワークが関わる要素はないよね。ね？ じゃあどこで？ あるいはジャッジサーバーが？全ての情報が正しくなるように、全ての相異なる 2 人組にどちらが強いかを割り当てる方法が少なくとも 1 通り存在する」という制約から推移律を破るような循環する入力は与えられないと思ったけど勘違いだろうか。あるいは単純に計算量が見積もれていないだけだろうか。N≦50 だから４乗でも通るはずだけど。TLE の原因がわからない。Ruby で最初に提出された #44259309 (kuma_rb さん) の着眼点がすごい。負けなかった人が一人だけいたならその人が最強だと。トーナメントではそういう話を聞いたことがあるけどね(「優勝者とは唯一負けなかった者のことである」)。■C 問題「Approximate Equalization 2」。これは B 問題より簡単だった。平均として考えられる２つの整数(切り捨てと切り上げ)を考えて、A 数列のすべての要素について下げるなら下げる量、上げるなら上げる量を数える。下げる量と上げる量の大きい方が答え。上げるのと下げるののうち操作回数が余った方は２つの平均値のあいだを移動するのに使われている。■D 問題は答えを求める手順がわからなくて飛ばした。もし答えが絶対にわからないときの答え方が用意されていたら、まんまと「わかりません」と答えて WA をもらっていたところだった。■E 問題「Duplicate」。そもそも長さ１に収束するというのがけっこうなレアケース。S="22" でも永遠に短くならない。先頭の文字はどうでもいい。２番目以降の文字が操作後の長さを決める。１なら現状維持(ということは操作により末尾の１文字分減る)。２以上なら伸びる。しかし２から９までの数が２から９までの数を増やして伸びることはない(そうしたら収束しない)。２から９までの数が末尾に至って消滅するまでに何個の１を生成するかを数える問題。右側にある文字数と同じ回数だけ、決まった長さ(１から８)だけ伸びる。右側にある文字数が知りたいので末尾から(ほとんど１の)長さであり操作回数を数える。■D 問題「Odd or Even」。コンテスト終了まで考えていた F 問題 Flip Machines が解けなかったので終了後に D 問題に戻ってきた。N 回のクエリで数列全体の偶奇(の連鎖)が決まるのはわかる。たとえば A[1..K] の偶奇がわかって A[1..K-1,K+1] の偶奇がわかると A[K] を基準にして A[K+1] の偶奇が同じか異なっているか決めることができる。同様にして A[K+2] 以降も決める。A[1] から A[K-1] の偶奇についてもうまいことやって決める。ここからが問題だった。クエリ回数は上限の N 回まで使い切っている。A[K] の偶奇を基準にして同じか異なっているかはすべて判明しているが、A[K] の偶奇を決めることができるのかどうか。たぶんここで K が奇数だということが効いてくるのかな。最初のクエリを思い出そう。A[1..K] の偶奇がわかっている。そして A[K] を基準にした仮の偶奇について、１から K までの範囲の偶奇はどうなっているだろうか。一致しているだろうか異なっているだろうか。もう解けた。■コンテスト成績証。自分のすべての提出。D 問題も時間内に解きたかったけど、終了後に１時間かけているので惜しいところはなかった。それというのも人間ジャッジがときどきレスポンスの偶奇を間違えるからなのですね。解答のデバッグと並行していつの間にかジャッジのデバッグをさせられていたのでは時間もかかる。D 抜きでも青パフォが出たのは E 問題様様です。■F 問題について。N≦40 と制約はかなり控えめ。各マシンについてありうる未来はかなり限定されていると思った。操作しなければ２枚のカードについて {表表}。１回の操作で {表裏,裏表}、２回の操作で {表表,裏裏}、３回の操作で {表裏,裏表} これは１回の操作と同じ未来。それでどうする？
直方体同士は体積が正の共通部分を持たない」 だったら N 個分書き込んでも総和は 100 万以下じゃん！ 隣のマスを見たら隣接直方体がわかるやん！ 提出 #44116267 (AC / 553 Byte / 729 ms)。■延長１日を含めてこれもう実質７完でいいんじゃね？ やったぜ！(めでたい)■■■G 問題。現在見ている頂点を３つ組の真ん中の頂点だと考えて直線トリオを数える DP ができるらしい(最後に３つ組の全選び方から引く)。提出 #44139844 (AC / 303 Byte / 634 ms)。そうすると直線ペアの数を数える必要がなくなって、サイズと直線トリオの数だけを数えればよくなったけど、期待に反してわずかに遅くなった。400 ms、500 ms 台に入ると思ったのになぜ？ 実は答えを合わせるのにすこし苦労して、現在見ている頂点を３つ組の真ん中に決め打つということは、他の２頂点を選んでくるのは子方向の部分木だけに限らず親方向からも選んでこられる(16 行目)。その点がこれまでの２つの解答と異なっていた(これまでは現在見ている頂点が LCA になるような３つ組を考えていたので問題が子孫方向の部分木に閉じていた)。■E 問題。たぶんだけど、サンプルにわかりやすーい図解が付随していたら当日の AC がもっと多かったと思う。問題文を読んでも全然具体的イメージが構築できなくて苦労したもんね。まず直方体の対角線って何だ、とか。それは長方形の対角線とは(必ず)違うと考えていいのか、と。不等号(X1<X2, Y1<Y2, Z1<Z2)に意味を持たせすぎないでもっと文章で説明してくれていいのよ。辺が軸に平行だということも、え、それってどういう、という疑問からなかなか先に進めなかった。脳内直方体は歪んでいた(それは直方体ではなくない？ 菱餅？ そんなつっこみも出てきやしなかった)。■■■F 問題。自分の提出は BIT を使ったせいで余分な log がついて時間がかかっていた。よく考えて整理した結果、２本の累積和から M 個を取ったあとで綱引きをするようにした。要するに尺取り。提出 #44215202 (AC / 619 Byte / 389 ms)。最速級まではいかないけど BIT 版より倍は早くなった。じっくり整理したので規則的で理解しやすいと思う。S2 に前加工を施すと k1x の補正が必要なくなるし、無意味に缶切りを取得する前に試行を中断できるけど、それは TODO。