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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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