問題 https://atcoder.jp/contests/agc020/tasks/agc020_b 考え方 考えていたこと ナイーブに考えると 回目のラウンド前にいた人数を とするとラウンド後は となることは分かる。1 回目のラウンド前にいる人数を として を順に 回適応すると最終的な人数が決…

問題 https://atcoder.jp/contests/agc007/tasks/agc007_b 考え方 の場合は中央値になりえないので必ず NO になる。そうでない場合、例えば の場合は可能かどうかというと可能である。 で実験すると容易に分かる。 上の段の中央値になる場合の条件について考…

問題 https://atcoder.jp/contests/agc007/tasks/agc007_b 考え方 えー、難しい... の順列 の順番になるように を構築する。その際に は単調増加で は単調減少になるようにする必要がある。 いろいろな条件をいっぺんに考えることが難しいときは、ひとつずつ…

問題 https://atcoder.jp/contests/abc119/tasks/abc119_d 考え方 各クエリに対して ないしは で答えないといけない。神社用と寺用のTreeSet(二分探索木)に各 をあらかじめ入れておけばクエリごとにある位置 に対して左右にある最短の神社と寺の位置を求める…

問題 https://atcoder.jp/contests/agc004/tasks/agc004_b 考え方 典型っぽい。ある変数を固定すると、最適な操作が見えてくる問題。 何を固定するか？ 最小の秒数を 秒として二分探索 「 秒で全色のスライムを集めることができるか？」というYes/No問題に切…

問題 考え方 式だけみるとぱっと何を求められているかわからないので、まずはナイーブに の実装で実験してみる。そうすると区間の数について最小になる要素を求めて、その総和を求める問題であることが分かる。 さて、区間の数をまとめて計算したい。「最小…

問題 https://yukicoder.me/problems/no/794 考え方 きれいな問題で好き。 はソートしても問題がないのでソートする。マッチングする際に が大きい値ほど候補になる相手が厳しく、候補が絞られるので が大きい値から考えていく。 サンプル1 の場合ソート後の…

問題 https://atcoder.jp/contests/agc002/tasks/agc002_b 考え方 実験？？実験のコツがわかるようになりたい...。 赤いボールが入っている箱から 回の操作によって到達できる可能性がある箱については赤いボールが入りうる。ただし操作後に操作元の箱 x が…

問題 https://yukicoder.me/problems/no/793 考え方 うし数列を 10 進数で桁ごとに考える。例えば の場合、 となる。項をまとめるのに等比数列の和の公式を用いた。そうすると後は各項ごとに modつきの累乗を取り、 で割る操作は逆元を取れば良い。 #318620 …

問題 https://atcoder.jp/contests/nikkei2019-ex/tasks/nikkei2019ex_e 考え方 サンプル2から であることが分かっているので、これを利用する。 を満たす を とすると である。この結果の両辺に すると となる。左辺は の偶奇によって仮定の式を適応するこ…

問題 https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_c 考え方 難しいが過去にも300点で似たような問題があるので、点数は相応な気はする... どこに着目して考察するべきだったか まずは H 軸、W 軸ごとに独立して考えることにしよう…

問題 https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_e 考え方 考えていたこと グラフは連結であるから、ある頂点のコストを決め打ちすると頂点と辺の関係から他の頂点のコストが一意に決まることが分かる。なの…

問題 https://atcoder.jp/contests/code-festival-2018-final-open/tasks/code_festival_2018_final_d 考え方 考えていたこと 文字 の長さについて つの箇所を全探索というナイーブな考察以外に思いつかなかった...。 文字なので、真ん中を固定して全探索し…

問題 https://atcoder.jp/contests/arc058/tasks/arc058_c 考え方 考えていたこと 条件を満たす数列はどのような数列であるか考えた。 を全探索する。そのとき の区間の長さを求めておいて、各区間の長さの要素の和が なる要素の組み合わせを考えると、これ…

問題 https://atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_d 考え方 ある数 を 進数で表記したときにどのようになるか考えると解ける。つまり を 進数で表記したときに下の桁の数から で表されたとすると と表すことができる。 であるから につ…

問題 https://atcoder.jp/contests/arc068/tasks/arc068_c 考え方 これは難しい... 考えていたこと imos法で区間を含むか数える、がこれは重複して数えてしまうのでダメ。 を全通り試すことは でできるのでこれは全探索 解説見た 公式解説のベースに考えてい…

問題 https://atcoder.jp/contests/dp/tasks/dp_z 考え方 ConvexHullTrick を用いる。もらうDPを考えよう。 足場 に至るときの最小のコスト と定義する。この時DPの遷移は となる。 の部分は に関する1次関数と捉えることができて なる における1次関数たち…

問題 https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_d 考え方 まずは最小値に単調性があるので、最小値 を二分探索することにしよう。つまり以下の問題を考える。ディスク使用量をコストと呼ぶこととする。 「最小値を とすると…

問題 https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_f 考え方 操作の結果の文字列を考えていく。ある文字列が構成されていると仮定したときに次の文字を置くことができる場合は、赤/青のボールごとに考えればシンプルに求…

問題 https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_f 考え方 放送解説が秀逸。chokudaiさんが考察の進め方を解説している。 さて、まずは入力の数列をソートしても問題ないのでソートしておく。状態を定義するが、どのように状態を定義す…

問題 https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_b 考え方 差の最大値を最小化したい。これはよくある典型問題で、最小化したい値 を二分探索することで最小値を求めることができる。問題を言い換えると 「差を…

問題 https://atcoder.jp/contests/arc067/tasks/arc067_c 考え方 漸化式的な考え方でDPをする。難しい。 人未満のグループのみで 人を分ける場合の数 と定義する。 を用いると 人のうち 人はすでにグループが決まっているため残りの 人のグループ分けについ…

問題 https://atcoder.jp/contests/arc098/tasks/arc098_c 考えたこと だとするともとの数列 をソートして連続する 個の要素の最小値をとればよいことはわかった。これはしゃくとり法とかで でできる。 選べない数を除々に決めていきたいが、これは小さい数…

問題 https://atcoder.jp/contests/arc097/tasks/arc097_c 考え方 状態を決め打ちできるかどうかが一番重要な考察な気がする。つまり dp[i][j] := 左から [1,i] までの黒 'B' の数と [1,j] までの白 'W' の数が正しく並べるようにするときの最小のswap回数 …

問題 https://atcoder.jp/contests/arc061/tasks/arc061_c 考え方 まずは問題文の条件通り、路線ごとの駅にノードを対応させてグラフを構築する。駅と会社でそれぞれの頂点の役割が変わってくるので座圧の要領で拡張点に index を付与しておく。 同じ駅で会…

問題 https://atcoder.jp/contests/yahoo-procon2019-qual/tasks/yahoo_procon2019_qual_d 考え方 まずはすぬけくんが散歩する操作をシミュレーションする。そうすると散歩による操作を数列で表すことができることがわかる。その数列はある性質を持っていて…

問題 https://atcoder.jp/contests/arc081/tasks/arc081_c 考え方 基本的な考え方は放送解説がわかりやすい。 dp[i] := 位置 i 以降で条件を満たす最小の文字列の長さ とする。そのとき dp[i] = min(dp[next[i][j]] + 1) となる。next[i][j] は 位置 i 以降…

問題 https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_e 考え方 連結成分について連結した状態から、除々に辺を切断して非連結にしていきたい。UnionFindは頂点の連結しかできないがどうするか？という問題である。 逆に非連結の状態か…

問題 https://atcoder.jp/contests/abc117/tasks/abc117_d 考え方 考えていた解法(貪欲) bitのXORを考える問題なので、bitの桁ごとに考えていこう。bitごとに独立して考えることができる。 について という制約がなければ本当にbitごとに上から貪欲でOK。た…

問題 https://atcoder.jp/contests/soundhound2018-summer-qual/tasks/soundhound2018_summer_qual_d 考え方 解は なる 年それぞれについて解を出力する必要がある。各年度それぞれについてダイクストラをするのではTLEになる。 まず からそれぞれの都市への…