AGC-A 13-18
を解いた。やはり、300点と200点の間には難易度に大きな壁があるように感じる。まあさすがに300も安定して解けるようにはなってきているが。
昨日から体調が悪い。そのクセそこそこ長期の旅行に出発してしまったので時間があまりとれない。
AGC 13
言われたとおり書くだけ
AGC 14
もらってくるクッキーが偶数 & 奇数という組み合わせが発生したら奇数になるので終わる。
今持っている枚数が4の倍数でなければ、渡すクッキーは奇数になる。
2つ偶数の和が4の倍数になるには、 両方が0 mod 4 or 2 mod 4である必要がある。
3人が同時に奇数となるパターンは、最初からそうなっているときのみ。
2人が同時に奇数になるパターンは、3人のうち一人が4の倍数、もう二人が2の倍数のとき。
1人だけが奇数になるのは、3人のうち二人が4の倍数、もう一人が2の倍数のとき。
クッキーの枚数の推移を見ると
A, B, C
B/2 + C/2, A/2+C/2, A/2 + B/2
A/2+B/4+C/4, B/2+C/4+A/4, A/4+B/4+C/2
2ターン経つと、自分がもともと持っていたクッキー/2 + 他の二人のクッキーの和/4が手元に入るという流れ。
無限ループになるa==b==c以外では、大した回数続かないように見えるので、実際にシミュレートして答えを出す。
AGC 15
基本的には、B-A+1個の可能な数字からA, B以外の未確定なN-2個を選べばいいが、和が等しい組み合わせを処理する必要がある。
和の大きい方から見ていくことにする。
A, B B B B …..が最大。
A, B-1, B B B B …がその次、
….
A, A, B B B … B まで続く。
途中でA, A+i, B-1, B…のような和を考えると重複が出る。
結局、未確定のうちで最小の値だけを減らしてAまで持っていくことを繰り返せばいいので、
1+(B-A) * (N-2)
入力例に a>bがあったりするの何がしたいんだ。
AGC 16
毎回、末尾かその手前の文字が消える。
後方の文字を前方にコピーしてくることはできるが、逆は不可能。
高々100文字で、26文字しか候補が無いのだから全て試せばいい。
100^2*26しかかからないはず。
文字を指定すれば、取るべき操作は明らか。
AGC 17
ビスケットが奇数個の袋と偶数個の袋がそれぞれいくつかを数える。
最初、それぞれの袋から好きな数だけ取っていい問題と勘違いしていた。
200点にしてはややこしすぎると気づくべき。
AGC 18
箱に入ったボールは増えていく。
箱に1が入っていれば、Aの最大値>=kで自明に作れる。
箱に1が入らないパターンとは何か。
Aの最小値での他のAのmodを考えると、その値までは少なくとも作ることができる。
さらにそれらの差を、と考えていくと、結局最大公約数？
ABC-C118も似ているが、絶対値を取って値を更新して、というタイプの問題は最大公約数ではという気付きにどれだけ早く到れるかが重要。
差を取っていって最大公約数というのは、ユークリッドの互除法がどのようなアルゴリズムかをちゃんと理解していれば自然な発想のはず。
AGC-A 1-12
をやった。
油断すると全然ダメ。
AtCoder Beginner Contest 119 & ABC-D 72-77
4回目のコンテスト参加。初回以来の全完。前回のリベンジは果たせた。
43分で4完の108th。
初の上限パフォーマンス1600を達成。上限解放してくれ。
レーティングは872 → 1047で1000台に突入。
デバッグに手間取って5分ほどロスしたのと、A問題でちょっと時間かかってしまった。pythonでsplitつかってサクッとやったほうが良かったかも。あと、正直D問題はもっと早く解けたはず。方針はすぐに立ったのに実装力とライブラリ知識の浅さで突っかかってしまった。
とは言え、全部一発AC通せたので良い。近傍順位は他はもっぱら青コーダーという感じで、緑の身で潜り込めて気分は良い。
順位表見てる感じでは、やはり皆さんDのほうが簡単という判断をしたようだ。全通り調べてやるという踏ん切りがつくかどうかが鍵だったように思う。想定解は全探索をdfsでやっている。
ratedな参加者の中では10位だったようだ。
4月までに水色になるという当座の目標、あと2回ABCで4完 or ARCでパフォ1800出せれば到達できそう。でも旅行とかで忙しいんだよな…。
以下、C, D解法。
C問題は、N<=8だったので全通り試せると判断し、数列 ell から i個使ってAを作り、j個使ってBを作り、k個使ってCを作るというのを全て列挙して計算した。
使用する竹の組み合わせが決まっていれば、それらで長さXを作るコストは 10*(本数-1) + abs(X - sum(使う竹の元の長さ))で一発で求まる。
実装はnext_permutationでゴリ押した感じ。全探索するという判断を下すまで時間がかかってしまった。計算量の感覚がもっとついていればすぐに動き出せたはず。
D問題は、クエリのかかった点の左右の寺と神社を一つづつ選んできて、それらの訪問順を8通り全て試せばいい。s, t, そしてそれらを逆順にしたものを用意して、lower_boundを使って左右の寺社を探せばいい。前回のD問題に比べると、同じ400点でもだいぶやりやすかった。前回がdpで食らいつけなかったというのが大きいけど。
以下、今日といたD問題の解答メモ。
わからないときはとことんわからない…。
ABC72
単純に左から決めていけるか？
条件を満たしていないもの(pi = i)については、隣接したものとswapすれば必ず条件を満たすようになる。
回数を最小化するには、自身の左と右のどちらとswapするかを決めればいい。
複数個連続して並んでいる場合には、それらの間でswapする。
基本は左から処理していけばいいが、最後尾が条件を満たしていない時どうするか。
左から処理した上で条件を満たさないということは、n-1番目は条件を満たしている。よって、そこでswapすればいい。
ABC72
R<=8なので、街を訪れる順番を全部試しても40000程度。
先にワーシャルフロイドで二点間を求めておけば、
Rから2点 ri, rj 選んだ場合に、他のR-2を経由する距離を求めて最小値を出せば良い。
異なる探索順の列挙はnext_permutationで。
ABC73
まず、Aijのうちで最小のものは必ず道に入る。
各 i について、Aikのうちで最小のものは必ず道に入る。
なぜならば、道の長さは正なので、より大きいものを経由してそのAikを作れないから。
この時点で、都市はいくつかのクラスターに分割されている。
次に、kの次に小さいAijを見る。
Aijについては、直接結ぶ or kを経由するのどちらかが最短。他を経由するより直接結んだほうが近い。
Aij < Aik + Akjなら直接結んだほうが良い。3番目については、Aik + Akl, Aij + Ajlと比較する… 繰り返し。
というか、単純にAijとAik + Akjを比較して、全てのkに対して見ればO(N^3)?
d[i][j] == d[i][k] + d[k][j]なるkが存在すれば、d[i][j]を直接結ばなくても良い。
Aijが最短距離になりうるかどうかについては、Aijに対してワーシャルフロイドしたときに更新が発生するかを見ればいい。
更新が無ければ少なくとも矛盾はない。
要素数がN^2だから全パターン調べたらO(N^4)で… という謎思考にハマってしまって時間を取られた。
ABC74
最適状態では、4辺それぞれに、少なくとも１つの点とのオーバーラップがある。
binom(50,25)はO(10^14)なので、全パターン試すのは無理。
ただ、binom(50,4) = 230300なので、辺に使う4点を選んで全パターン計算して、K以上を含むものの中で最小を探せばいい。
角に来るケースを考えると、x, yそれぞれで考えたほうが良い。
結局、長方形が指定されたときにその内側にいくつの点が含まれるかを調べればいいが、Nが小さいので全て調べても大丈夫。
ABC75
減速が間に合う範囲でとにかく最大速度を目指すのが最適。
時間を横軸、縦軸に速度を取れば、とにかく面積を最大にする問題。
最初の区間について考えると、
v1 > v2ならば、最終的にはv2以下になっていなければならない。
この場合、最大加速度でv2を超えられるかどうか。
v2を超えられるなら、v1に達しない限り加速し、t = t1で帳尻をあわせてv2にする。
v2を超えられないなら、ひたすら加速でいい。
v1 < v2ならばひたすら加速でいい。
とりあえずコード書いてみたが、入力例3のようなケースの処理が面倒。
次の区間だけ見る方針だとこのようなケースを処理できない。
区間 i を見ている時、 t{i+1} + …+tn >= v(t=t1+…+t{i-1})であること = 帳尻をあわせられることを保証しておけばいい。
区間終了時のゴール候補として、v[i+1]とt[i+1]…t[n]の小さい方を採用すればよさそう。
-> 入力例は全部通ったが、テストケースが全然ダメ。
想定通りの動きをしているように見えるのにWA。戦略が間違ってる？
-> 最後に帳尻が合うというだけでは不十分。その後の全ての区間で矛盾が生じないようにする必要がある。
区間iの終了時点の速度glは、 全てのj>iについて、gl - (tj-1 + … + ti+1) <=v[j]でなければならない。
すなわち、その後の全ての区間で減速し続ければ帳尻が合う事を保証しなければならない。つまり、gl <= min_j{v[j] + cumsum(v,j-1) - cumsum(v,i)}
WAがどうしても残ってしまう。心が折れた。
0.5刻みで見てやって、各時刻で許される最速値を取っていけば良かったらしい。
場合分けが多くなるとバグが確実に発生すると思ったほうがいい。
より実装がシンプルな解法を考える。
ABC76
ABC-Dで700点出るんか。
自明な最小の候補としてK自身があるので、まずKの桁和を求める。
高々何桁まで考えればよいなどがあればやりようはありそう。
桁和にはどのような法則性があるのか。
周期性があるわけではなさそう。
倍数を見ていった時、 kをn桁としたとき、 10^n * k以降は確実に桁和が大きくなると言えるのでは？
つまり、各kについて10^nまで見れば十分。kは最高で5桁なのでこれで回る？
-> k = 4が反例。他にも、k = 17で 5882353倍が最適だったり。
10^nしたところで、繰り上がりの影響は排除できない。
解法は、最短経路問題に落とし込むというもの。
givenな数字の桁和を求めるのではなく、その数字を1から構成していくという発想。
ある数字に1を足す or 10をかけるを繰り返すことで任意の数字を作ることができる。
1を足す操作に対応して重み1, 10をかける操作に対応して重み0の辺を張れば、
1からKの倍数への最短経路を求めれば良いことになる。
頂点たちはmod Kで同一視できるので、有限サイズのグラフになる。
1からスタートして遷移させていく。
全ての可能な状態からの遷移が、mod Kで同一視した整数に対してより大きい桁和を返すならば、そのさきの探索は打ち切ることができる。
なぜ mod Kで同一視できるのか。最終的に知りたいのは、Kの倍数、すなわち mod Kでゼロの整数の中でもっとも小さい桁和を持つもの。
mod K が同じものは、全て同じ回数だけ1を加える (and 好きな回数１０倍する)操作によってKの倍数になる。よって、遷移の仕方としてそれらは全て同じなので同一視してしまい、同じmod Kの整数の中で桁和最小のものだけを残して探索すれば良い。
さすがに思いつかんわこれ。
ABC77
二ターン以上は続かないように見える。
最後のカードを自分で引くか相手に引かせるか。
ABC-D 69-71
今日は3問だけ。
ABC69
縦に並べていって、なくなったら横にずれてまた縦に逆方向。
1 2 3 5 5
1 2 4 4 6
2 2 4 4 6
塗る順で1Dに書くと 1 1 2 2 2 2 3 4 4 4 4 5 5 6 7
ai個のiを順に1Dに書いて、2Dになるように読み出せばいい。
rep(i,h*w){
if(i/h %2==0){
ans[i%h][i/h] = color[i];
}else{
ans[h-1- i%h][i/h] = color[i];
}
}
ABC70
K始点でダイクストラしてdist[a]+dist[b]するだけ。
ABC71
左から i 列目がどうなっているか。
i-1が横向きドミノの二列目で
a
b
のとき、右側にあり得るのは
ac
bc
abb
baa
acc
baa
abb
の4通りで、後ろ３つは色の入れ替えで同値。
a
a
の時
ab
ab
ac
ac
abb
acc
acc
abb
の4通りで、前２つ、後ろ２つはそれぞれ同値。
横ドミノ1列目だったらそのまま。
結局i+1列目の塗り方は、
i 列目が横1ならi列目までと同じ。
i 列目が横2でi+1列目が縦ならi列目までと同じ。
i 列目が横2でi+1列目が横ならi列目まで*3
i 列目が縦でi+1が横なら *2
i 列目が縦でi+1が縦なら *2
0列目については、横なら6通りで縦なら3通り。
ABC-D 65-68
今日は4問。
問題文読み違えてたり、発想力を要する問題で、確信のない方針のままコード書いてそれにこだわってしまったり。
以下、解いていたときのメモ。
ABC65
辺のコストがマンハッタン距離であることが効きそうか？各点から伸びる辺の数を抑えたい。
実装重そう。500点で出るか？
計算量同じだけど想定解法はもっとシンプル。
というか、よく見たらコストがマンハッタン距離じゃなかった。
ABC66
1…nのうちで一つだけダブっている。
連続とは限らない部分列の個数。
各kについてO(1) or O(log n)で求められないと無理。
重複要素が無ければbinom[n,k]の和で良いが、
1 1 2で長さ2だと 1 2がダブルカウントされる。
重複要素をxとしたとき、一般に下のような並び。
. . . . . x . . . . . x . . . . . .
重複が発生しうるのは、
・２つのxの間に挟まれた領域から選ばず
・xのうち一方のみが選ばれる
ような場合。
各 k について, binom[n+1,k]をまず計算し、重複するパターンをそこから除く。重複は、binom[n+1-len[x…x], k-1]個
600点にしてはシンプルな問題だった。
ABC67
塗れる部分木を稼いたほうが勝つ。
根が塗られた部分木はどちらか一方のプレーヤーに占有されるので、お互いにとにかくまず最短経路を通って潰しにかかるのが最適っぽい。
まず1からNへの最短経路を調べて、両端から順に塗っていく。最短経路長/2回目で塗れなくなるので。1, N のそれぞれから、相手の色に出会わない限りという条件のもとでdfsしてマスを数える。多いほうが勝ち。
最短路を塗り終わるのが先手番か後手番かは気にしなくていい。
経路の重みが同じなので、最短路は幅優先探索で求められる。
ACは一発で取れたがずいぶんとごちゃごちゃしたコードになってしまった。
結局の所、1とNの近い方に対応する色で塗れば良かったっぽい。
考察もう一段深めるべきだった。
ABC68
とりあえず、aiの制約を考えなければ [k]が候補。
k > 10^16 + 1000の場合にどうするか。
[n-1 + n*(k/n) -(k-(k/n)), n+ n*(k/n) -(k-(k/n)), ….]
としてみる。
つまり均等に引く。
kがnの倍数であればこれで良さそう。
k = 100; n=1
0 + k - (k - k)=k
n=2
1 + 100 - 100 + 50
n=3
2 + 99 - 100 + 33 = 34
34 -> 4 + 10
[34,34,34]は 96回...
n個から一回ずつ引く操作によって、全体が -1される。
よって、kがnの倍数であれば、全ての要素を n-1 + k/n にすれば事足りる。
問題は中途半端な時。
n=3, k=9
2 + 3 = 5
[5,5,5] -> (3*3) -> [2,2,2]
n=3, k=10
[5,5,5]を[6,4,4]に -> (3*2) -> [4,2,2] -> [1,3,3] -> [2,0,4]->[3.1.1]->[0,2,2]
n=3, k=11
[5,5,5] を[11,2,2] -> 3 -> [10,1,1] -> [7,2,2]->[4,3,3]->[1,4,4]->[2,1,5]->[3.2,2]->[0.3.3]->[1.0.4]->[2.1.2] で11回。
k%n個に+k%n * 3, それ以外に-k%n?
少なくともkが小さい範囲では正しそう。確証は無いがジャッジに突っ込んでみる -> WA。kが大きいときに条件を満たす配列が存在しないということがありそう。
実際、入力499999999999999999に対して空出力になってしまう。
想定解は、終了状態から構成していくというもの。
"これを発想するのは難しいですが、これが以上の条件を満たすことを示すのはあまり難しくありません。"
NPかな？？？？
k%nが重要というところまで気づいた段階で、ノリで一つの要素に押し付けようとしてしまったのが間違い。
N = 50として、
44 45 46 47 48 49 50 0 1 ....
のようにして好きなk%nを作れることに気づく必要があった。
kの小さいところでもう少し紙とペンで遊んでみるべきだったか。
ABC-D 57-64
昨日までで、ABC-B, ARC-A,ABC-Cが終わったのでABC-Dに戻る。
むずい。ABC-Bが恋しい。
今週末もABCがあるようだ。
４月までに水色を目指したいが、前回の体たらくでは難しいかもしれない。
最近いろいろプライベート忙しいし。
以下解答メモ。
ABC57
数日ぶりにD問題に戻ってきたらWAを出しまくった。
方針は正しかったのだが、最大要素がa個以上あるときにどの範囲まで和を取るのかの部分でミスしたり、最大要素の個数を数えるのにわざわざ二分探索を使おうとして降順になっているのに比較関数をデフォルトのまま使おうとしてバグったり、二項係数の計算を行うのにdoubleでやって数値誤差で値がずれてやられたり。
教訓: 大きさが不安だからといって二項係数の計算をdoubleでやって最後にキャストするなんてことは絶対にしてはならない。誤差でやられる。
ABC58
x, y方向をそれぞれ予め処理しておけばok。
yの方で和を取るときに範囲を間違ってｍではなくnで指定していてREした。
コード内でコピペするときには細心の注意を払う。
ABC59
勝敗は石のとり方に依存する。つまり、最適にという部分は重要。
制約が巨大なのでdpではなさそう。
最終状態は(0,1) or (1,0)のみ。
場から石は毎回 i 個減っていく。片方の山からしか取れない。
(n,m)から最適手で(n-2i, m+i)に行ったとする。
他の動き、(n-2(i-k), m+i-k)を選んだとすると、相手は次のターンで(n-2i,m+i)にできる。
つまり、最大個数を取った場合に将来的に勝つ場合、それ以外の選択では負ける。
最大個数を取ったとき将来的に負ける場合、取る個数をi-k個にしてもその後で合わせられてしまう。
中途半端な個数を取ることでのみ勝てる場合はありえるか？
最大個数で負けるならやはり次のターンで合わせられてしまう。
結局、どちらかの山から最大個数取り続けるのが最適?
高々最初の1ターンしか無いので両方試す。
-> WA & TLE
WAはともかくなぜTLE?
一方に値が寄っていれば (n+m) -> (n+m)/2 -> …なのでlog(n+m)ぐらいのはず。
-> 初期状態として(1,1)の場合を考慮していなかった。
しかしWAの原因はわからないまま。
最大個数を取ったときに勝つならば、という部分を軽く考えすぎた？
相手がどのような行動を取ったとしても、という部分が取り入れられていない気がする。
|X-Y|>1ならAlice, それ以外ではBrownでいいらしい。
終了状態の近辺でどのように遷移が起こるのかをもっとしっかり分析すればよかったのかもしれない。
「最適に行動する」というタイプの問題では、
「負けが決定する状態[今回では (0,1), (1,1)]に１手で持っていけるなら勝ち」
という点を意識してみる。
制約が巨大であるところからシンプルな法則性がありそうという点に気づき、実験してみる。
ここでいう実験とは、紙とペンではなく、小さいサイズに対してdpなどで実際にシミュレートしてみること。
0の時後手が勝利、それ以外の時先手が勝利となるようなもの。
まず、終了状態に対して0を割り当てる。
遷移順を処理するのは面倒なので、実験する場合はメモ化再帰を使うとよい。
ゲーム問題は大抵の場合grundy数求めて法則性探る or ゲーム木探索でゴリ押すのどっちかという印象。
ABC60
w1 <= wi <=w1+3ということは？
入れる品物の個数がnのとき、
重量は n w1 <= sum{wi, n} <= n(w1+3)を満たす。
-> 入れる品物の個数がほぼ決まる。
N(w1+3) <=Wなら全て入れる。
(N-1)(w1+3)<=W <N*w1ならN-1個
N*w1とN(w1+3)の間はN-1個 or N個。
一般に、 n(w1+3)<=W < (n+1)(w1+3)となるnを見つければ
m = n個 or n+1個が最適(たぶん)。
品物の重さは、w1, w1+1, w1+2,w1+3の4種に分けられる。
それぞれの重さの中で価値の順にソートしておけば、重さごとの個数mjを
m = m1 + m2 + m3 + m4
を満たすように回して、重量がW以下の状態での最大価値を求めれば良い。
mは高々N<=100なので、このO(N^3)のループは回る。
とりあえず全てNまで回して、個数が足りなかったらcontinueで良い。
ループの境界値をミスして一度WAを出したが、割とスムーズに解けた。
ABC61
“最長”パスを見つければ良いので、重みを符号反転させて最短距離を出せばいい。
到達可能な閉路の検出が必要なのと、N <=1000なのでベルマンフォード。
重み反転したグラフにおいて1からnの間に到達可能な閉路がある場合、
ベルマンフォードのV-1回の更新のあとにもう一度V-1回回した時に1からnの最短経路長が更新される。
サクッと解けた。スニペット化してあったベルマンフォードを改造するのにすこし時間取られたが。
ABC62
a’の前半にできるだけ大きい要素を、a’の後半にできるだけ小さい要素を集めればいい。分割位置について探索する。O(N log N)でないとTLEするが?よーわからん。
プライオリティキューを使えば良かったらしい。
しばらくdp問題が来てない気がする。
ABC63
解がn回だったとすると、まず全体からB*n引かれる。
その上で体力の残っているものについて(A-B)をn回振り分けて引いていくことになる。
とりあえず、現時点で最大の値のものからAを、それ以外からBを除くことを繰り返せば良い。だが、制約的に、引く回数はO(10^9)になりうるので、各処理がO(1)でも間に合わない。
回数について二分探索して、その上で各 i について調べれば O(N log N)。
上限値は最大体力/B +1にでもしておけばいい。
ABC64
第一印象よりは面倒。
キャンセルされてない’)’と’(‘がそれぞれいくつかあるかを見ればいい。
例えば‘(‘に関しては、左から見ていって、’(‘に出会ったらストックを増やし、’)’に出会ったらストックを減らすようにする。
今日は7問。昨夜解いたABC-D57と合わせて8問。
飲酒してしまったのできょうは終わり。
ABC-B 1-41
ABC-B終了。
明日からABC-Dに戻る。
メモ
便利だからとdequeを使う前に本当にそれが有効かちゃんと考えたほうがいい。
例えば、ABC-B 23のように文字列を先頭と末尾に文字を追加しながら逐次的に作っていく問題は操作的にdequeが使いたくなるが、最終的に出力するにせよ他の文字列と比較するにせよ、dequeは不便。stringは t = “a” + t + “c” で連結できるのだからそちらがベター。
