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。区間最小値はセグメント木にお尋ねします。
まだだよ。
まだだよ。
入力に矛盾しない A が存在する」という制約により除外されている。潜在的バグはバグではなかったしテストケースにも不備はなかった。そこまで見切った上での割り切った実装(９行目の
if (1..N).all?{|n|)だったらかっこよかったんだけどな。ABC285-D「Change Usernames」のときも「入力制約のきれいさに助けられた」って書いてるんだよなあ。最終更新: 2023-02-08T02:07+0900
a = b = 0 # 初期化 a += b += a += 1 # 本題 p a #=> 1? 2?
右から順番に a に 1 を足して(a=1)、b に a を足して(b=1)、a に b を足して(a=2)、と考えると間違える。「自己代入」を読むと「この形式の代入は
」と書かれている。一番右の 式1 = 式1 op 式2 と評価されます。ただし、op が &&, || の場合には(略)a += 1 が評価される前に一番左の a += が a = a + と分解されていて古い a の値が評価中の式の値として一時的に記憶されているのだと考えられる。a の値は 1 になる。ちなみに C++ では 2 になった。
この前の ABC288-D が解けなかった理由のひとつにはこの罠に気がつかなくて合わせるべき数字がそもそも間違っていたということがある。それがなくても解けなかったのもたしかだけど。
