.keys 抜けが１つと L[] 抜けが３つだけと実装も素直。根からの距離を BIT で、LCA をダブリングで求めた。根からの距離をセグメント木で管理するなら LCA もセグメント木で求めたらいいと思う。BIT+セグメント木は無駄だし面倒すぎるのでナシ。だってセグメント木は BIT の上位互換でしょ？■提出 #39951562 (TLE×24)。試しにセグメント木で根からの距離の累積和と LCA の両方を管理してみたら派手に TLE だった。累積和は BIT でやる方が軽いのかな。■提出 #39954631 (AC / 3966 ms)。頑張りました。セグメント木にダミーの０番目の要素を入れて添字計算の微調整を省いたり、&:method 形式は Symbol#to_proc が呼ばれるせいなのか知らないけどやや遅いみたいなのでブロックを渡すようにしたり、せっかくセグメント木で累積和を管理しているのだから根からの距離を求めてから LCA を引き算するのでなく LCA からの距離を直接求めたり、オイラーツアーで作成する配列のサイズが 3N くらいになっていたのを節約して 2N に抑えたり。最初の AC だったなんちゃって HLD よりよっぽど厳しい。■モノイドが乗せられるようにまじめに ST クラスを改良したので、クラスを書く時のマイルールを。まずクラス利用者が知りたいであろう public インターフェイスを書いてから部外秘である private メソッドを並べる。public メソッドの中では、最初に呼ばれるであろうコンストラクタ(イニシャライザ)をまず書いて、つぎにアクセサ(読み取りメソッド)を書く。最後に、なくてもいい存在であり有害にもなり得るので書きたくないミューテータ(内部への働きかけ)を書く。クラスはオブジェクトのテンプレートであり、型通りの処理(不変部分)を書く場所だけど、ではオブジェクトのアイデンティティがどこにあるかというとコンストラクタへの引数でありインスタンス変数(メンバ変数)にふるまいを変える固有の値(可変部分)がある。すべてのメソッドがインスタンス変数に依存するべきだというのはそのため。その依存がないならメソッドの置き場所が間違っているサイン。とかとかいうことを考えながらクラスを書いている。あとはまあ名前だよね。よく言われるように名前重要。ソフトウェアという形のないものにはっきりした輪郭を与えるのは名前。適切な名前さえあればその実体をどう実装するかはどうとでもなるしどうでもいい。好きに、うまくやればいい。コーディング対象として適切な抽象に紛れのない輪郭を与える唯一無二の名前を見出すところが決定的に重要(形容詞増し増しで強調しました)。自分が常々疑問なのは、変数名に型名を使うというひとつの典型パターン(var arr = new Array; みたいな)。そりゃね、飼ってる猫が１匹だけならその呼び名はネコでも十分わかりますけどね、それは消去法や文脈でそう判断できるというだけであって、直接的な命名ではない。解釈や判断という余計なステップ、疑問や誤解の入り込む余地がある。クラスではなくインスタンスの、それそのものの本質を掴んだ命名をするのだ。■いやでも適切な命名は文脈に依存するということも言えるんだよな。識別子が機能するためには他と区別するのに十分な長さを必要に応じて使うのでいい。１文字変数を使い切ってから２文字３文字変数を使う、みたいな。ハフマン符号的な。その対極がたぶん Java の説明的で長ったらしい命名で、自分は HTML の p タグとか好きでいっぱい使いたくなる人間だからどちらかといえばアンチ Java なんだな。そのくせ、よそ者として文脈を共有しないで他人が書いたコードを眺めてるときに限って「変数名に型名を使ってる」とかを批判的に見てしまうわけだ。勝手な。p X を答えにしているが、正しくは p X%M。■終了後の提出 #39648781 (AC)。mod M の世界で A-1 で割りたいけど A-1 の逆元を掛けることができない。どうするか。以前にやってるんだよな。「L 問題だけが解けずに残っていた。余りをとる M が合成数でなければ 9 の逆元が使えて解けるんだけど」。Ruby なので (A-1)*M が 70 ビットになっても気にしないよ。D 問題で時間を使いすぎて 30 分ちょっとしか使えなかったのも悪かったな。■■■D 問題「Tying Rope」。ロープを分岐なしで繋いでいった結果、輪っかがいくつあるかと直線がいくつあるかを答える問題。それだけの問題。■最初の提出 #39629872 (TLE)。40 分かけてこねこねした謎処理が TLE になりました。■２番目の提出 #39631843 (AC)。その後７分ででっちあげた UnionFind が AC でした。どうして当たり前の問題を当たり前に解けないのか。■心当たりはある。道に迷ったとき、とりあえず引き返せばいいものを、前に進んで知っている道に出ようとする子供だった。来た道通った道を２度通るのは退屈なことだ。ABC292-D「Unicyclic Components」、ABC291-E「Find Permutation」、ABC285-D「Change Usernames」というように似たような見た目の問題が続いていたので、似たような解答を書くのには抵抗がある。それで間違えてりゃ世話がないってもんだけど。■提出 #39651186 (AC)。謎処理でも通しておきました。謎っていうか単に左右のノードをたぐるだけなんだけど、だけど、定型から外れた途端に間違えるんだなあ。■■■@2023-03-14 E 問題の問題名って等比数列の意味だったの？ 英語名難しすぎる(等比数列・等比級数が幾何～と呼ばれるためには何かエピソードが求められると思う。三角数……と考えてもみたけど、それはむしろ等差数列に近い)。そうすると A-1 で割るっていうのは等比数列の和の公式の分母にある r-1 (あるいは 1-r) のことだよね、たぶん。自分は A 進数で 111...1 で表される数字を 1000...0 から求めるつもりで式を立てたけど、意外な繋がりがあったもんだ(決してぼんやりしているから意外に感じられるのではない)。■■■@2023-03-14 D 問題に関連して Dancing Links という名前を初めて見たと思ったら、全然別のところでも Knuth 先生の名前とセットで見かけたりして。どうして今日一日だけそんなに有名になったのか。夜間に出荷したご注文は翌日発送扱いとなります」との定型文があるけど、これをどう考えればいいのか。■可能性１。発送メールの通りに発送されたあと２時間で届いた。■可能性２。夜間に出荷され注文ステータスの更新を見逃した。発送メール送信は翌朝に繰り延べられた。翌日発送扱いになるはずだけどヤマトがすっごく頑張って翌午前に届いた。■可能性３。発送メール前日(発売日当日)の日中には出荷・配送されていて、発送メール時点では配達拠点に届いていた。注文ステータスと発送メールが嘘。■さあどれだ。あるいは４番目があるか。■あとね、些細に見えて毎回導線の途切れにひっかかってしまうんだけど、出荷メールから注文履歴に飛べない。そこがすべての起点であるのに。１クリックでヤマトのページで荷物の追跡情報が見られないのも地味に残念。どちらに至らない点があるのかはわからないけど。
スマートフォンとケースを１つずつ買うと１１０ドルになります。スマートフォンの値段はケースの値段より１００ドル高いです。ケースの値段はいくらですか？」 １１０という数字を反射的にキリよく１００と１０に分けると間違える。こういう問題を 20230203 のときの簡易版職業適性テスト(Gテスト)の検査 C (数理)で見たぞ。残念ながらその手のひっかけは中１のときに散々間違えたあとだ(「100gの水に 5gの NaClを溶かしてできる食塩水の質量パーセント濃度は？」という問いに 5%と答えてしまうおバカな中学一年生でした」)。20230203 のときも実は一度ひっかかったけど逆方向に検算するのが習い性なので(答えを出す前に)訂正できた。以前に「ぶつかってそれではダメだと気がついたら定義に立ち返ってひとつひとつの手順を確かめながらたどるのが方法。ここでは注意が必要だと学習したから立ち止まって確かめることができるというだけで、失敗しないうちや失敗を回避できるようになれば、やっぱり中間を飛躍して答えに飛びつく高速のパターンマッチングの出番だと思う。それが人間の基本で、トライ＆エラーで最適化を重ねた結果が思慮や洗練として見えているという気がする」と書いた。2011 年のベストセラーらしい『ファスト＆スロー』(ダニエル カーネマン)がすごくおもしろそう。それでね、定型発達であることの不幸は、エラーに遭遇する機会の少なさにあると思うんだ。短絡思考を修正する機会に恵まれていない。■■■@2023-03-11 日本語の話。116 ページから「
20世紀前半の哲学者たちはヒュームの論述を深刻に受け止め、道徳的言説が論理に関するものでも経験的事実に関するものではないとしたら、いったいどういう意味があるのだろうかと悩んだ」。さて、この文は道徳的言説が論理に関するものであると仮定しているだろうか、そしてまた、経験的事実に関するものだと仮定しているだろうか。■「～でも～でもない」の形であれば迷いなく論理に関わるものではないし、経験的事実に関わるものでもないと読み取れる。では実際に見られたように「～でも～ではない」の形はどうだろう。自分は意味を変えずに次のように語を補うことができると考えている。「(たとえ)～で(あって)も～ではない」。そう書いてあるのだろうか。同ページの直前の文がこう「
確かに道徳的言説は、論理的言説とも経験的言説とも区別しなければならない」。論理的言説と経験的言説はそろって道徳的言説と区別されるべきものだと書いてあるのであり、道徳的言説が仮に論理的言説であっても、というのは話の流れに合わない。「～でも～ではない」をどう読み取れば良かったのだろうか。もとはの違いが大違いなのではないか。
Personal Identification Number (クレジットカードなどの) 暗証番号」だって。識別されるものは人ではないし(口座？)、識別に用いているのもカードであって数字ではない。PIN のどこに personal で identifying な要素があるのか。Card Number もしくは Device Number が相当では？
AB+CD=N」が４、５回読んでも理解できなかった。サンプルにヒントを求めても解答例が理解できなかった。つまり、A=12、B=34 だとして、AB=1234 だと読んでしまってそこから抜け出せなかった。A×B+C×D=N の意味ではないかとようやく推測できて、その解釈でサンプルが理解できることを確かめても、まだ半信半疑で問題に本腰を入れられなかった。問題文が難解。■D 問題「Unicyclic Components」。UnionFind をするついでに辺の本数を数えた。グラフの性質を踏まえたかっこいい解法で解きたいなと思ったけど、最近あほなので愚直にやった。■E 問題「Transitivity」。最初はダメ解法に捕まってしまった。こういうの。ある頂点を見て、入ってくる頂点と出て行く頂点の組み合わせを考える。すでに両者に辺が通っているなら操作はいらない。そうでなければ直通辺を足す。このやり方でやるとサンプルの３の答えが 17 と過大になってしまった。自分としては珍しいことだけど、そこで一旦リセットしてイチから別の解法を考えてみた(出口のない泥沼の数合わせに終始するのが見えてしまって瞬時にうんざりしてしまったのだ)。ある頂点から到達できる頂点というのは、必ず直通辺が通っていなければいけない頂点なのであって、距離２以上の頂点が操作の対象。有向辺なので問題は始点に選んだ頂点ごとに独立。足がかりに使う距離１の隣接頂点も無関係。N の２乗が通る制約なので全頂点を始点にして BFS をした。■F 問題「Regular Triangle Inside a Rectangle」。辺の長さが１の正三角形をちょっとずつ回転させて外接する矩形の大きさを調べた。そこから矩形の拡大倍率を求めたんだけど WA×10 が解消できなかった。二分探索をするのだと見かけてテキトーにでっちあげてみれば WA×43 と悪化していて AC が遠い。水 diff ですってよ。
i&-i で。部分集合の列挙は b = bits と初期化してから b = bits&b-1 で。メインはメモ化再帰。やりやすいからこういう方法でやったけど、必要以上にテクニカルなことをしているつもりだった。しかし TLE。■２番目の提出 #39380194 (TLE×1)。これのアイディアは１つで、左の子集合(L)と右の子集合(R)に L<R という大小関係を仮定して L>R の場合の再帰呼び出しを省いた。省いた分は ×2 で辻褄が合う。■提出 #39381113 (AC / 4266 ms)。これのアイディアは２つ。１つ目は前の提出のアイディアの改善。L<R を仮定しているのだから最初から列挙回数を半分にすればいい。２つ目はコードテストで数百 ms の効果があった(けれど単体では TLE 解消に少し足りなかった)チューニング。ビット列に対応した重さを予めメモする部分のコードで、いちいち各ビットが立っているかどうか調べるのをやめた。■(オーバーヘッドが大きい) Hash を使うメモ化再帰をやめて Array を使うボトムアップの DP に書き換えるとさらに改善するだろうけど、それは遷移がわからなくて書けない。最終更新: 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。区間最小値はセグメント木にお尋ねします。
まだだよ。
まだだよ。