ABC309参加記録
Published on 2023-07-13Last Modified 2023-12-01
Table Of Contents
始めに
本稿は2023/7/8に開催された、ABC309の参加記録です。
戦績
今回の戦績を紹介します。 A, B, C, D, Eの5完で、 パフォーマンスが1130で、レーティング変化が964=>982でした。 以下は今回の提出です。
解いた問題
A - Nine
問題概要: 各マスに異なる数字が書かれている3*3の盤面がある。整数A, Bが与えられるので、横方向で隣接しているかをせよ。ただしA<Bが保証される。 また、盤面は以下のとおりである。
1 2 3 4 5 6 7 8 9
解法:
法則性を見るなら、Aが3の倍数の時、条件を満たすBをとることができない。したがって、必要十分条件はB-A==1かつA%3!=0となる。
また、あり得る入力のパターンが少ないので、解をすべて埋め込むのも手である。
B - Rotate
問題概要: N行N列のマスが与えられる。外周を一マス右回りに動かした結果を出力せよ。 次は操作の例である。
次が操作前のマスである。
0101 1101 1111 0000
次が操作後のマスである。
1010 1101 0111 0001
解法: 解法自体は言われたことをやるだけである。計算量的には全くネックではない。 ただし、インプレースで置換しようとすると面倒くさい処理が発生することが予測される。 そこで、マス目をコピーして、片方は読み取りだけを行うようにした。
ただし、高次元の配列を参照で持つpythonなどの言語はシャローコピーとディープコピーの違いに気を付ける必要がある。
D言語も単に代入をすると同じメモリを指す参照のコピーとなるので、プロパティ関数.dupを利用して確実にコピーをする必要がある。
C - Medicine
問題概要: N種類の薬を考える。薬iは処方された日を含めてa_i日間、毎日b_i錠ずつ飲む必要がある。 ここで、今日は1日目であり、すべての薬を処方された。 1日に飲む必要のある薬の総和が初めてK以下となる日を出力せよ。
解法: 薬を飲む量が減る日は全部でN日あり、それらはa_i+1日目である。よって、次のような解法で解くことができる。
始めに1日目に飲む必要のある薬の量を求める。これはb_iの総和である。 もし最初の時点でこれがK以下となっていれば、1を出力し終了する。 a_i, b_iのペアをa_iをキーにした昇順ソートし、a_iが小さい順にペアのb_iを総和から引いていく。 K以下になったとき、a_i+1を出力し終了する。 計算量はソートが支配的になり、O(NlogN)となる。
また、もう一つの解法としては、X日目に飲む必要のある薬の量がO(N)でわかるので、解についての二分探索で解くことができる。 計算量はO(NlogK)である。
どっちの解法も個人的にかなり好きであるが、二分探索のほうが汎用性がありそうだなと思う。
D - Add One Edge
問題概要: N_1+N_2頂点M辺の無向グラフが与えられる。ここで、次の条件が保証される。
1<=u, v<=N_1となるような任意の2頂点は連結で、 また、N_1+1<=u, v<=N_1+N_2となるような任意の2頂点は連結である。 頂点1と頂点N_1+N_2は連結でない。
次の操作を一度だけ行う。
1<=u<=N_1, N_1+1<=v<=N_1+N_2なるu, vを選び、辺を追加する。
操作を行った後、頂点1と頂点N_1+N_2間の最短パスの長さを最大化せよ。
解法: グラフは二つの連結成分に分けられている。したがって、連結成分内で目的の点から一番遠い点同士を結ぶことで、明らかに最大化することができる。 重みが均一なグラフのパスの長さはBFS(Breadth-First search)を用いて解くことができる。計算量はO(N_1+N_2+M)となり、ネックにはならない。
E - Family and Insurance
問題概要: N頂点の木が与えられる。いくつかの頂点は正の整数であらわされる「保険」を持っている。 頂点1を根として、「保険」を持つある頂点から距離が「保険」の値以下であり、かつその子孫であるようなノードは「被保険者」とする。条件を満たさないノードはは保険対象外である。
「被保険者」は何人存在するかを出力せよ。
解法: 保険の影響が親に波及することはない。したがって、根から保険の影響が及ぶかどうかを調べていけばよい。現在の保険の影響力が今いるノードの保険の影響力より小さい場合、より影響が大きいほうに乗り換えていけばよい。 実装自体はほとんどDFS/BFSそのものである。よって計算量はO(N+N-1)となる。
また、最も影響力の強いノードを優先度付きキューで管理する多点ダイクストラ法でも解くことができる。詳しくはこの問題の解説が詳しい。
終わりに
今回5問解くことができた。 最近ABCで調子が良いが、気を抜かずに取り組みたいと思う。 実際、F問題は全く解法が分からなかった。
毎回画像を張り付けるのはユーザビリティ的にどうかなと思っていたので、今回は問題の概要をすべてテキストで書いてみた。 今後のエントリのスタイルは検討中である。
近況としては、 電気通信大学からチーム「A.N.Serenade」でICPC国内予選に出場した。 この感想などもやる気があれば近日中にエントリを公開したいと思う。
また、このコンテストの翌日のARC164でかなり手痛い負けをしてしまった。 普段ARCのエントリは作成していないが、忘れないようにという意味も込めてエントリを書くかもしれない。
あとから読み返して気が付いたが、ですます体が混在していて最悪なことになってしまった。