JOI

はじめに

2024年9月の現在JOIに向けた過去問演習を行っており、出題された典型アルゴリズムを振り返りやすいようにこのまとめを作成しています。名前のついている典型アルゴリズムは非公式難易度の難易度4以上から出現するのでそれ以降から難易度7以下でまとめています(予選2に向けたまとめと思ってください)。随時更新中です(2024年の予選2までには難易度7以下までまとめる予定)
「「問題文(難易度)」ちょっとしたメモ 」 というまとめをしています。

本番用メモ

• 困ったら部分点解法をとりあえず一個ずつACする方法を考える。部分点解法を考察すると実は満点解法に繋がってることが難易度6以降の問題で多い(5以下は試してなかったから不明) 「室温」「A - いっしょ」
• O(5*10^18)までならTLEしない、過去問やってると n=10^4で、O(n^2)解法が多くてTLEを誤認しやすい https://atcoder.jp/contests/abc381/submissions/60233818
• B問題がむずくて1完+部分点がボーダーの回がある(020/2021 二次予選)
• C問題が簡単で3完+部分点がボーダーの回があるので3完しても油断するな(2019/2020 二次予選)

未解決

• 「B - 宣伝 2(7)」なんで両方の条件を見るのか
• 「E - イルミネーション(7)」正しい解法を知らない
• 「D - 歩くサンタクロース(7)」なんでそれが解法として成り立つのかわけわかめ

難易度ごとの体感難易度

• 4まではABCのC問題が解ける人なら簡単
• 5はABCのC問題からD問題くらいの難易度
• 6はD問題からE問題くらい 水色コーダー的には自力で解法がわからないやつが多い

自力で解けなかった問題

• 「D - 展覧会 2(6)」最小値の最大化なので答えを二分探索を考えてみる。f(x)=最小がx以上であるやつをm個以上取れるか？を判定できればいい。選んだ内容を求められてなくて可能かどうかだから「m個取れればいい」=「m個以上取れるなら、適当に捨てればいい」と考えられる
• 「B - お菓子の分割 (6)」
• 「C - JOI 国の買い物事情(6)」ダイクストラ法で求めたdistを用いて式を立てる。distも含めた両方の経路において、経路での中心になりえる場所が最長となる。その最長となるというのは「左方向への距離=右方向への距離」なのだから、端の頂点への距離をdとして式を立てていくと、答えが求められる
• 「D - 水ようかん(7)」n* L=5*10^4で最小と最大を全通り見れなさそうと思うが、あり得る長さだけを考えるとn^2=2500通りしか存在しない
• 「E - イルミネーション(7)」「仮にこの木を取ったら次はどこから取っていいか？」を遅延セグ木のapplyで投げる(想定解じゃないっぽいのでいつか正しい理解をしてほしい)
• 「D - テンキー(7)」桁DP的な発想に繋げる。上界がありそうと思って実装するとWAなので、longlongを超える桁の数字に対して余りを見たくなる。そうなると桁DPみたいに一桁ずつ決めたくなって、とりあえず配列を考えてみるとそれに対してダイクストラ法かbfsすればよいと思える
  -「B - パンケーキ(7)」bfs的なことをしないと答え求めるのきついなとなるが、O(Q)があるのできつそうと思うが、3^12=10^6くらいなので、クエリを見る前に全探索すればいいとわかる。ただ遷移の時点でO(3^13 * 13^2)=2*10^8であり、記録用にmapにstringを入れるとlogがついてTLEするので、3進数に変換しないといけない(gm)
• 「A - とてもたのしい家庭菜園(7)」区間に対しての操作は階差数列で考えて、階差数列における操作はどういう操作になるかを考える
• 「D - 飴 2(7)」一次元も二次元も色んなDP配列を考える。dp[i][j]=最新がi番目、最新から二番目がj番目を取ったとしたときのmax。を求めようとすると、貰うDPを考えたら、dp[i][j]なんだから貰う先の最新はjで絶対固定となる。つまりdp[i][j]を求めるなら、dp[j][?]という感じになって、?について考えると、?=0,1,2...i-kの範囲ならOKといえる(dp[i][j]を求めるという前提から、i,jを選ぶのは確定しているからi-k+1,i-k+2...i-1の範囲でもう一個選んでいるとまずい(jと被っていないとする))ので、累積maxを求めつつやればOK。配列を考えたら実際に貰うDPの漸化式を立式するところまでやろう
• 「A - ロケット打ち上げ (7)」よくわからないまま図を書くのをやめよう。単調増加であることによるメリットというのを考えるのが典型？

区間のずらし

• 「A-最大の和(4)」

動的計画法(簡単)

• 「F - 通学経路(4)」2^16はフェイク、nCrでもACできる用の制約だった
• 「共通部分文字列(5)」EDPCの部分列が部分文字列になって優しくなった版
• 「D - 1年生(5)」問題文の読み忘れに注意
• 「D - シルクロード(5)」あからさまにDPをするしかない(n,mのループがどっちが先でもOK)
• 「D - 暑い日々(5)」i=0の日に注意
• 「D - 部活のスケジュール表(6)」連日で参加してる人が1人以上いればよくて、それを満たしてるならつじつまの合う用に鍵を渡したとすればいい

動的計画法(ちょいむず)

• 「D - パスタ(5)」i<=2までの初期化がちょいむず
• 「E - 通勤経路(6)」移動方向を状態に持たせるよくあるやつ。bfsとか最短経路系に多いイメージだけどDPでもよくあるっぽい 問題専用の状態を1つの次元に入れようとすると実装が考えにくくなるからやめた方がいい(2次元にして移動方向とカーブしたかを別々に入れた方が考えやすい配列の定義も大して変わらん)
• 「C - つらら(6)」DAGとして見れることに気づくのがむずかしい
• 「stairs(6)」lowerでどこまで登れるか求めていもす法で配る(実装がすごいめんどくさい)
• 「B - 古本屋(6)」ジャンルごとにまとめて見る、F問題の重さごとにまとめて調和級数と似ている
• 「B - IOI 饅頭(6)」Σ饅頭-Σ箱　として見ると、個数が決まったとき饅頭は一意で、箱をDPで求められればOK
• 「A - オレンジの出荷(6)」区間分割をするDPというらしい。毎回今回分割というか一回分の箱で取るのを決める
• 「B - スタンプラリー 2(6)」両端から各状態までの通りを求めて、追加する場所を一個ずつ見ていって接続する。JOIの三文字しかないので累積和でできる
• 「A - リレー競技(6)」「DPの遷移をするときに選んだ要素同士のmaxなどの数値の関係がめんどうなら、独立に値を求める方法」を考える、そうするとBに対してソートすることで、大きい順なら先に選ばれた方が絶対にmaxの勝負で勝つといえるので、選んだやつをそれぞれ独立に見れるようになる。
• 「A - いっしょ(6)」問題を区間分割としてとらえられると区間分割DPを考えられて強い。部分点1を考察してみると塊の性質に気づける
• 「committee - 委員会(7)」木DPするだけ。めっちゃ遠いやつなら委員長を経由する必要があるとかなので、委員長を必ず採用しないといけないわけではないので注意
• 「2 - IOI 列車で行こう(7)」0,1をDP配列に持たせる。両端がIの必要があるので、初期化と答えを回収するときに注意
• 「M - ストラップ(7)」aを大きい順に採用するかどうかを見ていった方が組み合わせ的にいけそうなのに端子数が小さいのを上にしたせいでだめだったみたいな場合が防げそうという発想になる(a=0を上の方におかなければおきないので、小さいからダメというわけではない)。なのでaを大きい順にソートしてdpしていけばOK。ソートしなくても、残り端子数が負になった場合も保持しておいて、もし正にできるのであればswapして実はこういう順番でした、みたいなつじつま合わせをすればOK
• 「D - ぬいぐるみの整理(7)」bitDPする。累積和を使うとlowerのlogが消せるがおもいつかなかった
• 「E - エゴイ展(7)」種類が被らないトップ2を持てばいい ABC345-Eと同じ

動的計画法(激むず)

-「ナイルドットコム(6)」昨日選んだ店は今日と同じかどうかの0,1だけ持てばよくなる。配るDPなら配る元、貰うDPなら回収先、というのは「違う店を選ぶ遷移」のときどこを元として値を貰っても良くて、そして商品の金額は連続購入がなくて一意だから、その貰える先の値のminだけ貰えばいいといえる(絶対難易度7の方が正しい)

• 「B - お菓子の分割 (6)」ちゃんと理解できていない
• 「D - テンキー(7)」桁DP的な発想に繋げる。上界がありそうと思って実装するとWAなので、longlongを超える桁の数字に対して余りを見たくなる。そうなると桁DPみたいに一桁ずつ決めたくなって、とりあえず配列を考えてみるとそれに対してダイクストラ法かbfsすればよいと思える(実際の解法はDPではないけど考察的には桁DPの考察がカギになると思っている)
• 「D - 飴 2(7)」一次元も二次元も色んなDP配列を考える。dp[i][j]=最新がi番目、最新から二番目がj番目を取ったとしたときのmax。を求めようとすると、貰うDPを考えたら、dp[i][j]なんだから貰う先の最新はjで絶対固定となる。つまりdp[i][j]を求めるなら、dp[j][?]という感じになって、?について考えると、?=0,1,2...i-kの範囲ならOKといえる(dp[i][j]を求めるという前提から、i,jを選ぶのは確定しているからi-k+1,i-k+2...i-1の範囲でもう一個選んでいるとまずい(jと被っていないとする))ので、累積maxを求めつつやればOK。配列を考えたら実際に貰うDPの漸化式を立式するところまでやろう

一次元累積和

• 「A - 最大の和(4)」
• 「C - イルミネーション2(4)」
• 「C - 投票(5)」求めつつ伸ばしていく

累積max

• 「A - 長いだけのネクタイ(6)」ソートして[i]ごとに勝負させるのが最適。左右から累積maxを取って、iを使わないときはl[i-1]とr[i+1]を回収する

二次元累積和

• 「C - ロシアの旗(4)」二次元累積和なしでもいいけど高速化必須なら必要
• 「mall - ショッピングモール(5)」ド典型の二次元累積和
• 「A - 惑星探査(5)」クエリの入力の渡し方がごみ

いもす法

• 「A - 鉄道旅行(5)」O(N)かO(M)にしたいお気持ちと各鉄道を独立に見られるお気持ち(Σで表せる)
• 「D - 釘(6)」パスカルの三角形を二次元配列に変換(30以下のときのnCrと同じ)して、左から右下にいもす法をしようとすればいい。しかし横方向だけ伸ばそうとするとO(M*N)でTLEする。しかしその初期化的なのが重たいだけなのでそれを軽くすればよくて、それは「横方向→縦方向→斜め方向」という感じで遷移の順番を決めてあげてからそれに合わせて、それ用のいもす法を初期化してあげれば軽くなる(つまり初期化のTLEに対してさらにいもす法を先に適応して軽くしている)

一次元or数字の座標圧縮

• 「折り紙(6)」縦で平面走査して、各縦で使うx座標だけで座圧すると、全体で見た時に生成したいもす法の配列のサイズの総和は「Σ=N220=210^5」となる(全体で使うx座標の座圧サイズを毎回生成すると(N20)*(N *20)でTLEかMLEする なおマス目を全列挙してmapでカウントするのが想定解)

二次元座標圧縮

• 「ペンキの色(6)」MLEすぎてgm問題。ケツに番兵を入れて、連結成分を見るときはその番兵のときにアウトとすればいいout_grid(ni,nj,h-1,w-1)

累積和+二分探索(lower_boundと答えを二分探索どっちも含む)

• 「A - インターカステラー(5)」ちょいむず。カステラを分割すると2の素因数が全部消えると考えたら、分割後の長さは全て同じと言える。各カステラを分割したときの個数を累積和して、クエリのをx-1してupperすると分割前のときにどこのカステラにあったのかがわかる
• 「B - JJOOII 2(6)」累積和には番兵を入れた方がいい、最初のときもループ途中のときにも、インデックスの場所をそのまま引き算として使えるから
• 「B - 買い物 2(6)」全体での累積和と、各種類ごとにインデックスとセールのお金の累積和を持つ

答えを二分探索

• 「factorial - 階乗(5) 」ABC280-Dと同じ
• 「B - ジョイ四人組 (5) 」最低の身長の人(leastとする)を決め打ちして、f(x)=least以上least+x以下の人が各クラスに一人いるか？を求める(けんちょんさんのを見ると答えを二分探索じゃなくて最低のやつからlowerした方が簡潔だった(素直に最低の人を決めてそこから組むやつの最適を試しただけといえる)答えを二分探索の方が思いつきやすけどlogが二乗だからめっちゃ重たい。素直に各人を最低としたときにシミュレーションする発想が必要だった)
• 「アナグラム (6)」f(x)=x番目の文字列はs以下か？　をする。分布を集計して文字列sの通りに採用したら何通りが今までにありえたかを求めるのが想定解っぽい
• 「D - 展覧会 2(6)」最小値の最大化なので答えを二分探索を考えてみる。f(x)=最小がx以上であるやつをm個以上取れるか？を判定できればいい。選んだ内容を求められてなくて可能かどうかだから「m個取れればいい」=「m個以上取れるなら、適当に捨てればいい」と考えられる
• 「cheating - カンニング対策(6)」f(x)=長さx以下にしたときに全員見れてるか？を求める。問題文がくそわかりにくい。判定は軸ごとに貪欲に見てOK(証明みたいなのはわからない、各軸ごとに覆うから的な勘)
• 「C - バームクーヘン(7)」最小の最大なので、最小を決め打ちして、二周した配列に累積和とってlowerすればOK
• 「B - 自習(7)」自習するときは「自由に科目が決められるけどその日ごとに自習そのものにやる気があるからスコアが変わる」というわけではなくて、「科目ごとに一律のポイント」なので誤読に要注意。また、n,aが限界だったとしてもm=1,b=1のときにwj=10^18だったら一回しかaを引けないから(10^18-10^9)/1がbを使うときに必要な回数でそれを全て集計してからres<=n*mを見ようとすると絶対オーバーフローする。部分点の解法を実装してみて、そのサンプルと答えが合わないと誤読であることに気づける
• 「A - ロケット打ち上げ (7)」よくわからないまま図を書くのをやめよう。単調増加であることによるメリットというのを考えるのが典型？

lower_bound,upper_bound

• 「C - 鐘(4)」ド典型
• 「B - たのしいカードゲーム(5)」Aの数字ごとの座標を集計してupperしつつ、Rを一個ずつ右に動かしてデータを再利用する(lowerするならnow_rを更新するときに+1しないと同じ数字の連続のときに既に使った座標を見てしまう)
• 「B - ピザ(6)」upperにしておくと実装が楽(k=0のときlowerして-1だと、it-1=-1になってしまうけどupperだと0の先をitが見るから問題ない)
• 「IOI(6)」超むずい。「自分の得点以上の人数がk/12以上か？」ではなくて「自分の得点より高い(=自分の得点+1以上)の人数がk/12以上か？」という判定じゃないと正しい答えが求められない。また、自分の変更前だったときの値で自分自身を数えないように注意。**lower_boundしたことによって何を求めて、そこから何を求められて、それでほんとに答えが求められるのか？**をよく考えた方がいい
• 「D - JOI国のお散歩事情(6)」衝突場所を列挙してクエリに答える。D問題の蟻のと似ていて、右移動と左移動ごとに集計する。衝突場所の両端に番兵をに入れてエア会話させると実装がとても楽になる([i]が右移動、[i+1]が左移動のやつしか初めて衝突しない、気づかなかった...)

bfs

• 「C - パーティー(4)」入力例2において，あなたには友達はいない．したがって，あなたがクリスマスパーティーに招待する生徒数は0人である
• 「E - チーズ(5)」簡単
• 「B - カーペット(5)」やるだけ。ダイクストラ法じゃないとダメそうな感じがするけどbfsでもいいような気がしてbfsでもいける(ダイクストラ法で求められた最短の経路を考えるとそれbfsでもいけるなという想像をするとそれなりに納得できる)
• 「flu - インフルエンザ (6)」辺を構築してbfsするだけ。1msなのがいやらしくてintにすればOK、ダイクストラ法だと正方形じゃなくて円を見て辺を構築しないと絶対TLEするっぽい

dfs

• 「薄氷渡り(5)」どっかのABCのE問題で見た 保証がなかったら大まかに見積もって4^(N*M)くらいでTLEする(俺が一生理解してくれないやつ)
• 「D - カード並べ(5)」 10P4(dfsでの探索するときのrep(i,10)をしても問題ない 大まかに見積もって10P4*10してない)(nCk通りのインデックスを用意してそれぞれをk!でnext_pしてもいい)

uf

• 「Fiber(5)」
• 「C - 塗りつぶし(7)」各連結成分のリーダーと隣り合っている違う色の連結成分でグラフというか隣接リストを構築してあとは色を変えた時の得られるスコアを求めればOK。計算量というかグラフがO(HW)くらいなのかを見積れるのかわからん

SCC

• 「advertisement - 宣伝(8)」閉路を圧縮してDAGにするのは典型。「互いに到達可能な頂点同士を1グループとしてまとめてくれる」のがSCCなので認識ミスに要注意。「1つの閉路」や「一番大きい閉路」とは違う(一番大きいというのは多少あっているが、その閉路の経路を列挙ではないので、同じ頂点が二回出てくるわけではない)JOI「宣伝」

最小全域木

• 「finals - 本選会場(6)」最小全域木の存在を忘れていた。問題を言い換えると木として見られて最小全域木となり、さらに木と最小全域木の性質から言い換える

ダイクストラ法

• 「route - 象使い(6)」内積で角度判定をしつつ、ダイクストラ法をする(欲しいのは内積が0以下なので注意、正なら90°より大きいというのは不正解)
• 「C - JOI 公園(7)」今の手札でできることを考えていくと順当に解法が求まる
• 「E - ゾンビ島(7)」危険範囲をbfsで列挙してダイクストラ法するだけ、前処理してからダイクストラ法という感じ
• 「F - ヘビの JOI 君(7)」distに情報を持たせてダイクストラ法
• 「E - 森林伐採(7)」移動についての見方を変えると、スタートからの行きと帰りで1セットと見れて、それが木の本数分あるといえる。移動や伐採を辺の重みとして見てしまえばダイクストラ法ができそうだと見れる。ただdistの配列にスタートまでの移動距離をどうやって持たせるかが難しい。移動経路を持つことはできないので困るが、毎回進むごとに距離が+1されるのだから、そのスタートからの距離を配列にもっておけばいける(スタートからの距離を小さい順に見るのを先にループしてDPをすると、DAGみたいに辿れるようになってpq_g無しで解ける。辺の重みの計算などでダイクストラ法が正しいか不安になったらDAG的に見ていくとDPにできて解法の正当性みたいな自信がもてる)
• 「E - パレード(7)」必要になり次第反転させればOK。同じ頂点番号に立ってて、反転してる回数が同じなら経路はどうでもいいから距離が近い方だけ見ればいいと考えると、ダイクストラ法がDP的に考えられて正当性に納得できる
• 「B - 建設事業 2(7)」何もしてない時点でs-tの最短経路がk以下ならどこに辺をはってもいいのでnC2が答え。もしk以下じゃないなら「追加した辺を使わないと絶対にk以下になることはない」といえる。だから追加した辺についてを軸に考える、とりあえず適当に貼ってみると、その両端をa,bとしたらs-a,a-b,b-tの三つの長さにパスを分割できて、両端からのダイクストラ法があればこのパスの長さが求められる。両端のパス？はそれぞれ独立に決められるから、ソートしてどのくらいの長さ以下ならセーフかでupperしたらいい感じにできる

トポロジカルソート

• 「D - 最悪の記者」トポロジカルソートが1通りしかないかを判定するだけ。queue,dfs,SCCどれでもできる

全探索

• 「C - 看板(4)」 計算量がちょっとぎりぎりで怖い
• 「C - イルミネーション2(4)」

差分だけを求める

• 「A - JOI 紋章(6)」各場所を変えても4つの正方形しか答えが変わりえないので、変更前の答えを求めて、そこから変更後の差分を求める
• 「B - 愉快なロゴデザイン(7)」再帰の部分を読み忘れに注意、実装がちょっと大変だけど結構楽しい

二重Σの問題

• 「H - JOIOJI(6)」結構むずい。累積和を用いて式を変形することにより、Rの相方として可能なLの条件が求められるようになる。あとは余分でないJ,O,Iの各セットが一番残るようなLが欲しくて、つまりそれは条件を満たすLの中で一番左をmapに記録し続ければいい。

ソート

• 「ストーブ(5)」全体-空白の時間のうち大きいのk個
• 「B - 美術展(7)」maxとminにはソートが強い、ABC372-Eと似てる。rep(i,n)して自分がmaxとなったら、自分を含めて自分より左のminから始まった区間においておいしいのが欲しくて、minが仮に決まったとすると、[min,max]の間の価値は全て貰えることがわかる。どこのminから始まるのが一番良いかを考えると、問題文の式を分解すると、それぞれ違う場所からminが始まったとしたら、始まった先から今見てるiまでの価値は全て回収できる、しかし問題文の式における、+minに関してはそれぞれ違うので、そこを大事に見ていくことをかんがえる。そうすると、全ての区間を見るDPみたいに、ある場所から始まって、現状までにおける答えの式の最大値を持っておけばよいとなる、iがmaxとしているのだから最後に自分の大きさを毎回引き算すれば、全ての区間を見ることができる(すべての区間を見るDPの派生として考えた方がいい？)

尺取り法

• 「E - メロンの出荷(7)」尺取り法で求めた内容はグラフ化できる

円環

• 「A - 室温(6)」modMが来たら円環を考える(%tしたときの負と正みたいなのは絶対違う...)「全ての人を覆うような区間」という発想がある

幾何

• 「4 - JOIポスター (6)」円を中に完全に含んでいるかを判定する 「√a-√b>√d」みたいなのを判定するんだけど、両辺二乗して、さらに二乗すればいける

RLE

• 「A - JJOOII(5)」Oを基準にJとIを見る
• 「A - 碁石ならべ(5)」 指示通りに実装する
• 「C - 連鎖(6)」O(n^2)が通る。一番最初にRLEじゃなくて、変更した状態でRLEという実装の工夫みたいなのがある(正直嫌いな問題)
• 「電飾(6)」3つ連続したのを見て真ん中を判定させると左右とくっつけられる(セクションのDPでもできる明らかに実装がめんどくさいからしない)

貪欲法

• 「B - ダンス(4)」
• 「C - 最高のピザ(5)」DPと思いきやお金が一意なのでソートして大きい順に取る貪欲ができる
• 「B - いちご(5)」ぱっと見の解法だと一番左から拾っていくことで、でも戻る時間に無駄があるから最初から一番右にいればええやんという発想(はまやんさんによると直線状で右往左往するのは無駄である問題が多いらしい まぁ複雑な問題だと実装するのも難しいと思う)

小さい方から貪欲に見ていく

• 「E - 認証レベル(8)」おもろい、各世界にあり得る数字の通りがH*Wであることに気づいて、bfs的なのを順当に考察していくと解法にいける
• 「pyramid - 貫きピラミッド(8)」高さを上から順に見て、8近傍に配る。というのを考えるとO((H*W+N)*8)と見積もれる。しかしpqでlogをつけると4500msになってしｍ。ただ、高さごとに頂上の座標を集計して、上から見ている高さが下がった時に集計していたその高さの頂上をqueueに追加すると、pqではなくqueueで実装できて10^9未満の計算量で済む

集計する

• 「A - 勇者ビ太郎(5)」どっかのD問題で見た集計してnC2する的なやつ。Jを基準に右のOと下のIを求める(累積和でもできる実装が長くなるけど)
• 「D - コイン集め 2(6)」縦横それぞれを集計する。maxなのかminなのかがややこしい。二回反転されるやつの加算の数字は、(i,j)というのがbaseの値に元々含まれてるからそこに戻すと考えたら2を使うとわかる

シミュレーションする

• 「A - 往復すごろく(5)」#への移動を'.'をショートカットして計算していく
• 「B - ジョイ四人組 (5) 」答えを二分探索でもできるけど、各人を最低の身長としたときの最適な選び方をそれぞれシミュレーションするべきだった
• 「D - 日本沈没(6)」小さい高さから見ていく
• 「D - 釘(6)」imo[i][j]=(i,j)から自分を含めて何レベル下まで伸びるかのmaxをもっておいて、電波させていく
• 「fraction - 分数(8)」答えを二分探索してO(MlogK)したくなるけど、O(K)が怪しくて、小さいのから1個ずつ見ていくことを考えると、各分母の現時点の分数をpq_gに突っ込めばいい。互いに素になるまで+1し続けるのがTLEしない理由が不明

クエリ系

-「B - パンケーキ(7)」bfs的なことをしないと答え求めるのきついなとなるが、O(Q)があるのできつそうと思うが、3^12=10^6くらいなので、クエリを見る前に全探索すればいいとわかる。ただ遷移の時点でO(3^13 * 13^2)=2*10^8であり、記録用にmapにstringを入れるとlogがついてTLEするので、3進数に変換しないといけない(gm)

考察系

• 「C - タイル(4)」外周を削っていって残った場所が答え
• 「E - 品質検査(5)」見ていく内容の順番を考察する
• 「B - 最長の階段(5)」連続してるやつをRLEっぽく(合成のケツ更新忘れに注意)1セットとして結合させるとO(K)でできる(けんちょんさんの解法)
• 「C - 桁和(5)」操作は狭義単調増加で、各数字から行ける先は一意なのでメモ化再帰していいみたいな感じ。桁見るようの数字でmemoに書き込まないように注意(1敗)。あとDPでもできて、dp[i]=iからnにいけるか？をdrep(i,n)してもできる
• 「D - いちご 2(5)」四隅や中央を決め打ちすればいいと思いきや、十字架とかいろんなケースがあるので、「このいちごを含む正方形を全パターン見る」という実装が必要だった(くそ沼った 覚えておかないとABCで同じミスするから角決め打ちじゃダメなパターンがあると覚えておこう)(公式解説みたいに「自分を含んでくれる正方形の左上に+1するのが賢いと思う)
• 「A - 碁石ならべ 2(6)」一番強いやつみたいなのを考える。本番で考察系の問題に出会って困ったらとりあえずサンプルをたくさん用意して考察するのが良い
• 「E - 最軽量のモビール(6)」二分木っぽいイメージと、LCMが使えそうという考察が大事
• 「sheet - 色紙(6)」重なりの関係を有向グラフで表す。 そしたらトポロジカルソートでいける。E問題のstamp的にやるのは不正解...
• 「D - ラーメンの食べ比べ(7)」ずっと隣同士の比較をするよりも、rep(i,n)して現状のmaxかminを保持していく方が比較回数が少ない
• 「E - 尾根(7)」DAGなのは当然で、DPというかメモ化再帰したくなる。行きつく先がたくさんあるけど最大2つ、つまりトップ2を持ちさえすれば十分であると考察できる
• 「sequence - 数列(8)」偶奇なので%2だけ考えれば良い。幅mを1セットとしてとらえると、状態がループするみたいに考えられる。その閉路サイズはm=2,3,4だと2^m-1が閉路サイズと思えるが、mが大きくなると違うらしく、実際に閉路サイズを求めて、よくあるfunctionalグラフのやつをやればOK。MLEがgm
• 「abduction - 誘拐(8)」入力時点で縦横移動にわけられることがわかる。そうしたときに縦横を独立の求めてその積が答え

式を立てる

• 「C - JOI 国の買い物事情(6)」ダイクストラ法で求めたdistを用いて式を立てる。distも含めた両方の経路において、経路での中心になりえる場所が最長となる。その最長となるというのは「左方向への距離=右方向への距離」なのだから、端の頂点への距離をdとして式を立てていくと、答えが求められる

式変形

• 「B - 宣伝 2(7)」i,jを独立した形で見れるように式変形する。未理解

問題の言い換え

• 「F - ビンゴ(6)」nnのビンゴとはあるが、不等式を考えると数字が一列に並んでて総和がsになっているだけ。1,2,3...mの中からnn個の数字を選んで総和がsになればよくて、これはDPの典型の形と同じ(普通にむずい)
• 「C - あみだくじ(6)」横棒の座標的なのがめんどくさいけど、本質的な部分を考えて言い換えると「横棒の左右にいるやつのゴールの結果をswapできて、それ以外はそのまま」と言い換えられるので、各スタート地点でゴールの結果をswapできるやつを求めて純粋に変更可能なやつ同士を結んだグラフみたいになる

尺取り法

• 「B - 最長の階段(5)」O(N)の尺取り法じゃなくてO(K)でやろうとすると実装がむずすぎて諦めた。セクションのDPもできる。連続してるやつを1セットとして結合させるとO(K)でできる(けんちょんさんの解法)
• 「B - JJOOII 2(6)」「Jがここから始めるとき、OはどこからならOKか？」というのを尺取り法で求める(個人的に珍しい)

半分全列挙

-「ダーツ(6)」0を入れておくと投げないとか無に投げたとかができて強い

next_alphabet

• 「deciphering - 解読(6)」典型90のやつに後ろのやつに来ちゃいけない条件がついただけ。存在をほぼ忘れててデジャヴを感じて思い出した。「同じ文字列を複数回数えてしまう」という状況を回避するには「文字を採用するときは絶対に一番近いやつだけを採用する」とすればいいと気づけば自力でもできるかも

数学系

• 「C - 超都観光(4)」場合分けがめんどい

階差数列

• 「A - とてもたのしい家庭菜園(7)」区間に対しての操作は階差数列で考えて、階差数列における操作はどういう操作になるかを考える
• 「A - フェーン現象(6)」サンプルを書いて考察してみると、[l,r]は階差数列における[l-1]と[r]にしか温度の変化を与えないので、答えの差分の変化だけ求めてあげればいい

ルジャンドルの定理

• 「factorial - 階乗(5)」ABC280-Dと同じ

素因数分解O(√N)

• 「factorial - 階乗(5)」ABC280-Dと同じ

繰り返し二乗法O(logN)

• 「fermat(6)」現代のCPUならO(p^2)かけてもいけるらしい(0.5msなのに10^8回がなぜ通るのか)

包除原理

• 「banner - 横断幕(6)」>- 「bitを立てたやつを絶対に含む他はどうでもいい」ではなく「bitを立てたやつを絶対に含まない他はどうでもいい」というのを軸にしないとできない包除原理がある

実装問題的な

• 「IOIOI(5)」ある塊を1セットとして見ることで実装を楽にする
• 「JOIポスター(5)」再帰関数で華麗なる逆転
• 「コンテスト(5)」B問題の250点レベル
• 「シャッフル(8)」1,2,3,4...nを[1,n+1)の区間として考えて、操作がこれを分割すると考えると、最大でも一回の操作で2回までしか個数が増えないので最大が1+2Mの区間となるため、ループ内で一個ずつ区間をみてもO(M^2)でTLEしない。実装がくそむずい

出入りはそれぞれ一回なので、コード全体は2*N回で済むやつ

• 「B - 買い物 2(6)」セールの種類ごとにまとめて答えを求めると考えたとき、セールに関係するお金の出入りは追加と削除のそれぞれ一回なので、BITでそれぞれのお金を管理してもTLEしない
• 「C - 座席 2 (6)」ΣΣで考えると「それぞれの人を見る→違う国の人を見る」となるので、ここで内側の国の方を先に考えてみると「国を基準に考える」と言えて、同じ国の人が被らないようにするのを考えるとmultisetへの削除と追加がそれぞれ一回でできる
• 「E - 砂の城(7)」各マスの寄与みたいなのを考えると8方向しかない、で消えるやつをqueueにつっこむみたいなのをかんがえると、出入りが一回なのでO(HW)。E-stampと似ている

部分点を考察する

• 「E - カードゲーム 3(7)」内容的に事前知識で殴れる感じじゃないから部分点がヒントであると信じて部分点の考察をすると解法にたどりつける

セグ木

• 「E - エゴイ展(7)」セグ木を保持してDPする。seg[i]=最後にとったのがi番目の種類である最大。毎回一点しか更新しないのと左と右の区間を回収できればいいのでセグ木でいける

遅延セグ木

• 「E - イルミネーション(7)」「仮にこの木を取ったら次はどこから取っていいか？」を遅延セグ木のapplyで投げる(想定解じゃないっぽいのでいつか正しい理解をしてほしい)