Top
挑戦した問題一覧
ACしたけど不安の残る問題
AtCoder ABC043 D - アンバランス
:証明。"aa"や"aba"を含まないとき、アンバランスな部分文字列は存在しない
AtCoder ABC044 D - 桁和
:$b \gt \sqrt n$のとき、$n$を$b$進数で表すと$2$桁の整数になる
AtCoder ABC048 D - An Ordinary Game
:証明。最終的な文字列は必ず"ababab..."の形。長さの偶奇は一意
AtCoder ABC064 D - Insertion
:括弧列の問題。なんとなくで解いてしまった
AtCoder ABC065 D - Built?
:辺の候補を減らして最小全域木。1つの辺を2つに分解
AtCoder ABC078 D - ABS
:$O(1)$解法もしくは
ゲームDP
(メモ化再帰)
AtCoder ABC086 D - Checker
:実装難。市松模様の正方形内にある点の個数を求める
AtCoder ABC087 D - People on a Line
:UnionFind木の拡張かDFS。DFSのほうが楽
AtCoder ARC033 C - データ構造
:個数のRSQ。写経AC。Treapでも解けそう
Codeforces #568 (Div. 2) F. Two Pizzas
:小さな集合を扱うときはsetではなくbitを使う
Codeforces #569 (Div. 2) D. Tolik and His Uncle
:構築系は自由度が高い分、複雑な方法を選択しがち
Codeforces #570 (Div. 3) H. Subsequences (hard version)
:部分列DPに長さの情報を加える
yukicoder No.141 魔法少女コバ
:解は必ず存在すること、解が一意に定まることを証明していない
yukicoder No.451 575
:大きい要素と小さい要素が2つおきに交互に出現
ACしていない問題
AtCoder ABC076 D - AtCoder Express
Codeforces #568 (Div. 2) G2. Playlist for Polycarp (hard version)
:DPをうまくやって状態数を減らすっぽい
Codeforces #569 (Div. 2) E. Serge and Dining Room
:遅延セグ木を使うみたい
ACした問題
AOJ Lowest Common Ancestor
:ダブリングの要素数は$2^{k-1} \ge |V| - 1$を満たす最小の$k$
AOJ Queue
:キューの使い方を学べる問題
AOJ Stack
:スタックの使い方を学べる問題
AOJ Range Query - RMQ and RUQ
:遅延セグ木の練習問題。
提出コード
AOJ Range Query - RSQ and RAQ
:遅延セグ木の練習問題。
提出コード
AtCoder ABC042 D - いろはちゃんとマス目
:グリッド上での数え上げ。グリッドをグラフで表すと良さげ
AtCoder ABC045 D - すぬけ君の塗り絵
:盤面が大きすぎるときは、マスに注目する
AtCoder ABC046 D - AtCoDeerくんと変なじゃんけん
:(自分のパーの数)-(相手のパーの数)が最大得点
AtCoder ABC047 D - 高橋君と見えざる手
:最小値を保持しながら先に進む
AtCoder ABC049 D - 連結
:UnionFind木を2つ使う。map<pair<...>, int>を用意してペアをカウント
AtCoder ABC050 D - Xor Sum
:$(u, v)$と$(a, b)$を1対1対応させるルールを作って
桁DP
AtCoder ABC051 D - Candidates of No Shortest Paths
:ワーシャルフロイド
AtCoder ABC052 D - Walk and Teleport
:自明な貪欲
AtCoder ABC053 D - Card Eater
:優先度付きキューを使った貪欲。Editorialはもう少し考察を続けた解法
AtCoder ABC054 D - Mixing Experiment
:dp[i][j] := $A$が$i$グラム、$B$が$j$グラムのときの最小予算
AtCoder ABC055 D - Menagerie
:最初の2つを決めるとすべてが芋づる式に決まる。
inc()
と
dec()
AtCoder ABC056 D - No Need
:「$a_i$が不要なとき、それ以下の$a_j$は不要」を示す。あとは部分和DPと二分探索
AtCoder ABC057 D - Maximum Average Sets
:平均は自明。何通りかは、降順ソート後に$v_1=v_{A}$かどうかで場合分け
AtCoder ABC058 D - 井井井
:数式で表して$\sum$を分解し、2つ並ぶ$\sum$の計算量を落とすために数直線上で考察
AtCoder ABC059 D - Alice&Brown
:Win-Lose Algorithm
AtCoder ABC060 D - Simple Knapsack
:制約を見る。「重さ$w$の品物を$x$個選ぶ」の組み合わせを全探索
AtCoder ABC061 D - Score Attack
:ベルマンフォード。$2N$回ループすることで閉路を検知
AtCoder ABC062 D - 3N Numbers
:境目を全探索。インデックスをインクリメントしながら状態を更新
AtCoder ABC063 D - Widespread
:爆発の回数を二分探索
AtCoder ABC066 D - 11
:重複して数えたものを後から引く
AtCoder ABC067 D - Fennec VS. Snuke
:相手の邪魔をするのが最優先。両方向からBFS
AtCoder ABC068 D - Decrease (Contestant ver.)
:制約を眺めると、長さ$50$の数列が見えてくる
AtCoder ABC069 D - Grid Coloring
:蛇腹模様のようにグリッドを埋めていく
AtCoder ABC070 D - Transit Tree Path
:経由点からの最短距離を予め求めておく。木かつ正の重みなのでDFSでOK
AtCoder ABC071 D - Coloring Dominoes
:考察を重ねて乗算だけで済ますか、数え上げDPをするか
AtCoder ABC072 D - Derangement
:スワップ系。証明して貪欲
AtCoder ABC073 D - joisino's travel
:訪れる町の順序を全探索 + ワーシャルフロイド
AtCoder ABC074 D - Restoring Road Network
:迂回しても最短距離が変わらないような辺を取り除く
AtCoder ABC075 D - Axis-Parallel Rectangle
:長方形の辺上には必ず点がある。全探索。二次元累積和
AtCoder ABC077 D - Small Multiple
:正の整数は$1$から始めて$\times 10$と$+1$を繰り返して作れる。
DP解
AtCoder ABC079 D - Wall
:$i$から$j$に書き換える魔力の最小値をワーシャルフロイドで求める
AtCoder ABC080 D - Recording
:同一チャンネルの連続する範囲をまとめてからimos法
AtCoder ABC081 D - Non-decreasing
:操作は$2N$回行えることに注目。絶対値が最大の要素を使えば、2回の操作でどんな要素でも大小関係を逆転できる
AtCoder ABC082 D - FT Robot
:x方向とy方向を独立に考えると部分和問題の類題に。MLEに注意
AtCoder ABC083 D - Wide Flip
:
'0'
と
'1'
が隣り合うとき、片方を書き換える操作が必要
AtCoder ABC084 D - 2017-like Number
:素数判定。$1 \le n \le 10^5$の数をあらかじめ調べておいて累積和
AtCoder ABC085 D - Katana Thrower
:$a_i$と$b_i$は分けて考えられる。順番は無視できる。境界値に注意
AtCoder ABC088 D - Grid Repainting
:最短経路を求める必要はなく、最短距離だけでOK
AtCoder ABC128 E - Roadwork
:座標圧縮 + 双対セグ木が一番楽
AtCoder ABC131 A - Security
:文字列内の文字を参照できるか
AtCoder ABC131 B - Bite Eating
:難読
AtCoder ABC131 C - Anti-Division
:割り算の包除原理
AtCoder ABC131 D - Megalomania
:期限の迫っている仕事を先にやるという貪欲
AtCoder ABC131 E - Friendships
:グラフ構築問題は、最初に極端なグラフ(スターや完全グラフ、ライングラフ)を考えると良さげ
AtCoder ABC131 F - Must Be Rectangular!
:座標を二部グラフで表現。座標上の点は、二部グラフの辺に対応
AtCoder いろはちゃんコンテスト Day1 I - リスのお仕事
:最短距離が求まっても、seen=trueにしてはいけない
Codeforces #568 (Div. 2) G1. Playlist for Polycarp (easy version)
:巡回セールスマン問題を意識すると良さげ
Codeforces #569 (Div. 2) A. Alex and a Rhombus
:$\sum_{i=1}^n i^2$でOK
Codeforces #569 (Div. 2) B. Nick and Array
:最初に全要素をマイナスにしておくと楽
Codeforces #569 (Div. 2) C. Valeriy and Deque
:いずれ一番大きい要素が前に固定される
Codeforces #570 (Div. 3) A. Nearest Interesting Number
:全探索
Codeforces #570 (Div. 3) B. Equalize Prices
:最小と最大の差に注目
Codeforces #570 (Div. 3) C. Computer Game
:不等式を解く
Codeforces #570 (Div. 3) D. Candy Box (easy version)
:抽象化して優先度付きキュー
Codeforces #570 (Div. 3) E. Subsequences (easy version)
:hardと同じ解法
Codeforces #570 (Div. 3) F. Topforces Strikes Back
:「3個」に着目($k$個ではない)。場合分けして複雑さ軽減
Codeforces #570 (Div. 3) G. Candy Box (hard version)
:優先度付きキューと少しの工夫
yukicoder No.3 ビットすごろく
:ダイクストラで解いた。BFSとの違いがよくわかっていないっぽい
yukicoder No.59 鉄道の旅
:BITを使う。セグ木だと、BITの10倍くらい時間がかかる
yukicoder No.179 塗り分け
:平行移動の量を全探索
yukicoder No.652 E869120 and TimeZone
:日付に関する実装は意外と大変
yukicoder No.672 最長AB列
:$A=1, B=-1$として累積和