AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

競プロ

Donutsプロコンチャレンジ2015 C - 行列のできるドーナツ屋

問題原文 atcoder.jp 解法 人 について考えている時、 いま見えている人の数を の答えとする いま見えている人のうしろから見て行って、 より小さいものは今後見えなくなるので削除 を今見えている人として末尾に追加 で解ける。 これはスタックを使うと楽に…

ABC170 D - Not Divisible

問題原文 atcoder.jp 解法 エラトステネスの篩っぽく、「 を割るような が何個あるか」を数える。 これは調和級数っぽい形になるので、実は ぐらいでできる。 ただし重複する数をそのまま処理すると、2 2 2 2 .... 2 2 2 をはじめとするパターンでTLEしてし…

ABC172 D - Sum of Divisors

問題原文 atcoder.jp 解法 普通に解けなかったので解説をガン見した。 キーとなる性質は「ある数 が 何かで割れると、答えが される」ということ。 で、例えば は当然どれも 5で割れるわけなんですが、これは答えに されるのと同じ。 つまり、等差数列の和の…

ABC172 E - NEQ

問題原文 atcoder.jp 解法 まず全パターンは、 「 個の数から 個選んで並べる」を「 と に対してやる」 ので、 通り。 ここから、ダメなパターンを引いていくことを考える。 ダメなパターンは「1つが一致しているパターン」「2つが一致しているパターン」…

ABC168 E - ∙ (Bullet)

問題原文 atcoder.jp 解法 実験とかすると、 は としていいことは分かる。(一旦0は無視で) これをとりあえず集計したくなる。 集計の結果、例えば が 個、 と仲が悪いものの個数が 個 ということがわかれば、 S からも Tからも選ばない S から1つ以上選…

CODE FESTIVAL 2014 予選B D - 登山家

問題原文 atcoder.jp 解法 ぱっと思い浮かぶのが、平衡二分探索木 + が大きいものから見て行って、すでに見たやつに対して二分探索。 とはいえ当方はPythonなので\(^o^)/になる。 ここから解説に載ってた別の解き方。 まず、「ある山小屋のより東であって…

ARC064 E - Cosmic Rays

問題原文 atcoder.jp 解法 スタートとゴールにも半径0のバリアが張られていると考える。 こういうのはグラフにできないかなと考えるとうれしい。 バリア内は自由に動き回れるので、「バリアの中に入る」ではなく「バリアの中心にたどり着く」ためのコストを…

ABC171 F - Strivore

問題原文 atcoder.jp 解法 解説放送があまりにも神だったので理解のためにこの記事をお読みになる場合はこちらをご覧いただいたほうが。。。 www.youtube.com 以下、振り返り & 反省 & まとめ です。 例えば、 abc とあって、各文字の間に文字を差し込んでい…

ABC E - Red Scarf

問題原文 atcoder.jp 解法 答えを、 とする。 両辺に をかけると、 になる。 これは、 が偶数なことより、右辺で各 が 奇数回あらわれるため。 これは一般化できるので、 としておいて、 を各 について行えばよい。 が奇数の場合には、 となる。右辺はあきら…

ABC171 D - Replacing

問題原文 atcoder.jp 解法 愚直にやると当然間に合わない。 あらかじめ全要素の和を計算しておいて、差分更新だけするようにやれば間に合う。 差分更新は各数の個数を持っておけばできる。 実装 from collections import Counter N = int(input()) A = list(…

ARC027 C - 最高のトッピングにしような

問題原文 atcoder.jp 解法 あるトッピングを交換する時、スペシャルチケットはなるべく温存し、普通のチケットを多く使いたくなる。 すると、最大でもスペシャルチケットの枚数分しかトッピングは手に入らないこと、それさえ守ればスペシャルチケットを普通…

ABC168 D - .. (Double Dots)

問題原文 atcoder.jp 解法 部屋1から幅優先探索をすれば、各部屋まで最小の移動回数で到達できる。 逆にいうと、それを辿れば各部屋から部屋1まで最小の移動回数で到達できる。 よって、次の部屋に移るタイミングで、今いた部屋の番号を次の部屋の道しるべ…

AGC041 B - Voting Judges

問題原文 atcoder.jp 解法 とりあえず降順ソート。 ついでに 上位 番以内に入るために最低限必要なボーダーも求めておく。 番目が採用されるような時、 番目も採用されるので、単調性があることがわかる。 つまり答えの境界を二分探索できる。 ここからは二…

CODE FESTIVAL 2015 予選A D - 壊れた電車

問題原文 atcoder.jp 解法 分で作業が終えることができる時、 分でも作業を終えられる。 つまり単調性があるので、答えを二分探索できる。 次に二分探索内の判定を考える。 これは左詰め(あるいは右詰め)をするように貪欲的に点検していくのが最適。 ただ…

Donutsプロコンチャレンジ2015 B - Tokyo 7th シスターズ

問題原文 atcoder.jp 解法 なんかすごそう。 入力がとてもとてもめんどくさそう。 少し落ち着いて見ると、 程度なので全部試せることがわかる。 実装 from itertools import combinations N, M = map(int, input().split()) A = list(map(int, input().split…

Code Formula 2014 予選B C - 仲良し文字列

問題原文 atcoder.jp 解法 3回のswapで影響範囲があるのは最大6文字まで。それより大きいと3回では足りない。 よって と が異なるindexを列挙しておいて、実際に3回のswapを全探索する。 の中に同じ文字が複数あれば、それらをswapすることで回数を稼げる…

東京海上日動2020 C - Lamps

問題原文 atcoder.jp 解法 1回分の操作はいもす法を使うことで でできる。 これを 回行うので、 、さてどう高速化するか。。。となるけど、実は愚直にやっても 回程度の操作で に収束する。 ので、実際には で答えを求められる。 のケースを手計算してたら…

ARC011 C - ダブレット

問題原文 atcoder.jp 解法 グラフ構築 + BFS + 経路復元、という問題。 グラフ構築 「1文字変えたら相手の文字列になれる」ような , を見つけ、その間に辺を張ってグラフをつくる。 単語の文字数は MAX30文字らしいので、愚直にやっても大丈夫。 BFS 辺のコ…

ARC040 C - Z塗り

問題原文 atcoder.jp 解法 上から & 右から優先でみていけばいいです! 右上残しても結局後から塗らなきゃならないからね!おわり! 実装 N = int(input()) S = [list(input()) for _ in range(N)] S.append(['o'] * N) # 番兵 ans = 0 for r in range(N): f…

ABC015 D - 高橋くんの苦悩

問題原文 atcoder.jp 解法 ナップサック問題発展版。「個数」という制約が追加されている。 やり方はいろいろあると思うんですが、 がなんか嫌な予感がしたので、「価値に対する最小の重さ」っぽくやりました。 詳しくは実装がわかりやすいかと。 実装 ちょ…

ARC034 C - 約数かつ倍数

問題原文 atcoder.jp 解法 制約が本質。 ↓こういう感じになってる。 実際に約数の個数を考える必要があるのは、 より上の部分。 これは最大でも100個なので、それぞれについて素因数分解しても全然間に合う。 実装 from collections import Counter A, B = m…

CODE FESTIVAL 2014 Easy C - 身体バランス

問題原文 atcoder.jp 解法 みたいなのがあるときには、真ん中を軸として考えると嬉しいことが多いんですが、今回は真ん中を全部調べる必要があります。 ということでダイクストラで からの最短距離と からの最短距離を調べておけば、各 について高速に判定が…

第三回 PAST M - 行商計画問題

問題原文 atcoder.jp 解法 の制約が小さいのがポイント。 訪れたい 個の頂点について、全点間最短距離は からそれぞれBFSをすれば求められる。 これで巡回セールスマンっぽい問題になったので、あとはbitDPで解ける。 実装 枝刈りしてないけど。。。まぁいい…

CODE FESTIVAL 2015 あさぷろ Middle B - ヘイホー君と削除

問題原文 atcoder.jp 解法 2つの文字列 と があったとして、削除のみを用いて にする場合、 と の最長共通部分列を残すのが最適。 よって をどこかで二分し、それらを , として最長共通部分列長を計算すればよい。 全ての切り分け方を試して、最小値が答え…

CODE FESTIVAL 2015 あさぷろ Hard A - 一次元オセロ

問題原文 atcoder.jp 解法 は奇数 と制約に あるので、 白, 黒, 白, 黒, 白 みたいになっている。 おける黒は両端のどちらかで、どちらかに黒を置いた後、白の選択は一意に定まる。 これで 左端に黒を置いた時にひっくり返す枚数(次の白の手番まで考慮) 右…

ABC169 F - Knapsack for All Subsets

問題原文 atcoder.jp 解法 → に部分集合 → の部分集合 みたいな構造をしている。 番目までみて として選んだものの総和が になるような通り数 とする。 ある に着目した時、遷移先は として選ばない としては選ぶが としては選ばない として選ぶ の3つがあ…

ABC169 E - Count Median

問題原文 atcoder.jp 解法 【注意】雰囲気証明なので間違っている可能性が十分にあります!!!あくまでも「こうsubmitしたくなる気持ち」の1つとして読んでいただければ 考えうる最小の中央値は、全ての区間について を取った時。これを とする。 考えうる…

ABC169 D - Div Game

問題原文 atcoder.jp 解法 の 因数であれば当然割り切れるので、素因数分解をしておきたい気持ちになる。 一度使った は二度使えないので、 を因数として持つ場合には、 と使っていきたくなる。 実装 from collections import Counter N = int(input()) def …

ABC169 C - Multiplication 3

問題原文 atcoder.jp 解法 少数を少数のまま扱うと誤差で死ぬ。 少数第二位まで与えられるので、 ×100をしてから大丈夫そうに思えるが、floatで受け取った段階で誤差が出てるので死ぬ。 文字列として受け取ってから変換すればOK! 実装 A, B = input().split…

ARC005 C - 器物損壊!高橋君

問題原文 atcoder.jp 解法 「2回まで壁を壊せる」→「壁に侵入するコストを1として、ゴールまでの最小コストが2以下なら2回までしか壁を壊してない」と言い換える。 辺のコストが0か1なので、01BFSが使える。 実装 from collections import deque H, W …