脳log[2023-03-04～]

最終更新: 2023-03-03T18:23+0900

♪ [AtCoder] 第12回 アルゴリズム実技検定 過去問

自分のすべての提出

 A - 信号機

赤になってから Z 秒時点でボタンを押したら X 秒後に青に変わるけど、最低 Y 秒間は赤の時間が確保されているように。[Z+X,Y].max

 B - クレジット

正整数 を 100 で切り捨て除算する。桁数が 50 万と 1 になることがあるのでうっかり gets.to_i してはいけない。いや、案外平気かも。文字列として２桁削るのが無難だけど N が２桁以下のときに 0 を出力するのを忘れない。

 C - 偏ったサイコロ

出目の和ごとに場合の数を記録する DP。6×6×6×18 程度の計算量。

 D - 採点

辺の集合が与えられたときに多重辺と自己ループの有無を調べる。

強いて注意点を挙げるなら、多重辺を調べるときに文字列のまま比較すると 1 2 と 2 1 の同一性を見逃してしまうことと、隣接頂点リストを配列として持つと星型のグラフで多重辺のチェックが O(N) になってしまって全体が O(N^2) で TLE になってしまうこと。Ruby なら Hash で隣接頂点を管理する。

 E - 棒倒しゲーム

問題文に書かれている通りにスコアを消費していって、スコアに過不足がないかを調べる。

 F - 薬剤師

限られた数の薬と数限りないアレルゲンがある。薬が含むアレルゲンと人が持つアレルギーが交わらないようにするとき最も効果の高い薬の番号を答える。

制約を見ないと方針が決められない。薬は最大 100 種類。アレルゲン/アレルギーは最大 20 万種類。人は 10 万人。ただし人が持つアレルギーの総数が 10 万までに抑えられている。

人が持つアレルギーごとに使える薬を定数時間で調べて 1000 万の処理量。アレルゲンをキーにして 100 ビットのビットフラグで使えない薬を管理した。

 G - Wildcards

N が 1000 以下、L と K が 10 以下に抑えられているので、一致しているべき文字のインデックス(L-K 個)を決め打ってから文字列の集合を分類して絞り込んでいった。考えるのではなくうまく実装する。

 H - ３種の硬貨

問題文から読み取るべきこと。銀貨が有限だが無数にあると考えていい枚数ある一方、銅貨は X 枚に限られている。両替はできない。金銀銅の価値は差が非常に大きく、価値の大きい貨幣の多寡を価値の小さい貨幣でひっくり返すことができない。

なので、X 枚の銅貨をできるだけ多くの金貨に変えることをまず考え、金貨の枚数が同じ場合に使用した銀貨の枚数を少なくすることを考える。

そこまで分かれば銅貨の枚数ごとに金貨と銀貨の枚数を記録する DP をやるだけ。

 I - 毎日のリンゴ

悲しさを考える前にまず 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 個の悲しさをどう求めるか。一発で求まる式があるとは知らない」

n%c の区間をどんどん割って余りを取って効率的に数えられるような気はする。ユークリッドの互除法くらいの効率で。でも数字が合わない。

 J - スプリンクラー

長方形と円のどちらかがどちらかを含む場合を除けば、扇型の面積から直角三角形の面積を引いたり引かなかったりすることで水を撒く面積が求まる。

扇型の面積(s)の求め方。半径を r、弧を l とすると s = r*l/2。弧の長さ(l)の求め方。中心角(ラジアン)を θ として l = r*θ。中心角(θ)の求め方。三角形の３辺の長さがすべて分かっているので、余弦定理から中心角の cos が分かり、cos が分かれば acos 関数で角度が分かる。

ここまでわかればあとは場合分けを間違えないようにやる。

 K - 連結チェック

辺を繋いで連結判定をするのはおなじみ UnionFind で。辺を切断する方法は知らない。辺を繋ぐのが 10 回以下に制限されている一方、切断する回数はいっぱい。クエリを逆向きに処理すれば切断は接続に、接続は切断に変わる。10 回の切断をどうするか。UnionFind のデータ構造を丸々コピーしても 10 万×10 = 100 万だから許される。落ち着いて頭の中を整理して逆向きに考えられたら実装するだけ。

 L - 展覧会

ヒントを見たよ。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) の３通りから最大値を選ぶ。

 M - シリーズ

ある範囲のセット買いと単品買いを組み合わせて全 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。区間最小値はセグメント木にお尋ねします。

 N - 上からと横から

まだだよ。

 O - ２個のボール

まだだよ。

最終更新: 2023-02-08T02:07+0900

♪ [Ruby] Ruby クイズ (複合代入編)

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 が解けなかった理由のひとつにはこの罠に気がつかなくて合わせるべき数字がそもそも間違っていたということがある。それがなくても解けなかったのもたしかだけど。