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$として累積和