問題解説

  • 別解法
  • 同じ解法でも異なるアプローチでそこに至った場合
  • 公式解説が存在しない問題

などについて、書いていっています。

公開日 コンテスト 問題 関連分野
2022/10/29 yukicoder No.2114 01 Matching slope trick 凸共役
2022/10/15 yukicoder No.1216 灯籠流し/Lanterns 木クエリ
2022/10/15 yukicoder No.1763 Many Balls 指数型母関数
2022/10/10 yukicoder No.1379 Postponed
2022/09/19 yukicoder No.1353 Limited Sequence
2022/09/14 yukicoder No.1292 パタパタ三角形
2022/05/23 tenka1-2013-final E – 天下一折れ線遊戯
2022/05/11 s8pc-4 G – Get the Salary of Atcoder
2022/05/11 yahoo-procon2017-qual E – 遊園地
2022/05/05 yukicoder No.1594 Three Classes
2022/05/01 yukicoder No.925 紲星 Extra
2021/06/26 gigacode-2019 G – ギガ国の道路事情
2021/06/23 jag2015summer-day2 J – 連結
2021/06/21 ijpc2012-1 A – むこのどうぶつたちとしんりんはかい
2021/06/20 abc206 E – Divide Both
2021/06/12 pakencamp-2018-day2 G – グランド・グラフ
2021/06/12 code-festival-2014-china J – XORAND
2021/06/12 code-festival-2014-china I – Obstruction
2021/06/12 code-festival-2014-china H – Dungeon
2021/06/12 code-festival-2014-china G – Ammunition Dumps
2021/06/12 code-festival-2014-china F – Yakiniku
2021/06/12 code-festival-2014-china E – Game
2021/06/12 code-festival-2014-china D – Maze
2021/06/11 pakencamp-2020-day2 H – 旅立ちの日に Heuristic
2021/06/11 maximum-cup-2013 G – King’s Ring Tower
2021/06/09 tkppc J – 仕事をしよう! 木クエリ
2021/06/06 joisc2018 J – 飴 凸関数
2021/06/05 utpc2014 L – セミ時雨ハッシュ
2021/05/31 wupc2nd H – ダイヤグラム
2021/05/31 wupc2nd F – 僕は宇宙人
2021/05/31 k2pc-hard E – 暗号化
2021/05/31 k2pc-hard D – マシュマロ
2021/05/30 k2pc-hard C – お気に入りの数2
2021/05/30 k2pc-hard B – 虫歯
2021/05/30 hbpc2012 A – 1→1
2021/05/23 fuka5 G – Graph Cut
2021/05/23 fuka5 F – IRU vs SAKI
2021/05/23 fuka5 E – すごろく
2021/05/23 fuka5 D – Bintree
2021/05/22 NYC2015 M – お絵かき
2021/05/22 autumn_fest J – Ninja of Train 行列累乗・線形漸化式
2021/05/22 dwacon2018-final D – ニワンゴくんとゲーム
2021/05/22 tenka1-2013-qualb C – 天下一ジグソーパズルふたたび
2021/05/21 jag2017autumn J – Farm Village slope trick 凸共役
2021/05/21 yukicoder No.309 シャイな人たち (1)
2021/05/20 wupc2019 I – Ramen クエリ平方分割
2021/05/20 k4pc G – 42 凸関数
2021/05/20 jag2014summer-day4 H – トーナメント
2021/05/09 xmascon18 I – Interesting Equation 乱択アルゴリズム
2021/05/07 abc107 D – Median of Medians 転倒数
2021/04/18 rco-contest-2017-qual A – Multiple Pieces Heuristic
2021/04/15 rco-contest-2019-final B – まわしてそろえる Heuristic
2021/04/13 joisc2010 simroad – シムロード Heuristic
2021/04/12 code-festival-2015-okinawa H – Happy 2015 数え上げ
2021/04/12 utpc2011 L – L 番目の数字 木クエリ
2021/04/12 ttpc2015 N – 何かグラフの問題 双対問題
2021/04/12 joisc2012 broadcasting – テレビ放送 Heuristic
2021/04/12 joisc2011 ufo – UFO の飛行場 Heuristic
2021/04/12 joisc2008 election – 選挙 Heuristic
2021/03/27 code-festival-2015-exhibition A – 高橋王国と青木王国 最小カット
2021/03/15 ArCoder, arc114 E – Paper Cutting 2
2021/03/15 AtCoder, arc114 C – Sequence Scores
2021/03/04 jag2017summer-day3 K – Permutation Period クエリ平方分割
2021/02/27 jag2014summer-day4 D – 夕食 式変形
2021/02/24 pakencamp-2018-day3 H – 整数をつくろう! Heuristic
2021/02/23 dwango2015-honsen D – コインの取り合い 式変形
2021/02/23 TTPC2019 L – 多項式の零点の個数 中国剰余定理
2021/02/14 AtCoder, yahoo-procon2018-final D – LCP(prefix,suffix) Z アルゴリズム
2021/02/14 jag2013summer-warmingup B – Cans of Toys 線形漸化式・計算誤差
2021/02/13 jag2015summer-day2 I – ツインリバース
2021/02/12 joisc2010 plugs マッチング
2020/08/01 AtCoder, NYC2015 L – 机のしみ Gauss 整数環
2020/05/19 yukicoder No.856 増える演算 計算誤差
2020/05/19 yukicoder No.869 ふたつの距離
2020/05/03 yukicoder No.691 E869120 and Constructing Array 5
2020/05/02 yukicoder No.1042 愚直大学
2020/04/14 yukicoder No.803 Very Limited Xor Subset
2020/04/09 yukicoder No.42 貯金箱の溜息 多項式・形式的べき級数
2020/04/08 yukicoder No.886 Direct
2020/04/08 yukicoder No.262 面白くないビットすごろく
2020/04/07 yukicoder No.161 制限ジャンケン 最小費用流
2020/03/23 yukicoder No.918 LISGRID
2020/02/13 yukicoder No.984 Inversion
2020/02/12 AtCoder, agc013 E – Placing Squares 多項式・形式的べき級数
2020/01/02 yukicoder No.540 格子点と経路
2019/12/19 AtCoder, arc019 D – ほんとうのたたかい 有限体上の射影平面
2019/11/23 AtCoder, agc018 E – Sightseeing Plan 二項係数・多項式
2019/11/18 AtCoder, agc001 E – BBQ Hard 二項係数・多項式
2019/11/10 AtCoder, arc003 C – 暗闇帰り道
2019/11/10 AtCoder, tanka1-2015-qualb C – 擬二等辺三角形 多項式補間
2019/11/10 AtCoder, kupc2019 K – One or All 多項式・形式的べき級数
2019/10/22 AtCoder, cf17-final F – Distribute Numbers 有限体上の射影平面
2019/10/19 AtCoder, s8pc-3 G – フィボナッチ数の総和 多項式・形式的べき級数
2019/10/09 AtCoder, cf16_exhibition_final H – AB=C Problem 線形代数
2019/10/04 AtCoder, jsc2019-qual E – Card Collector マトロイド
2019/08/25 AtCoder, jsc2019-qual F – Candy Retribution 多項式・形式的べき級数

その他、AtCoder ユーザー解説機能で投稿したもの

別解っぽいものの他、公式の想定解法が見当たらなかった場合にときどき書いています。

CODE FESTIVAL 2014 エキシビション A – パズル
CODE FESTIVAL 2014 エキシビション B – かっこつけ
JAG Practice Contest for ACM-ICPC Asia Regional 2012 H – Magical Bridges
JAG Summer Camp 2014 Day 4 C – Magic Bullet
JAG Spring Contest 2015 A – Balanced Paths
2009年 日本情報オリンピック春合宿 OJ logo – ロゴマーク (Logo)
IOIer Japan Programming Contest 2015 B – カードゲーム 
天下一プログラマーコンテスト2013 決勝 B – 天下一マジック
スポンサーリンク
問題解説

[yukicoder] No.2114 01 Matching

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 解法 $K=1$ に帰着します。次のような問題が解ければよいです。 点 $X_0, \ldots, X_N$ ($X_i \leq X_{i+1}$)がある。各点は...
問題解説

[yukicoder] No.1216 灯籠流し/Lanterns

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 公式解説よりも計算量が良いので、書いておきます。 解法 消灯への対応 $v$ を出発した灯籠が、$w$ から先では消灯しているとします。このとき、 $v$ か...
問題解説

[yukicoder] No.1763 Many Balls

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 割と素直な解法だと思いますが、少し公式解説と違うのかな?大差での Fastest AC にもなったので、書いておきます。 解法 $p = 90001$ とします。$K = 60...
問題解説

[yukicoder] No.1379 Postponed

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 公式解説では、最小値の挙動に注目しています。私は最大値の挙動に注目して解いたので、解説しておきます。 私の解説では、$A_i+1$ のことを改めて $A_i$ と呼ぶこと...
問題解説

[yukicoder] No.1353 Limited Sequence

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 想定解法よりも計算量が落ちたようなので、一応書いておきます。$O(R\log R)$ 時間で解けます。 解法 $a$ を $1$ 個以上 $k=A_a$ 個以下並べ...
問題解説

[yukicoder] No.1292 パタパタ三角形

概要 問題文 → ■公式解説 → ■自分の提出 → ■ Fastest AC 記念 解法 まず、正三角形を次のように座標空間内に配置します: $A(1,0,0), B(0,1,0), C(0,0,1)$. $A$...
AtCoder

天下一折れ線遊戯(天下一プログラマーコンテスト2013 決勝 [E])

概要 問題文 → ■公式解説 → あるのか不明自分の提出 → ■ 解法 LGV 公式を使います。 参考:ABC 216 H 解説() 可能な線分すべてを考えてしまうと、線分に交差が生じる場合があります(サンプル 3...
AtCoder

Get the Salary of Atcoder(square869120Contest #4 [G])

概要 問題文 → ■公式解説 → ■, p.86自分の提出 → ■ 解法 Euler Tour をとって、Euler Tour における頂点順を $x$ 座標、木における深さを $y$ 座標と見なすことで、次のクエリ処理に帰着...
AtCoder

遊園地(みんなのプロコン 2017 [E])

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 公式解説も面白いけど、こっちの方が分かりやすいかな? 解法 解説同様に、次のように辺を張ったグラフを作って強連結成分分解すれば解くことができます。 $i&lt...
問題解説

[yukicoder] No.1594 Three Classes

概要 問題文 → ■公式解説 → ■自分の提出 → ■ 想定されている解法よりもだいぶ難易度が高いですが、$O(N^22^N)$ で解けます。$N \leq 12$ の制約では特に高速にならないですが、この解法であれば $N=20$...
スポンサーリンク
タイトルとURLをコピーしました