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 が解けなかった理由のひとつにはこの罠に気がつかなくて合わせるべき数字がそもそも間違っていたということがある。それがなくても解けなかったのもたしかだけど。
みんなで「いじめ」をゆるさない」。こういう全体思想、連帯思考がいじめの背後に構造的にあると思ってる。つまり、個々人がばらばらなら諍いがあってもそれは喧嘩と呼ばれるのであり、集団対集団でも別の呼び方があるとして、いじめと呼ぶときには被害者が個人であるのに対して加害者傍観者が集団として存在していることが想定されていると思う。群れがなければいじめは存在しない道理。それなのに「
みんなで」と連帯を呼びかけるとは。「
ゆるさない」という強い言葉で正当化される非難や暴力の存在を示唆するとは。怖いよ。いじめは人間関係の淀みなのであり人間を集団にすればそれも未成熟な人間を集団にすれば水が低いところに集まるように必ず生じるものだと思う。プレッシャーをかけて何が解決する。理想的には対話によって被害者の人間性が回復できればいいけど、それ以外には距離を取らせる、避難場所を用意する以外に何ができる。恐怖で支配する？ 全員を均質なロボットにする？ 人間の密度を下げる？(人間をふくらませるという意味ではありません)。密度を下げるのは衝突を減らすのに効果がありそうではある。
