第7回アルゴリズム検定、なんと70分以上余らせた状態で満点いただけました！
前回の第6回が82点の上級だったのでこの成長は嬉しいな～。
せっかくブログも作ってたので1問1問振り替えります。
個人的には人に丁寧な説明をするのが好きなので、問題の難易度に合わせた説明ができたらなと思います。といいつつ後半ダレてきた跡がしっかり残ってる。
私もまだまだ日が浅いので認識として甘いものがあったらどんどん指摘いただきたいな～と。
A : チェックディジット
言われた通りにやればよいです。
文字列を数字にしっかり変換できるようになっておきましょう。
慣れてきたら左から見て言って「奇数なら3倍、偶数なら1倍で足す」のほうが整理しやすい。
通常の変換でもいいし、s[i]-'0'でもいけます。
B : 蒸気圧
言われた通りにやればよいです。
doubleの変換はお間違えなく。一個一個割っていっても良いし、計算式を整理すれば実は
max(double(c),double(a)/b)で終わっちゃう。
C : 入力チェック
いろんなやり方がありますがこれも言われた通りにやれば大丈夫ですね。
Aと同様、文字列を数字に変換する方法をしっかりと身につけておきましょう。
D : 書き換え
ベーシックな貪欲法。
左から順に言われた通りに変換すればいい問題。
ただ注意点としては
- axaxa
というものが出てきた時に、与えられたsと答えの文字列を別々にしてると
- 1～3文字目はaxaだから答えの1～3文字目は...
- 3～5文字目もaxaだから答えの3～5文字目は...
- 全部合わせて答えは「.....」
とかにご注意を。
そしてこの問題「本当に左からやっていけばいいのか」「実はどこかの真ん中を取った方がいいんじゃないか」という疑問があります。貪欲法の証明ですね。
貪欲法の基本は「明らかにその貪欲を選んだ方が、他の場合より良い状態になる」という部分にあると思っています。
例えばこんな文字列が合えたえられたとしましょう。HOGEFUGAはなんでもいいですし、なんなら空っぽでも良いです。
HOGEHOGEaxaxaFUGAFUGA
今回の「左から順番にこなしていく」をしていくと、もうHOGEHOGEは見なくていい状態です。
ここで「実は左のaxaを変換するよりも右のaxaで変換したほうが良い答えになる」という可能性があるか。という疑問です。
答えはノーです。
要はこのどちらがいいかという話ですよね
- HOGEHOGE...xaFUGAFUGA ←早く処理したほうが後に続く文字が純粋に多い
- HOGEHOGEax...FUGAFUGA
どちらにせよその後の右に残る文字列が、後者の方が短くなります
答えの量としては変換した後の右側の文字列において、1は2を含んでいます。
まず、1のほうが答えが長くなります。左から取ってた方が優れています。
これを一番左から見て言って、変換できないのであればHOGEHOGEは一番左から見てしまっているのでどうせ今後も変わりません。できるのであれば、上記の通り早めに変えていたほうが後が優れています。
コンテスト中にいちいち貪欲法を証明することはめったにないですが「明らかにこの取り方をした方が優れている」といった目星がつけられるようになりたいな～と言った振り返りでした。
そういうことを誰にでもわかりやすく話せて使える引き出しを作ってあげられる人間でありたい。
E : 青木君のいたずら
意外と実装が面倒だった問題。逆算して考えるのであれば下記を見る。
- 値をどんどん3で割っていく
いたずらされてないなら3^30⇒3^29⇒…となる - どこかで3で割ると1余る瞬間があるので、それがイタズラされた瞬間
- 1余る瞬間が2回来るのはダメ
- 30回割り切った後に1以外の数が余るのもダメ
と、ここまでが私が本番でやった実装なのですが、後から
- 30個分のイタズラ結果を最初から計算しておく
これでいいじゃんと思ってしまった。
全部のパターンが探索できる問題は全探索が強いです。間に合うならいいじゃん。
F : ダブルブッキング
絵にかいたようないもす法。
いもす法のミソは時間が永遠に続いていようが変化が発生する順に変化が発生する瞬間だけ注目すればいいってことで良い気がしてます。
開始時刻と終了時刻は完全に別物として考えていきましょう。
例えばpairで<開始or終了予定時刻,会議開始なら+1で終了なら-1>を作る。
そして予定時刻でソート。
最初会議のかぶり数を0としておいて、ソートして予定時刻順になった配列に対して±1を加えていく。
こうすれば会議が最大いくつ被っているかを見ることができますね。始まったら+1,終わったら-1。一瞬でも2以上になる瞬間があったらそれはダブルブッキングしてます。
注意点として、今回の形は問題ないのですがある会議が終わった同時刻に別の会議が始まる場合に、別の誤った配列構造を作って会議が終わった判定の前に始まった判定を先にしてしまって、ダブルブッキング判定してしまうことがあります。
G : べき表現
The 算数問題。
小学生の頃分銅を使った問題があったのを思い出しますね。
3進数が身についている人なら秒殺問題になるかと。
発想に至る道筋としては、計算については
「3^iを加える」か
「3^iは減らして、もっと大きい数にをカバーしてもらう」
では計算はどちらからいくか
「大きい数字から攻めるか」
「小さい数字から攻めるか」
そして「下から攻める」が正解です。証明的な意味では貪欲法に似た感じですね。
上から決めてしまうと、後で小さい数字が減らされた時のカバーに入るかわかりませんから。下から決めていきましょう
1,3,9,27,81,...と3^iになるXに対して、N
- Xの3倍で割った余りがXなら、答えにプラスXが入り、NはX引いておく
- Xの3倍で割った余りが2Xなら、答えにマイナスXが入り、NはX足しておく
- 割り切れるなら何もしない
こうするとどの処理をしてもNは3Xで割り切れる状態になります。
3進数が身についているならこんな感じになりますかね
N=187
3進数で表すと
N=20221 (3)
- 一番下の位は1なので、Nから1を引き、答えに+1を入れる
N=20220 (3)
答え：+1 - 次は2なので、Nに3を足し、答えに-3を入れる（繰り上がり注意）
N=21000 (3)
答え：+1,-3 - 次は0なので、Nには何もせず、答えに+9も-9も入れない
N=21000 (3)
答え：+1,-3 - 次は1なので、Nから27を引き、答えに+27を入れる
N=20000 (3)
答え：+1,-3,+27 - 次は2なので、Nに81を足し、答えに-81を入れる（繰り上がり注意）
N=100000 (3)
答え：+1,-3,+27,-81 - 次は1なので、Nから243を引き、答えに+243を入れる
N=0 (3)
答え：+1,-3,+27,-81,+243
というわけで、243-81+27-3+1=187となります。
H : 折れ線グラフ
ちょっと苦労した動的計画法(DP)問題。Hに出すDPにしては難しくないか…？
貪欲でも行けそうだけどよくわかってない。
最初「できるだけ平らにしたら普通にAC出てくんない？」と思って出してみたら普通にWAで突き返されました。
この問題最大のポイントはNも合計も100と妙に少ない。
100なんて3～4乗ループ前提なので、多少強引な力技も使えるってことです。DPに多そう。
40,20,10以下あたりが来るとさすがに露骨すぎます。半分全列挙！bit全探索！順列！！！
↑超露骨な奴
というわけで
dp[i][sum][before]と三つ分 のdpを作って起き
「i番目まで見て、現在の合計がsumで、直前にbeforeの数字を選んだ時の最小の合計長さ」を作ればよいです。
最後は0必須なのをお忘れなく。
ブログだけでゴチャゴチャ書くとややこしいタイプのDPなので細かい話は別でどうぞ。
I : ほくろ
ABCに出たらそこそこ虐殺が発生しそうなアフィン変換の幾何学問題。
この程度なら茶～緑diffくらいになりそうですが、これを二捻りくらいした問題で皆殺しが発生してる気がする。
線形代数はやり込むと深いことが多すぎてどんどん沼に入ってしまいますが…
とりあえず回転、拡大縮小、平行移動をいい感じに何回か正しい手順で行うと全部の位置関係を維持したいい感じの行列変換になってくれるんですよ（適当）
と、いっても今回は何が優しいかというと
- 平行移動と回転移動しかしてない
⇒平行移動してから回転移動しても、回転移動してから平行移動しても問題ない
⇒回転してから平行移動した前提で問題ない - 右目と左目の位置が最初はx軸上かつ、y軸対称だった
- 目の場所の中点は原点だった
最後に気づけば平行移動分はわかるので、あとは回転移動を求めればいいです。
サインコサイン。
計算式の確認はしませんが、Pythonなら複素数が標準装備なのでやさしい。
J : 終わりなき旅
SCC(強連結成分分解:Strongly Connected Component)で秒殺。一番早く解けた。
問題が聞いてるのは要は「ループしてる場所はありますか」という話。
SCCというものは要はループできる点のグループ（強連結成分）を抽出する典型アルゴリズムなので、この問題でそれを知ってて使える人にとっては一瞬です。
なんとatCoderライブラリに強連結成分求めるライブラリ入っちゃってるんですね～。
ちらほら閉路検出の方法で調べてみたのですが、だいたいがトポロジカルソートを行うほぼSCCと同じことを述べている為、SCCのことを調べれば同じ考えで行けると思いますので省略します。
K : 急ぎ旅
ダイクストラの基本に忠実な応用問題。楽しかったです。
最短経路を求める方法として最もよく使われるのがダイクストラ法です。
存じ上げない方は是非ともそちらをまずお調べください。とても便利なので。
最短経路を求める方法は主に3通りあります。ここで語るには厳しいので個人的な印象だけ。
- ベルマンフォード法
・スタート地点が決まってる必要がある
・負の閉路があっても生きる
・O(VE)なのでそこそこ遅いAfterContestでWriterにハックされて殺された程度には遅い
・負の閉路検知以外では有効だった場面は見たことない - ダイクストラ法
・スタート地点が決まってる必要がある
・負の閉路（グルグル回ってれば永久に距離を稼げるループ）があると死ぬ
・最適化してれば平均O((V+E)logV)でとにかく早い
・上記を満たすならこれ一択 - ワーシャルフロイド法
・全点同士の最短経路が求められる
・負の閉路があっても生きるし、検知もできる
・O(V^3)なのでとても遅い
・逆に言うと間に合う(Vが300程度)ならコイツを疑う
※V:点数 E:辺数
とりあえず今回は上記を考えればダイクストラを採用に至れます。
問題は最小の時間を使いつつ、できるだけ景観は稼ごうといったところです。
一般的なダイクストラでは距離や時間のみを計測していますが、今回は景観が条件に入ります。
だったら距離だけでなくこれまで稼いだ景観ポイントもダイクストラの判定にして
- 時間が早いほうを優先する
- 時間が同じなら景観ポイントが高い方を優先にする
といった更新にすれば良いです。
気にしてくれると嬉しい点としては
- 無限に景観が稼げる閉路が発生しないか？
⇒時間のほうが偉くて時間がゼロの道は存在しないので、時間損で問題ないです - 景観は二回目以降はカウントされないが問題ないのか
⇒最短路を行かなくてはならないので、二回も同じ町を通る手間が無駄です
逆に言うと「移動時間ゼロの道があったらちょっと困りましたね」って思いますね
⇒[その場合は移動時間ゼロの道で結ばれてる点は同じ点扱いにすればいいと思います。条件次第ではゴールだけはちょっとさらにひと手間必要なので面倒そう]
L : たくさんの最小値
セグメント木を使えますか？ではなくセグメント木を理解していますか？という問題。
あと個人的には数字以外の問題文ちゃんと読んでますかって問題だった。
セグメント木は平衡二分木を用いた区間演算をスピーディに行う方法です。
セグメント木に関する細かい説明や実装は他の解説にもあると思いますので今回の問題に限った概略だけ言います
まずこんな感じで7つの数字があるとしましょう
そしたら2つおきに「小さい数字が勝つ選手権トーナメント表」を作ります。
綺麗なトーナメント表を作るには2のべき乗個の要素が必要なので、足りない枠にはCPUとして絶対負ける数字で入ってもらいます。（厳密には単位元を入れる）
あとはどんどんトーナメントで勝ち残っていきましょう
2の優勝です。まぁ同点に関してはどっちにしても2が残るので。どっちか残ったんでしょう。
注目したいのはそれぞれの途中結果です。
途中結果を見ることで連続した範囲のまとめた計算結果がこれで見れてますよね。（図は一部のみ）
こういった連続した部分の事前計算をしておくことで計算を非常に高速化することができます。
例えば3～6の中の最小値を取りたいのなら、本来なら[3,4,5,6]の4か所を調べなくて張らなないところが、下の黄色の3か所だけでよくなります。2と2と5なので最小値は2ですね。
このケースだとたかが一か所ですが、数が大きくなればなるほど非常にお得になります。基本的にはO(logN)です。
先程も申し上げました通り具体的な理論や実装は他所に溢れてるのでお任せしますが、この問題はそれを理解した上で、セグ木で最小値は求まりましたね。では求めた最小値の逆走をしてください。という問題。
実際に今求めた3～6の最小値「2」の逆走のイメージとしては
一番上はどの区間も絶対に含んでいるので、引き続き下を調べる
次の0～3と4～7も、範囲は部分的に含んでいるし、最小値は2なので十分逆走できます。
ただ、次に下に行く場合「3～6と関係ない場所」や「最小値が2でなくなる場所」があります。この先は調べなくてもよいですね。
さらに下に降りましょう。同じように範囲外だったり最小値が違いものになるものは今後無視しても良いですね。
これで一番下までいけました。2つの2が検知できましたね。
このトーナメント表の高さはlogN個になりますので、一個当たりの最小値を調べるのにO(logN)になります。問題文をよく見ると最小値の出力個数にも制限がしっかりあるので、十分に間に合います。私はここを読み飛ばして3分くらい悩んだ。
問題で問われているセグメント木の特徴としては値の更新もO(logN)で行えます。
値が一個だけ更新するのであれば自分が通るトーナメント部分だけを全部更新すればよいので、トーナメント表の高さであるO(logN)で行えます。
本当にセグ木の基本的な仕組みについてしっかり理解してますかって感じの問題です。セグ木自体はいろんな応用方法があります。っていうか今回のNで私が結構な無茶をした。なのでその点では非常に良いと思えました。
M : 分割
この辺りからは人に説明できるほど理解してないのでわりと省略します。
このレベルの最小値求めろって問題、二分探索か、最小費用流か、最小全域木か、最小カット問題か、貪欲法か、dpか…………結構あるな。
この問題は数字の接続方法を見ているのと、Nが200と3乗くらいまでは平気で見てるので最小費用流で定めました。
考えのポイント
- 各種数字の接続関係を見るため、グラフの問題に帰着しそう
- 部分集合の分割は200だろうがスターリング数でクソデカになるためdpは難しい
- 前後関係しか参照しない為「どの数字が接続されているか」だけ見ればいい
こちらは説明できるほど理解できてないのでサンプル1でのグラフの作り方だけ
基本的に辺の容量は全て1です。
真ん中のは4から発してるもののみ書いてますが、要は「自分より先の数字」に「差の絶対値コスト」で繋がっています。19のfromからは22のtoのみで、22からtoには何も繋がっていません。
あと全てのfromからはゴールにコストcで直接つながっています。上のほっそい線。
こうすれば「自分が部分集合最後の数字になるならコストcを。次の数字があるならその次の数字を選ぶ」といった形でコスト張りができます。
最小費用流は慣れてないんですがなんとか浮かんでよかったです程度。
N : モノクロデザイン
正しい解法かはわかりませんが、私の解法的には平面走査・座標圧縮・セグメント木をバチクソに使えますかというのを聞いてきた応用問題。並べるとエグいな…。
完全な応用問題なのでこのレベルの人は解法サクッと書くだけでも良い気がするのと、正直もっといい解法存在するだろうと思うし、丁寧な解説ができる気が一切しない解法なので概要だけ。
考えのポイント
- 座標の範囲が10^9なので、マトモに計算させる気が一切ない
⇒座標圧縮して、平面走査でいくか… - 10^5個あるので、N^2は使えない。縦方向か横方向はlogNで済ます必要がある
⇒セグ木でなんとかできねえかなぁ………
- 全長方形のy座標を取得しておき、重複を省いて昇順に並べておく(syとする)
- セグ木を準備。セグ木はモノイドでも通るので問題ない。
・左から順番にtupleで(0,sy[i],sy[i],false)と登録しておく
・それぞれ意味は「ここまでの面積のある部分のy方向の長さの合計,左端y,右端y,ここの右端から右は反転させるか」という意味
・上の意味が通るように演算を設定し、単位元は(0,1e15,1e15,false)
⇒これのall_prodが、現在のy方向の面積がある部分の長さの合計になる - (a[i],b[i],d[i])と(c[i],b[i],d[i])を格納したリストを作成し、x座標順にソートする
- (all_prodして出てきたy方向の長さ)×(次のxまでの長さ)の面積をバシバシ合計する
- 値の更新はそのy座標が出てきた回数が偶数だったら(0,sy[i],sy[i],false),奇数だったら(0,sy[i],sy[i],true)で更新する
なんとなく、ここまで書いたら整理した昇順yに十分大きな値や十分に小さな値を加えておいて、累積和で良い感じにやる方法とかないかなぁとかも思えてきたんですけどね。うー、なにがあるだろ。実装も重かったです。
O : コンピュータ
正しい解法かはわかりませんが、貪欲法・動的計画法・しゃくとり法に関する発展問題ですかね。
こちらも詳しく解説できる理解力を持ち合わせていないので解法だけ
考えのポイント
- 漸化式を愚直に立ててみるとO(N^2)になるDPが完成するので、そこからどこが簡略化できるか考える
- 立てた漸化式は広義単調増加であることに気づく
- しゃくとり法で簡略化ができる
- DPをとにかく考える
このパターンはとにかく「愚直なDPに対してどこが簡略化できるか」である
というわけで立てた式は
dp[i] : その日までにかかる費用の最低額
dp[i] = min(dp[j]+i日目までに必要な機械の最高額) (j<iかつ、dp[j]+最高額≦その日までの収入合計)
このままだとjに該当する過去の日程を全部調べなくてはいけないのでO(N^2) - 「i日目までに必要な機械の最高額」「その日までの収入合計」は容易に事前計算できる
- このdpは実は帰納的に広義単調増加であることに気づくと、「機械最高額」は常に変わらないのでdp[i]はdp[j]からdp[i]まで飛べる（収入合計が足りる）一番左端からだけ見ればよい
- 左端に「現在の日数」右端に「既に購入できることが確定した日程」としたしゃくとり法でdpが埋まる
以上です。さあ今日はARCなんだからこの後はゆっくりしーよっと。
