精選100問をやる
これはなに
ABC の 400 500 が埋まり、 experimental でない 水 diff が埋まり、experimental でなく AGC でもない 青diff もだいぶ埋まり、蟻本類題も中級までやったため精進の方向性が迷子になってしまった…… 次はなにをやろうかなと思ったところで、今足りていないのは何かを考える。
- 知識はある程度身に着いた気がする
- 思いつく能力みたいなのは全然足りていないけど、これは粛々と数をこなすしかない気がするので保留
- なんとなく現状速さと正確さがが足りない気がしている
- 今の知識セットのまま速くなればレート200は盛れる気がするし、正確さを得れば爆死が減って精神によい(ハードル走の反省……)
その辺を色々考えて、イカの精進が思いついた
(要するにちょっと下くらいの問題を時間を計って短時間で解いてみようという試み)
- experimental な 水 青 diff埋め
- experimental difficulty は一色ぶんくらい高く出ているような気がするので、下埋めの狙い
- 平成ABC(ABC041以前)の D 埋め
- 実は実質 experimental な 水 青 diff埋め
- 精選100問 埋め
- 目指せ水色コーダー の記事なので、やっぱり下埋めの狙いなのだけど、"100 問全部解けたら、水色コーダーどころか青色コーダーくらいの実力が付くと思います。"らしいんで、信じるのだ……
思いついた中で、現環境に合わなかろう古い問題を埋めるよりも赤い人のおすすめ100問のほうがコスパがよかろうということで精選100問をやることに。
レギュレーション
- 時間を計る
- 速さを定量的に評価するため。
- ライブラリ禁止
- 実装の筋トレも目的のひとつなので。
- ただし非本質部分(ダイクストラに対するグラフテンプレート部分とか)はオッケー
- 蟻本写経はオッケー
- 自己流の悪い実装をしてもしかたないので……
- 解いたら時間、自力 or not、感想をここに書く
- ボトルネックにならない程度に……
- できれば朝やる
- 基礎力トレーニング
- とか言いつつ、おせんべいが やや難問 とか言って登場したりするのでできる限りで
- できれば疑似コードを手で書く
- バックスペース禁止はむりだけど……
結果
| num | time | submit | 感想(どういうバグらせをしたか等) |
|---|---|---|---|
| 1 | 4:30 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4556791#1 | 重複NG とかを読み飛ばしてちょっと戻った |
| 2 | 7:56 | https://atcoder.jp/contests/abc106/submissions/14085318 | 奇数 を読み飛ばして合わず、変数名を間違えて合わず をした(考えながら実装をするな) |
| 3 | 5:55 | https://atcoder.jp/contests/abc122/submissions/14085853 | 疑似コードを書くようにした 一度も戻らずAC |
| 4 | 7:51 | https://atcoder.jp/contests/pakencamp-2019-day3/submissions/14086112 | 疑似コードというか C++ のコードを手書きしているんだけど…… |
| 5 | 8:32 | https://atcoder.jp/contests/abc095/submissions/14086472 | max と min を間違えて1回休み |
| 6 | 11:03 | https://atcoder.jp/contests/sumitrust2019/submissions/14104743 | 3桁決め打ち、フラグ立てる時どこまで埋まっているかを見ず1回戻り |
| 7 | 21:27 | https://atcoder.jp/contests/joi2007ho/submissions/14148247 | 面白い、頂点 P, Q, R, S のうち2点を決めれば正方形が定まるので、全探索するのはN2でOK |
| 8 | 15:33 | https://atcoder.jp/contests/s8pc-6/submissions/14169626 | 興味があるのは 人が行きうる座標だけなのでそれを全探索 手戻りなし(のわりに遅い？) |
| 9 | 16:04 | https://atcoder.jp/contests/joi2008yo/submissions/14190764 | 手戻り無し のわりに遅いかなあ。 JOI、座標好きがちなのでベクトルのライブラリがほしくなってくる |
| 10 | 4:05 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4572490#1 | 手戻り無し |
| 11 | 10:07 | https://atcoder.jp/contests/abc128/submissions/14401968 | 条件が若干複雑なので紙で条件を整理すると事故らなくてよいですね |
| 12 | 11:45 | https://atcoder.jp/contests/abc002/submissions/14422184 | 集合の中にいる人の組を全探索するときに同じ人間の組み合わせを許容してしまい1回戻り |
| 13 | 10:10 | https://atcoder.jp/contests/joi2008yo/submissions/14442890 | 手戻り無し |
| 14 | 23:34 | https://atcoder.jp/contests/s8pc-4/submissions/14462776 | 累積 max を持っておくと実装が楽。編集していいビルを全探索するか見えるビルを全探索するかで迷った、コストを計算する式を間違えてコストが負になった |
| 15 | 11:30 | https://atcoder.jp/contests/abc145/submissions/14601298 | 添字を2回間違えて時間を食った、1回目は1->2->3 のルートの長さを6回足してた(なんで) |
| 16 | 6:35 | https://atcoder.jp/contests/abc150/submissions/14626459 | フラグを書き換える場所と辞書順の値を誤って1回戻った |
| 17 | 31:56 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4625270#1 | 言われて見れば順列全探索だなあ、と思い next_permutation を書き、バグらせて結局dfsを書いた。グリッド上の斜めはx座標とy座標の和または差が一定。 |
| 18 | 6:09 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4628621#2 | 手戻り無し、次の数の場所を探すときにupper_boundが使える |
| 19 | 23:37 | https://atcoder.jp/contests/joi2009ho/submissions/14875840 | 各クエリで二分探索して 家 の左右の店を見つければよい。(番兵として距離dにも店を置いておく)、== と = を間違える古典的なやつをして1バグ |
| 20 | 7:23 | https://atcoder.jp/contests/abc077/submissions/14894821 | 固定するのは直接影響する要素が多いもの(今回はB)がよい、 + と * を間違えて1バグ |
| 21 | 19:39(+2WA) | https://atcoder.jp/contests/abc023/submissions/14958761 | H_i > k なる k は達成不可能なのを見落として1WA、デバッグ中に1WA |
| 22 | 41:11 | https://atcoder.jp/contests/arc054/submissions/15034683 | 謎の定数(迫真) 二分法は初めてだったので時間がかかった 追記: 2.164042560698 は3 / (2log2) で、fx = x + P(2x/1.5) の第二項目にあたる |
| 23 | 13:52 | https://atcoder.jp/contests/joi2008ho/submissions/15057057 | N = 1000 なので半分全列挙して相方を二分探索。全列挙した配列をソートし忘れて1バグ |
| 24 | 32:17 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4651272#1 | 問題の読解が難しかった、出次数0の点を展開するのに1かかるなどを見逃してハマった(適当に時間を増やしたり減らしたりして通してしまった節がある、問題文から何をすると時間が経つのか読み取れなくない？) |
| 25 | 10:08 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4656192#2 | 手戻り無し |
| 26 | 9:23 | https://atcoder.jp/contests/abc138/submissions/15214611 | 手戻り無し |
| 27 | 43:21(+3WA) | https://atcoder.jp/contests/joi2009yo/submissions/15232708 | x と y を間違える、nx と x を間違える、そのマスの探索が終わったらそのマスの visitedフラグを折る(これが本質)を忘れるなどしてハマった、depth を最初引数にしなかったのも混乱を助長した、多少冗長でもわかりやすさを優先した方がよい |
| 28 | 5:55 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4671578#1 | while の条件書き忘れ(そんなことある？)と != と == を間違えて(そんなことある？)2回バグらせたけどどちらも一瞬で解決できた |
| 29 | 8:38 | https://atcoder.jp/contests/abc007/submissions/15249845 | 壁かどうかを見るのを忘れて1回バグった(そんなことある？) |
| 30 | 16:38 (+ 1TLE) | https://atcoder.jp/contests/joi2011yo/submissions/15325682 | visited な場所はキューに入れない から大丈夫と思ってキューから出したもののvisitedチェックをサボったらTLEした(同じマスに同じ距離で到達するパスが複数ある場合、同じマスからのパスを複数回数えてしまう) |
| 31 | 42:54 | https://atcoder.jp/contests/joi2012yo/submissions/15340713 | W と H を取る順番を間違えて1回戻った、純粋に六角形の遷移を考えるのに時間を食った |
| 32 | 24:59 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4692845#1 | 普通に bfs だけど壁の扱いが厄介、h と w を 1か所間違えて1回戻り |
| 33 | 13:10 | https://atcoder.jp/contests/abc088/submissions/15373165 | 普通に bfs 、スタートとゴールのことを忘れて1回戻り |
| 34 | 1:53 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4704355#1 | 手戻り無し |
| 35 | 23:06 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4704427#1 | ナップザックの大きさを勘違いしていて1WA、デバッグに苦労した |
| 36 | 4:38 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706743#1 | 手戻り無し、個数制限がない場合は遷移の方法を少し変えることで対応できるのであった。 |
| 37 | 8:01 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706794#1 | 手戻り無し、36 の個数制限なしナップザック問題の気持ちになるとOK |
| 38 | 18:29 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4706913#1 | 1-indexed にする時にstring::length を先頭にダミー文字を追加した後に使ってしまいバグらせた。蟻本の「どれかであるので」という考え方が重要なのであった |
| 39 | 14:47 | https://atcoder.jp/contests/joi2011yo/submissions/15484514 | 手戻りなし、dp[i][j] := i 番目まで計算して、結果が j になる場合の数。先頭と末尾を特別扱いするのでインデックス注意 |
| 40 | 44:54 | https://atcoder.jp/contests/joi2012yo/submissions/15485657 | 配るDP にしたら i 日目 は パスタ k しか食べてはならぬ の条件を i + 1日目 に適用してしまいバグらせた。 前日と前々日の食事さえ分かっていればよいので、それらを添字に持つ |
| 41 | 18:48 | https://atcoder.jp/contests/joi2013yo/submissions/15496981 | 手戻りなし、dp[i][j] := i 日目 にフク j を着るときの最大スコア |
| 42 | 19:11 | https://atcoder.jp/contests/joi2015yo/submissions/15513581 | M 日目 にも移動できることを忘れて答えが合わなかった。 dp[i][j] := i 日目 に j に居る時の最小疲労度 |
| 43 | 21:17 | https://atcoder.jp/contests/pakencamp-2019-day3/submissions/15532988 | 手戻り無し。結局 i 列目 の塗り方は i-1 列目の塗り方にのみ依存するので、 dp[i][c] := i 列目 を色 c で塗る時の最小コスト。i 列目 を色 c で塗る場合を全てまとめて考えてよいことに対応する。 |
| 44 | (時間を計っていないけれど合計1hくらい？) | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4727213#1 | 個数制限なしナップサック問題なのだけど、普通にやるとMLEする。配列を使いまわすとOK |
| 45 | 20:33 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4730700#2 | 素直に dp[i][j] := i番目のデータがjに復号される時の最小コスト |
| 46 | 33:58 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4730839#2 | 素直な区間DP、[m, r) をマージした行列の行数を間違えて1回戻った |
| 47 | 40:01 | https://atcoder.jp/contests/joi2015ho/submissions/15655523 | 円形 -> 二周分配列(今回はDPテーブル)を持つ。手番の存在を忘れて1回戻り、メモ化を忘れて1TLE |
| 48 | - (自力できず) | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4736472#1 | dp[l][r] := [l, r) にできる操作の回数 なのだけど、2つの区間の和になる遷移 と 長さが2小さい区間の外側の差が1以下の遷移 を同時にやろうとして迷走してしまい解説AC |
| 49 | 38:20 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4738606#2 | 始点が定まっていない。と思ったら始点を0にする大嘘が通ってしまうので笑う。と思ったがそれはそうか*1蟻本を見ながら頑張って書いた。dp[S][v] := Sに含まれる頂点を訪問済みで、vにいるとき、そこから残りの頂点を訪問して start に帰ってくるときの最小コスト。初期値(再帰の停止条件)が全頂点を訪問し終わった時であることに注意する |
| 50 | 101:11 | https://atcoder.jp/contests/s8pc-1/submissions/15803043 | dp[S][v] := 訪問済み頂点集合がSでvにいる時の(最小コスト, 場合の数) のペア として下から配る DP をする、蟻本版でやろうとして無限に迷子になった |
| 51 | 29:40 | https://atcoder.jp/contests/joi2014yo/submissions/15815045 | 手戻りなし、 dp[i][S] := i日目に集合Sの人が参加する場合の数、SからS'に遷移するときに S & S'が0でないこと、各日の責任者を含むことを確認する |
| 52 | 33:43 | https://atcoder.jp/contests/joi2017yo/submissions/15818888 | 手戻りなし、 dp[S] := ぬいぐるみを左から詰めていくとしたとき、集合Sを置き終わった時の最小コスト。TSP 同様 n! を 2n に落とす系。 bitDP と言われてなければ解けなかった気がする…… |
| 53 | 31:43 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4754100#1 | 手戻りなし、セグ木の方しか知らないので貼ってしまった、dp[i] := ai を左端としたときの最長の LIS で更新はchmax(dp[i], [0, ai) の最大値 + 1)、aの範囲が広いので座圧がひつよう |
| 54 | 14:51(+ 1WA) | https://atcoder.jp/contests/abc006/submissions/15838521 | i 番目までソートする手順から i + 1 番目までソートする手順を構築しようとするも嘘なのでWA、よく考えると LIS の場所は変えずにそれ以外の場所だけ変えると最小コストになることがわかるので昨日書いた LIS のコードを貼ってAC |
| 55 | 15:23 | https://atcoder.jp/contests/abc134/submissions/15865751 | 手戻りなし(が、すでに解いたことがあったため……)、作られる増加列の先頭に注目すると、広義単調減少になっていることがわかるので、LISの要領で最長減少部分列の長さを求めるとGG |
| 56 | 10:45 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4760053#1 | 手戻りなし、素直なdijkstra |
| 57 | 17:07 | https://atcoder.jp/contests/joi2008yo/submissions/15881676 | ダイクストラをソラで書く縛りをしているのでキューに入れる不等号を逆にしてバグらせた |
| 58 | 48:13 | https://atcoder.jp/contests/joi2016yo/submissions/15882860 | 手戻りなし、普通に実装が重かった、bfs パートは素直に bfs をすると TLE するのでそのノードにより近いゾンビ町が存在するときは探索を打ち切る枝刈りをいれるとO(N)になる気がする。 |
| 59 | 83:39 | https://atcoder.jp/contests/joi2014yo/submissions/15984809 | グラフ構築パートで dfs を書いて1回戻り(dfs では最短経路は求まらないのであった)、bfs をなんとなく書いたらめちゃくちゃバグって苦しくなった。visited はキューに入れる時に true にしないとほかのノードからそのノードに到達したときに最適でない経路が記録されてしまうのでNG。幅優先探索なんもわかってなかった |
| 60 | 9:39 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4765542#1 | 負閉路検出は2回目で更新があったらでOKなのであった。(ベルマンフォードと同じ) 蟻本の実装だと負辺がある場合 INF から引かれてしまうので、 INF からは遷移しない、出力時に INF の範囲を広くする(あり得る最大パス長を超えたらINF)などの工夫が必要。 追記: WF の負閉路検出は dist[i][i] < 0 でもできるらしい。たしかに…… |
| 61 | 11:02 | https://atcoder.jp/contests/abc012/submissions/16014119 | 手戻りなし、問題文の読解が難しいけど WF して全始点について調べたらOK |
| 62 | 5:42 | https://atcoder.jp/contests/abc079/submissions/16021273 | 手戻りなし、グラフに見えるまでが大変な問題な気がするけど流石に最近は見えるようになった気もする |
| 63 | 64:11 | https://atcoder.jp/contests/abc074/submissions/16022335 | 与えられたAを完全グラフの隣接行列と見るまではよかったものの最小全域木を求めたり辺を小さい順に入れようとしたりして迷走した、迂回路がある辺は取り除いてよいので、A[i][j] == A[i][k] + A[k][j] なる k があったらその辺を除けばOK |
| 64 | 7:57 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4772473#1 | 手戻りなし。今まで クラスカル の方が簡単なのでクラスカル を書いていたが、ここでは経験のため プリム を書いた。このプリム は ElogE な気がするけど、どうするとElogV になるんだろう(蟻本のダイクストラ同様の議論ができる？) |
| 64_2 | 4:19 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4772504#1 | プリム法。こちらの方が実装が楽なので以降こちらを使う。(UnionFInd はまだ貼ってる) |
| 65 | 28:42 | https://atcoder.jp/contests/joisc2010/submissions/16039928 | 手戻りなし。K = 1 のときは普通に最小全域木を求めたらよくて、そうでないときは最小全域木から自由に辺をK-1本除ける(会場と会場の間の辺を自由に1本除去できるので、好きな辺を除去するための配置を構築できるはず) |
| 66 | 30:55 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4775067#1 | int と double を間違えて何度か戻った。 基本はセル？をノードとしたグラフを考えて MST するだけ |
| 67 | 11:07 | https://atcoder.jp/contests/abc065/submissions/16068331 | 手戻りなし。3回目なので流石にネタを知っている、この問題設定では MST に含まれうるのは x座標とy座標でソートした時に隣り合う点を含む辺のみ。 |
| 68 | 2:34 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4783941#1 | + と * を typo して1回もどり(そんなことある？) |
| 69 | 10:59 | https://atcoder.jp/contests/abc084/submissions/16175469 | 1 を素数にしてしまい1回戻り、これ本質は 累積和 なのでは…… |
| 70 | 2:28 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4784031#1 | かけた時に mod 取り忘れて1回戻り、毎回蟻本版非再帰はかしこいなあとなる |
| 71 | 14:06 | https://atcoder.jp/contests/s8pc-1/submissions/16178360 | 今いる場所を更新するのを忘れて1回戻り、これも本質は累積和…… |
| 72 | 8:39 | https://atcoder.jp/contests/abc034/submissions/16178666 | H+W が 105 を超えうるのを忘れて1回戻り |
| 73 | 13:09 | https://atcoder.jp/contests/abc145/submissions/16179230 | 手戻りなし、基底ベクトルがちょっと変な座標平面で経路数える問題をやるだけ |
| 74 | 63:04 | https://atcoder.jp/contests/abc021/submissions/16182256 | O(nk) DP の計算量の見積もりを間違えて1TLE、その後DPテーブルを見るとパスカルの三角形になっていることに気づいてAC |
| 75 | 解説AC | https://atcoder.jp/contests/abc149/submissions/16202402 | むずい、期待値の線形性から各ノードの寄与度を個別に計算してよい、全方位木DP が必要そうな気持ちになって手が止まるんだけど、根つき木にした時に子側のノード数は木DP、親側のノード数は全体から引けば求まる(典型)(CF665 Div2 Dでも出た) |
| 76 | 8:18 | https://atcoder.jp/contests/nikkei2019-final/submissions/16214202 | 手戻りなし、累積和で区間和を高速化するとO(N2)で全探索できるようになる |
| 77 | 15:25 | https://atcoder.jp/contests/joi2010ho/submissions/16233240 | 区間和を累積和で高速化するだけ、あまりを取り損ねて1回戻り |
| 78 | 31:11 | https://atcoder.jp/contests/joi2011ho/submissions/16253199 | 実は2D累積和ははじめて、けんちょん氏の記事を見ながら頑張って書いたものの半開区間の感覚がバグってクエリ時の +1 を忘れてバグらせた(ちなみにけんちょん氏の記事の2D累積和はクエリ時のxとyが逆？) |
| 79 | 26:59 | https://atcoder.jp/contests/abc106/submissions/16272131 | 2D累積和を構築するときに0-indexedと1-indexedを間違えて1回戻り、1回解いてネタを知ってる + 累積和という情報あり、というかなりのズル、包含される区間の個数は2D平面にプロットすると累積和で高速に求められるのであった。 追記: 実装に若干嘘を埋めていて、入力が L <= R を期待しているコードになっている(L > R なる区間を足してしまっているが、そこが0であることを期待している)。今回の制約はそうなので、通る。 |
| 80 | 31:18 | https://atcoder.jp/contests/gigacode-2019/submissions/16463172 | 素直に2D累積和すると全探索できる。試しにライブラリ形式で実装してみた、べた書きだとインデックスを間違えがちなので相性はよさそう |
| 81 | 3:43 | https://atcoder.jp/contests/abc014/submissions/16475363 | 素直な imos 法するだけ |
| 82 | 23:15 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4813839#1 | 素直な imos 法するだけ、時刻のパースがヘタクソすぎる |
| 83 | 22分程度(CEDEC見ながら) | https://atcoder.jp/contests/joi2015ho/submissions/16478616 | imos をすると各路線を何回通るかわかるので、どちらがお得か計算可能 |
| 84 | たくさん | https://atcoder.jp/contests/joi2012ho/submissions/16489765 | 三角形のいもす法をいもす研ガン見しながらやった、変な座標系に対するいもす法の構築は目新しかった |
| 85 | 7:55 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4816695#1 | UF のライブラリを再実装してから解いた、 root の else 節で値を返し忘れておりデバッグした |
| 86 | 4:02 | https://atcoder.jp/contests/abc075/submissions/16500077 | 除く辺を全探索できる |
| 87 | 15:46 | https://atcoder.jp/contests/abc120/submissions/16521383 | UnionFind は分離できないので手順を逆回しして併合にする。最初の0が要らないのに気づかずちょっとデバッグした |
| 88 | 19:06 | https://atcoder.jp/contests/joi2008ho/submissions/16534292 | (色, 個数)のペアを保持する。置き換えが発生したとき、置き換えによって2つ手前の集合と同じ色になる場合マージする必要があることを忘れて1回戻った。毎回適切にマージすると保持される区間の色は交互になる(ex: 0, 1, 0, 1...)はずなので、計算量は悪化しない。 |
| 89 | 82:12 | https://atcoder.jp/contests/joi2013ho/submissions/16537069 | ランレングス圧縮した後同じ色が{2, 3, 4以上}連続する時について丁寧に場合分けする、2の場合が複雑でつらかった 解説を読むと交互列の長さでランレングス圧縮しており、かしこい |
| 90 | 24:00 | https://atcoder.jp/contests/s8pc-5/submissions/16550535 | 最小値の最大化なので二分探索(二分法)をする。最小半径 r を固定するとそれが可能かどうかはO((N+M)2) で判定できて十分高速。 |
| 91 | 27:49 | https://atcoder.jp/contests/abc144/submissions/16558668 | 平面図形の問題に落とせる、2回計算ミスした |
| 92 | 48:20 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4820842#1 | y座標ごとに始点をリセットするのを忘れて1バグ、デバッグに苦労した |
| 93 | 40:10 | https://atcoder.jp/contests/s8pc-3/submissions/16587818 | 落下処理とスコア計算処理を 92 から使いまわしたものの結局バグっていた、定数倍気にしなければ各行をランレングス圧縮してK以上だったら消える、とするのがいいのかも |
| 94 | 38:38 | http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4824261#1 | 計算量はたいしたことないので vector::erase を使ってサボれる。 |
| 95 | 6:33 | https://atcoder.jp/contests/abc149/submissions/16604842 | 貪欲 |
| 96 | 5:52 | https://atcoder.jp/contests/abc139/submissions/16604984 | i mod j (i < j) は i なので、1, 2, ..., N を1反時計回りにずらした Pi を考えると良い、適当にいじっていればすぐに思いつくけど、こういうのを直感以外で思いつくのはどうすればいいんだろうね |
| 97 | 43:33 | https://atcoder.jp/contests/abc150/submissions/16622766 | 式変形すると ak の奇数倍が 2X になればよいことがわかるので、全体の lcm の奇数倍が 2X 以下であるものを数えればよい。ただし、 ak の偶数倍が lcm になるときは解がなくなることに気を付ける。(lcm の奇数倍が ak の奇数倍ではないため) |
| 98 | 7分くらい | https://atcoder.jp/contests/sumitrust2019/submissions/16648910 | 各人を独立に考えてよくて、前から見て人iを見た時に A_i-1 の登場回数 - Ai の登場回数 通りの色があることがわかる。 |
| 99 | 155:24 | https://atcoder.jp/contests/ddcc2020-qual/submissions/16666763 | 操作の順番は回数に寄与しないという考察はそこそこ早く出たものの、へんなバグらせをして無限に時間をかけてしまった |
| 100 | 31:40 | https://atcoder.jp/contests/tenka1-2018-beginner/submissions/16749495 | 集合を頂点、共通の数を辺とみなすと完全グラフの辺にちょうど1-Nの数字を振れればいいことがわかるので、その通りに構築する、出力フォーマットを間違えて1WA |
メモ
19: こういう「二分探索して自分以下の数があれば返す」みたいなクエリはライブラリ化してもいいかもしれない(upper_bound -> begin じゃなければ一個もどす)
感想
- 1日1問やるにはちょうどいい難易度だった
- 簡単すぎ、と思うこともややあったけれど、全体的に見れば簡単すぎ、と言ってはいけないくらいの時間がかかっている問題が多いのでやっぱりちょうどいい難易度だった気がする
- 実装がやや複雑そうなときだけ疑似コードを書いたけれど、しょうもない添え字バグとかは減った……気がする
- それでも全体的にしょうもないバグ埋める率は高め……
- DP の部分がめちゃめちゃいい練習になった
- ライブラリ縛った意味はそこそこあった気がする、少なくともここに上がっているアルゴリズムとデータ構造で理解に不安が残るものはなくなったはず
*1:一筆書きの閉路なので、どこが始点になろうが解が存在するなら長さは同じはず
