phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

問題が解けない原因を考えたい

背景

競技プログラミングの能力を鍛えたい。
ただ、何ができなくて解けなかったのか?や、問題の難しい部分はどこなのか?など簡単な抽象的・体系的でとらえたいお気持ち。
なんとなく思ったことがあるので、それを書き出して整理してみる。

「問題を解く」とは?

「問題を解くこと」=「アルゴリズムを考えること」+「アルゴリズムを実装すること」と考えてみる。

アルゴリズムを考えること」

f:id:phyllo_algo:20180117232055p:plain
アルゴリズムを考えること」=「"問題"と"アルゴリズム"を辺でつなぐこと」

"問題"が与えられたとき、"問題"を"分解または言い換え"て、アルゴリズムの"使い方や制約"を踏まえて"アルゴリズム"を適用する。
ただし、"問題"以外のノードは与えられないため、自分で利用可能なノードを増やす必要がある。

また、SRM形式は辺を1本つなげればよいが、Marathon形式は重み付きグラフになってその最大化を行う。

問題が解けない=辺をつなぐのを失敗すること

"問題"から"アルゴリズム"までの辺を貼ることに失敗すると問題を解くことができない。

「分解・言い換え」のノードが足りない

"問題"を「グラフにして考えてみたり」、「複数の問題に分解したり」することに失敗。

ここの部分のノードの作り方が難しい問題は、「難しい」問題の印象。

「使い方・制約」のノードが足りない

アルゴリズム自体は知っていても、その"使い方や制約"をきちんと理解できておらず、適用できない。

例えば、動的計画法というアルゴリズムは知っていても、その使い方で「状態設計」「遷移」「高速化」などがちゃんと考えられないと、ノードが作れず、辺を貼るのに失敗する。
f:id:phyllo_algo:20180118004355p:plain

アルゴリズム」のノードが足りない

そもそもアルゴリズムを知らないとお話にならない。

辺が張れていない、間違って張ってしまった

ノードは用意できてもノードとノードの関連性をちゃんと理解できていないと張れると気付かなかったりして失敗。
また、張れると思って張ったら実は嘘解法で張れない辺を張ってしまって失敗。

勉強すべきこと

問題が解けない時、「ノードが足りていない」のか、「辺が張れなかった・間違って張った」のか考えたい。

ある程度、頻出パターン(頻出ノード、頻出エッジ)があるようで、効率的に勉強するには頻出パターンから攻めたほうがよく、「"使い方・制約"と"アルゴリズム"」の部分は体系的にまとめられている。
他には、グラフ系・文字列処理系・幾何系など特定分野に絞って勉強するのもよいのかも。

”分解・言い換え”ノードを増やす

あんまり体系的にまとまっていない気がするし、問題に合わせて考える考察力・発想力が問われる気がする。

"問題"側から"分解・言い換え"側を考える場合は、いろんな問題を解いていろんな言い換えや分解方法を憶えておくか、それらの発想の基となる既存の理論・学問を勉強したりとかが必要なのかも。。。

"使い方・制約"側から"分解・言い換え"側を考えることもできるかもしれなくて、ある程度関係ありそうなノードを考えて辺が張れるか考えてみたり。
また、小さいパターンで実験してみて問題に含まれるパターンを見つけたりというテクニックとかも有効かも。

典型とかもあって、「絶対値を見たら45度回転」とか「Nが小さければbitで2^N全探索できないか」とか、こう来たらこう考える、みたいなのもあるっぽい。

"使い方・制約"ノード、"アルゴリズム"ノードを増やす

アルゴリズムの教科書とか。
"アルゴリズム"の方だけ覚えておけばという感じになると、"使い方・制約"ノードが作れない場合もあるので、できるだけいろんなパターンを覚えておきたい。
使い方・制約を1種類だけしか覚えなかったり、公開されているライブラリからだけで勉強したりと、問題を考えたときに"使い方・制約"ノードが足りず、辺を貼るのに失敗しそうなので、気をつけたい。

その他

  • 典型
    • 頻出パターン(頻出ノード、頻出エッジ)
  • 枝狩り
    • 無駄なノードやエッジを作らない
  • 嘘解法
    • 本当は張れないエッジを張る
  • アルゴリズムを実装すること」

Weathernews Programming Competition

概要

圧縮やRangeCoderの勉強のつもりで参加。

最終順位は26927.87点で20位。
といっても、一つ前との差分値をRangeCoderで圧縮しただけのコード。

問題

5分おき4観測分の衛星データが波長(16チャネル)ごとに64枚ある。このデータすべてを可能なかぎり圧縮・回答するプログラムを作成せよ。
スコアは、bz2の-9オプションでのサイズbase_comp_sizeに対して、「max(0.0, (1.0 - 圧縮サイズ/base_comp_size) * 10^6)」で計算される。

最終的に提出したアプローチ

  • 各画像ごとに、2byte単位で読み込み、直前の2byteとの差分を作成し、それをRangeCoderで圧縮

振り返り、というか勉強

ロスレスな(動)画像圧縮、ファイル圧縮あたりが関係しそうということで、そこらへんの勉強のために参加。
いくつかメモ。

画像形式

画像形式でパッとでてきたのがPNG形式で、wikipedia見てみると結構いろいろ載っていて勉強になった。

Portable Network Graphics - Wikipedia

やっていることは「フィルタ処理→圧縮」。
フィルタ処理では「左との差」「上との差」「左と上の平均値との差」「左と上と左上の値を使ったPaethアルゴリズムでの予測値との差」、圧縮はLZ77とハフマン符号の組み合わせ。

この記事を読んで「どっかの値を使う(位置を保存)」とか「ある位置との差分を使う(差分を保存)」を考えてた。
けど、ちょっと複雑な「いろんな情報からそのピクセル値の予測をしてその差分を保存」のようなアイデアは保存する情報が増えて圧縮あんまりできなそうと思ってしまっていたので、全然考えてなかった。

Lossless JPEG - Wikipedia

Lossless JPEGなど損失なしの画像フォーマットがいくつもあるようだったので、それをちゃんと調べられていなかったのは調査不足だった。

1byte単位か2byte単位か

最初、hexdumpコマンドとかで眺めてて、偶数byteと奇数byteで分けて考えてみてもよいかなと思い、それを考えた。
片方はほとんど種類数がないので結構つぶせそうで、もう片方のbyte列をどう圧縮するか?が重要かと考えていた。

しかし、「上位byte列+下位byte列」で扱うと、それぞれ別に圧縮しても、まとめて圧縮しても、あまり圧縮効果が変わらず、正の点数が取れてなかった。
他にも、差分を取って圧縮するときに「正か負か」と「差分値」を保存するよう別々に分けようとすると同様に圧縮効果があまり得られず。
結局、twitterでも見かけていた「2byte単位」でまとめて扱って~というのが必要だった。

RangeCoder

エントロピー符号化で、Huffman Codingは情報理論とかでも知っていたけど、さらに圧縮率の高い算術符号化(≒RangeCoder)があるとのことで、それを実装するのを目的にすることにした。

Algorithms with Python / レンジコーダ (range coder)

RangeCoderの実装や内容は上記のページを参考に、写経。
理解が怪しくて、1byte単位のコードはそのままでいいけど、2byteやそれ以上の単位を扱う場合の処理がうまく書き直すのに苦労してた。というか、提出コード、いろいろ変えたりして定数がおかしいまま提出してた、、、バグってるはずなのに普通に動いているよう・・・

予測符号化・変換符号化

http://www.pcsj-imps.org/archive/2013tutorial.pdf

終了後に調べた限りだけど、上記資料がまとまってた。
「予測符号化」というっぽいが、「次の値を予測し、予測値との差分値を符号化」をどうやるかがアイデアとして重要だったよう。

そもそも「隣接画素が似ている(画素の相関が高い)場合に、隣の画素を予測値として注目画素との差を取ることで、分散(値の種類数)を減らせて(冗長性を減らせて)、効率よく圧縮できる」ので、この考えだと「前の画素の値を予測値にする」の発展として、いろんな情報や予測手法(線形・非線形な手法、用いる予測器を切り替える「適応予測」など)を考える方向へ行けてたよう。

また、データを互いに相関のないデータへ変換する「変換符号化」も。
ブロックに分ける、離散コサイン変換、・・・。

Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017参加記

概要

AtCoderで開催されたマラソンマッチに参加してみた。
phyllo-algo.hatenablog.com
1stの方は比較的時間取れて取り組めたけど、2ndの方は時間がほとんど確保できず、だいたい2.5日分ぐらいしかできなかったと思われる。。

最終順位は6,961,040点で73位。

WAが2つ出てて、Timelimitを10秒で計算してるという大ポカ。

問題

重みなし無向グラフGが与えられる。そのグラフの頂点をG_embの連結な部分頂点集合に対応させる。
基礎点として5000点が与えられる。
G_embの方で部分頂点集合同士で隣接していた場合、+100点となる。
G_embの方で、ある部分頂点集合s(v)の頂点数が|s(v)|である場合、-Σ_v (|s(v)|-1)となる。
Gのすべての辺がG_emb側で隣接状態になっていた場合、ボーナスとして+100000点となる。
連結でない頂点集合だったり、不正な場合は0点となる。
最終得点が最大となるよう対応付けを求めよ。

最終的に提出したアプローチ

  • 初期配置は、Gの頂点の近傍ができるだけ近くなるようにランダム配置し、それをできるだけランダムに伸ばせるだけ伸ばしたもの
  • G_embの頂点を1つランダムに選び、その8近傍どれかにコピーする焼きなまし

時系列での振り返り

今回は考察重視で行きたいと思ってたけど、何が重要なポイントかは手を動かして見つけないとやっぱりダメだった。

初日~8日目(1日分ぐらい)
  • HHMM1とだいたい似ていて、焼きなましが有効そうな形をしていたので、HHMM1の反省をしつつ焼きなましをちゃんと書こうと考えた
  • 焼きなましについて勉強&&HHMM1の復習
  • おそらく、全部焼きなましに任せるとアレなので、HHMM1と同じように「形を固定化して割り当て問題」か、「近傍のうまい定義」をすればひとまずよさそうか、とか考えていた
  • 忙しかったり、体調不良であまり手を動かせず
10日目~12日目(1.5日分ぐらい)
  • ひとまず、HHMM1復習のコードを流用してHHMM2用に書き直して様子見
  • 実装が適当すぎて、スコアが差分計算できていないので、そこがボトルネックで回数稼げてないコードを作成
    • ビジュアライザーは、テキスト出力の簡素なモノしか用意してなかった
  • で、どうも、回数稼ぐよりも、初期配置が重要そうな感じだったので、初期配置を中心に考えることにしたが、前半「形の固定化して割り当て問題」を考えていた時のアイデアとか完全に忘れてて、0ベースで考え直し
  • 斜めだと、線をまたぐことができるので、平面グラフ的でなくても連結にすることができそうなので、斜めが肝っぽい
  • 前半の時の紙を見るに、形状のアイデアとしては、斜め直線型やダイヤモンド型をうまく配置させられれば多くの頂点に絡みそうと考えたらしい
  • 直線型よりもうにゃうにゃ絡み合う方が期待できそうな気もするので、ランダムに線を伸ばす感じのコードを作成(最終提出のやつ)
  • で、ここで(なぜか)ボーナス点を取りに行っていないことが気になって、上位とはそこが差になっていると考えたため、できるだけちゃんと辺をつなぎに行くような方法を考える方に走った
  • グラフが大きくなってもG_emb側で全連結になるよう辺をつなぎに行けるうまい方法が思いつけず、結局時間を無駄にしてしまって終了
13日目
  • あきらめて、書いてたコードを提出
  • 14日目は時間取れないのがわかっていたのでここで終了
SystemTest後
  • TLEが10秒のままという指摘をもらってマジか状態(今回は30秒)
  • スコア差分計算してないのは、結構どんな場合でも実装優先度は高そうなので早めに実装したほうがいい、という話をした
  • WAが2つ出てるけど、実装が大味すぎてるので、ミスってただろう、という感じ(おそらくスコア計算の部分で0点なのに0点じゃないと返してる気がする)
  • 「完全グラフ埋め込み」というのがtwitter流れてるのをみて天才か、と思った
    • 時間取れても至れたか怪しいので、ARC点数でいうとアイデア思いつくのは600点ぐらい、具体的な形状を見つけるのは800点ぐらいだと思う

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017参加記

概要

AtCoderで開催されたマラソンマッチに参加してみた。終了30分前なので、時系列で振り返ってみる。
システムテスト前のスコア・順位は156,999点で66位/298人。おそらくシステムテスト後は順位下がる・・・

最終順位は720,841点で62位でした。

今回は知り合いと競争してて、知り合い内では3人中3位という感じで効率の悪さと実力不足が明らかになったなぁという感じ。
とはいえ、マラソンマッチはちゃんと参加できたことがなかったのに対し、今回は比較的時間使えていたので、完敗。

問題

重み付き無向グラフGが与えられる。そのグラフの頂点を別のグラフG_embの頂点にマッピングする。
もしG_embにマッピング後、G_embでの頂点で隣接辺だった場合、Gでの辺の重みが適用される。
G_embはKing's Graphというグリッドの斜め方向頂点にも辺をつないだグラフが与えられる。
マッピング後のG_embでの重みの合計が最大になるような頂点のマッピングを求めよ。

最終的に提出したアプローチ

  • まずは山登り
  • その後、グラフが密な場合はちょくだいさんサーチっぽいの、疎な場合は焼きなましのハイブリッド
  • 頂点のマッピングは、G_embの中心から渦巻き状に広げていく形で決め打ちし、何番目にどの頂点を割り当てるかを考えた
  • ちょくだいさんサーチっぽいのは、重複排除がうまくできなかったので、各番目で上位数件で切り捨てる感じで多様性を確保する感じ
  • 焼きなましの方は、2-optっぽく、適当に2点選んで交換するので近傍探索。悪化した場合での採択率を山登り時点でのスコアとかで微妙に変えてる
  • 評価値は生のスコア

時系列での振り返り

初日
  • 問題理解自体は簡単そうな雰囲気だけど、どこらへんが難しいポイントかわからないので、数日は適当に実装しながら考えた
  • 初日は「ビームサーチ」か「n手先読み」を考えてた
  • 実装は適当に1点を決めてそこから8近傍に頂点を増やしていく感じで、先読みを1ターンだけするものを書いた
2日目
  • 状態数が多すぎて試せる分量が少なすぎるので、8近傍に頂点を広げていくビームサーチを実装しようと書いてみた
  • この時点では適当な調整をして148kぐらいだったけど、サイズが大きい場合に探索量が多くTLEしてしまったりスコアに大きな差がでてしまう問題があった
  • というか、ビームサーチの時間のコントロールが難しいというのが身をもってわかった
3日目
  • ビームサーチではなく、他の方法もありそうか考えてた
    • 決定的な手法とか、マッチングとか
    • 焼きなましとか試してみたけど、うまくいかず、ちょくだいさんサーチっぽい感じで何回も最初から最後までを繰り返す感じの探索でやってみたら悪くなさそうだったので、この方向で書きはじめ
  • ここで、ビジュアライザーを作ってないことが気になったので、C#で最終状態を出力する雑なものを作成
4日目~5日目

f:id:phyllo_algo:20171130234710p:plain

  • ビジュアライザー見ると、形がひどいときがあることに気づいた(上みたいなの)
  • ある程度中央付近に固まっていた方が都合がよさそうだろうと思って、距離が離れるほど評価値が下がるように書いた
  • けど、うまくいかなくて、ここで、「どこに何を」割りあてるかだと状態数が多くなりすぎるので、形を決め打ちして「何を」割りあてるかだけにすればよさそうと気づいた
  • 形はいろいろ考えられそうな気がするけど、とりあえず中心からグルグル渦巻き状に増やすようなものを考えることにした

f:id:phyllo_algo:20171130235755p:plain

  • 形の最適解の考察としては探索結果を見る感じだと平行四辺形っぽい形が多いので、辺の数的にもそういう形だろうと考えてた
  • けど、最後そこまで調整たどりつけなかった
6日目~7日目
  • メモリの制約からpriority_queueで保持する状態数に限りがありそうなので、適当に状態を削って探索
  • ただ、サイズが大きい場合は、十分な探索ができてなくて、イマイチスコアがでない
  • 他のアルゴリズムに浮気しつつ手を動かしてたけど、ダメだった
8日目~11日目
  • ここらは、ちょっと細かい考察と実験をしながら、提出の方はパラメータとかちょこちょこ変更して提出する感じで進めてた
  • 多様性確保のための状態の間引き方でうまい方法が思いつかず、ネットで情報調べたり勉強したり、いろいろ試してた
    • いろいろ取り入れようとすると探索量が減ってスコアが下がることを繰り返しててて、つらぽよ
    • あと、n手先読みとかペアを作ってからそれをくっつけてく方法とか別アプローチを試したりしてたけど、どれもイマイチで、つらぽよ
  • この時点での提出の最高点は154kぐらい
12日目
  • いろいろ出力して観察していたところ、どうも焼きなましっぽい動きをしてそうに見えたので、焼きなましでいけないか検討始めた
  • すると、調整が雑でもスコアが結構伸びた(!)
  • しかし、スコアが大きい場合、ちょくだいさんサーチっぽい方がスコアがよかったので、焼きなましとハイブリッドで実装
  • この時点での提出最高点は156kぐらい
13日目~最終日
  • 高速化を試していないことに気付いたので、時間計測とかintをshortにとかを置き換え
    • あと、cinをscanfにしたりしたらなぜかスコア下がったりして最終提出は変えなかった、、、
  • 500点ぐらい増えて最高スコアの156,999
    • ただ、何回か提出してみると、上振れスコアのようで、再提出すると数百点平気で下がってしまう運任せコード
  • 受理率が悪すぎて効率の悪い探索ばかりしていそうだったので、近傍の定義を効率化しようとして、ランダムに任意地点の2点をswapするのではなく、隣同士の2点を交換し続ける感じで書いてみたけどスコア悪化
  • あとは冷却スケジュールと評価関数が何もできていないので、そこを最後に詰めようと実験
  • 冷却スケジュールの方は、診断人さんまとめの焼きなましページを参考に、ちゃんと調整してローカルだと+600点ぐらいになったので、喜々として提出したら下がって絶望
  • 評価関数はいい形悪い形とかで加点減点を追加したらスコアが下がってしまって絶望
    • 頂点の辺の合計とか、何番目に大きい辺を使ってるかとか
  • 最終日で調整する時間がないのに、ローカルとオンラインのスコアの相関がなくなってて、絶望しながらオンラインの提出調整するしかなかった
  • 絶望
  • 絶望
  • 結局点数上がらないので、上の提出最高得点のコードを最終提出して、絶望のうちに終了
最終提出後~寝るまで
  • 振り返ってみてみると、焼きなましの受理率がものすごく悪いし、無駄なスワップとか繰り返しまくっているのでだいぶ改善の余地がある
  • 探索量とかは結構稼げてるから「焼きなまし+評価関数工夫+ヒューリスティックルール」が正解だったかなぁとか思う
  • あと、問題の切り分けとして、グラフの密度が「密」「疎」「スコアが大きい」あたりで分けて考えたけど、「疎」と「スコアが大きい」時が重要なのに全然詰められていなかった・・・
  • ビジュアライザーは、最終結果を見るものしか作れてなかったけど、「やりながら見る」や「やってる途中経過(探索しているもの)を確認できる」ようなものを用意しないと厳しいなと思った
  • 他にも試したけどここに書いていないものは、みんなの解答出てから反省時に振り返りたい

ARC085 D. ABS

問題

N枚の山札が与えられる。上からi番目のカードの数字はa_i。
XさんとYさんが、この山札を使ってゲームをする。最初にXさんはZが書かれたカード、YさんはWが書かれたカードを持っている。
2人は交互に「山札の上から1枚以上のカードを取り除く。最後にひいたカード以外は捨てる」という行動を繰り返す。
山札がなくなるとゲーム終了で、最後のスコアは両者のカードの数値の差の絶対値となる。

Xさんは最終スコアが最大化するように、Yさんは最終スコアが最小化するように行動する場合、最終スコアはどうなるか?

制約

  • 入力はすべて整数
  • 1 <= N <= 2000
  • 1 <= Z,W,a_i <= 10^9

解法1

ゲームの先読み。


Yさんがi番目までカードを引いたとする。
Xさんはi+1番目から何枚かのカードを引くことになるが、このとき、最終スコアがどのようになるかがそれぞれの枚数の時でわかっていれば、それで最適な枚数を引けばよい。(Xさんは最大化したいので、最終スコアが最大になる枚数を引くことになる)


int dp[pos][turn] := turnさんの番で、相手がposまでカードを引いてる場合の最終スコア


として、メモ化再帰すればO(N^2)で求められる。

// ZとWはカードの数値を入れた配列vの最初2つに入れておく
int dp[2005][2];

int dfs(int pos, int turn){
  if(dp[pos][turn] != -1) return dp[pos][turn];

  int ret = (turn==0)?MIN:INF;
  REP(i,pos+1,N){
    int tmp;
    if(i == N-1){
      tmp = abs(v[pos]-v[i]);
    }else{
      tmp = dfs(i,1-turn);
    }

    if(turn == 0){
      ret = max(ret, tmp);
    }else{
      ret = min(ret, tmp);
    }
  }
  return dp[pos][turn] = ret;
}


// dfs(1,0)が答え

解法2

想定解法はO(1)。


最初、Xさんが取れる行動はいくつかあるが、「全部取る」「1枚残す」だけ考えればよい。
全部取る場合、Xさんはa_N、YさんはWになる。最終スコアはabs(a_N - W)。
1枚残す場合、Xさんはa_{N-1}、Yさんはa_Nになる。最終スコアはabs(a_{N-1} - a_N)。


2枚以上残した場合、Yさんは1枚残して最終スコアをabs(a_{N-1} - a_N)にすることができる。
なので、Xさんの最終スコアはabs(a_{N-1} - a_N)より大きくはならない。(そうできる場合はYさんによってabs(a_{N-1} - a_N)にされてしまう)
結局、Xさんは、abs(a_N - W)かabs(a_{N-1} - a_N)かの2つしか選ぶことができないので、どちらか大きい方になるように行動するしかない。

反省

コンテスト中は無駄な状態を考えて、
dp[i][j][turn]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目でturnさんの番が回ってきたときの最大スコア
を考えてしまっていた。
けど、「1枚以上取る必要がある」ので、自分の持ってたカードの数字は保持しておいても意味がなく、結局i,jの2つ区別して持つは必要ない。


一応、メモリの持ち方をdp[N][N]にして考えることもできて(turnの部分はiとjを見て決められるので不要)、dp[i][j]として、
dp[i][j]:=Xさんが最後に取ったのがi番目でYさんが最後に取ったのがj番目のときの最大スコア
として考える。
i,jを見てどちらの手番かがわかり、かつ、手番の方のiまたはjの値は依存しないので、i,jで小さい方がiだった場合、0~j-1までのdp[i][j]の値は同じなので、1回だけ計算すればよい。

  for(int i=N-1; i>=0; i--){
    for(int j=N-1; j>=0; j--){
      if(i == j) continue; //あり得ないパターンなので無視
      if(i == N-1 || j == N-1){ //最後のカードを取った場合
        dp[i][j] = abs(v[i]-v[j]);
      }
      else{
        int ret = (i<j)?MIN:INF;
        if(i<j){//Xさんの手番
          if(i == j-1){
            REP(k,j+1,N){
              ret = max(ret, dp[k][j]);
            }
          }else{
            ret = dp[j-1][j]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー
          }
        }else{//Yさんの手番
          if(j == i-1){
            REP(k,i+1,N){
              ret = min(ret, dp[i][k]);
            }
          }else{
            ret = dp[i][i-1]; //前に持っていたカードに依存しないので、すでに計算済みの値をコピー
          }
        }
        dp[i][j] = ret;
      }
    }
  }

//dp[0][1]が答え

yukicoder No.595 登山

問題

N個の地点が1~Nまで順番に直線上に並んでおり、地点iの標高がH_iで与えられる。
地点1からスタートし、すべての地点に1回以上訪れたい。終了地点はどこでもよい。
移動は2種類あり、「隣接地点に移動する場合、登る方向に移動する場合のみ標高の差」か「ワープによる任意地点への移動にはP」のエネルギーがかかる。
最小エネルギーを求めよ。

制約

2 <= N <= 2*10^5
0 <= P <= 10^9
0 <= H_i <= 10^9

解法

コンテスト時間中は、左から順に、隣が登る場合はワープして降ってくるor登るか、隣が降る場合は隣に降るかその地点にワープする感じで、
dp[i][x] := i地点までの最小エネルギーで、i地点にいる場合x=0、いない場合x=1
というのを更新していく感じで書いていた


しかし、降る場合について、右から登ってくるルートを考慮できておらず、
f:id:phyllo_algo:20171111125323p:plain
のような場合、「地点1→地点3→地点2→地点1→地点4→地点5→地点7→地点6→地点5」というルートを考えてしまっていた。
(この場合の最小ルートは「地点1→地点3→地点2→(地点1)→地点7→地点6→地点5→地点4」というルート)


左からも右からも降るか登るかすべてを考える必要がある。左右どちらからくるかを区別すると、
dp[i][x] := i地点に左から訪れている場合x=0、右から訪れている場合x=1の場合の、1~i地点までの最小エネルギー
とすれば、i-1とiの地点でのdpの値を考えて、

  dp[0][0] = 0;
  REP(i,1,N){
    // i-1  i
    // -> & ->
    dp[i][0] = min(dp[i][0], dp[i-1][0] + max(0LL,H[i]-H[i-1]));
    dp[i][0] = min(dp[i][0], dp[i-1][0] + P);

    // -> & <-
    dp[i][1] = min(dp[i][1], dp[i-1][0] + P);

    // <- & ->
    dp[i][0] = min(dp[i][0], dp[i-1][1] + P);

    // <- & <-
    dp[i][1] = min(dp[i][1], dp[i-1][1] + max(0LL,H[i-1]-H[i]));
    dp[i][1] = min(dp[i][1], dp[i-1][1] + P);
  }

のような遷移を考えられる。

答えはdp[N-1][0]かdp[N-1][1]の小さい方。

AGC017 C. Snuke and Spells

問題

N個のボールが一列に並んでおり、各ボールには数字が書かれている。
魔法を使うと、今あるボール個数と同じ数字が書かれたボールを消すことができる。また、魔法は連続的に行うことができる。
例えば、{1,3,3}だった場合、魔法を2回連続で行うと、{1,3,3}->3個あるので3が書かれたものが消える->{1}->1個あるので1が書かれたものが消える->{}となる。

各ボールは単位時間ごとに、ボール1個だけ数字が変化することがわかっており、変化する回数はM回であることもわかっている。
ここで、各単位時間ごとのボールの状態に対して、いくつか数字を書き換えて連続魔法で全消しができるようにする最小書き換え回数を求めたい。

制約

1 <= N,M <= 2*10^5
1 <= ボールの数字 <= N
1 <= 変化するボールの場所 <= N
1 <= 変化した後の数字 <= N

解法

まずは、あるボールの状態に対して、ボールの最小の書き換え回数を求める問題を考える。


魔法を発動するときのボールの位置は無関係なので、あるボールの状態をソートしたものを考える。
例えば、{1,3,3,5,5}のような場合、魔法を連続発動することで、全消しができる。
どういうときに全消しができるか考えると、

i 1 2 3 4 5
x 1 3 3 5 5

インデクスが5から5が2個、3から3が2個、1から1が1個、、、と、NからNがa個、N-aからN-aがb個、、、と続けられればよいことがわかる。
また、例えば、

i 1 2 3 4 5
x 1 3 3 4 4

の場合は、インデクスが5のとき値が4なので、全消しすることができないことがわかる。
たとえば、この4を5に書き換えると、インデクスが5から5が1個、4から4が1個、、、となり全消しができる。


ここで、全消しができる条件を考えると、各インデクスの部分について、ボールの数字で、すべてのインデクスをボールの数字の連続でカバーできるかどうか?になっている。(上だと、各数字のインデクスのところから各数字の連続ですべてのインデクスをカバーできている)


(難しいが)、これを扱うのに、数字aについて、[a-数字aの個数,a]という範囲を考える。
上の全消しができない場合の例{1,3,3,4,4}を考えると、カバーしている範囲の数を各インデクスで考えると、

i 1 2 3 4 5
r 1 1 2 1 0

のようになる。
5のときカバーできていないので、他の2以上になっているところから5のところに数字を書き換えてあげれば全面カバーができることがわかる。

ここで、書き換えてあげる必要がある数字の個数というのは、カバーされていないインデクス==0になっているところの数なので、これを求めてあげればよい。


数字が変化した場合は、各数字の個数から上のカバーしている範囲の数のところが1か所減って1か所増える、という変化を起こすので、各単位時間での変化はO(1)で更新できる。
前の状態で0の個数がわかっていればこの更新時に0になるかどうかみれば、こちらもO(1)で更新できる。

AGC017 B. Moderate Differences

問題

N個のマスの一番左にA、一番右にBが書かれており、それ以外は空白になっている。
いま、空白のマスに、以下の条件を満たすように数字を入れることができる。

  • 隣接するどの2マスについてもその差はC以上D以下

このとき、条件を満たすように数字を入れることができるかどうか判定せよ。

制約

3 <= N <= 5*10^5
0 <= A,B <= 10^9
0 <= C <= D <= 10^9
変数はすべて整数

解法

Aの右隣の空白に何を入れられるか考える。
条件から、減らす方向に[A-D,A-C]と増やす方向に[A+C,A+D]の範囲の数字を入れることができる。
続けて、その隣には、ひとつ前の範囲[x,y]に対して、[x-D,y+D]の範囲が該当する。
最終的に、Bのマスまで来たとき、範囲にBが含まれているものが存在すればYESと答えられる。
しかし、この方法では、マスを進めるにつれ、範囲の数が2倍になっていくので、指数関数的に大きくなっていってしまう。


また、各マスで範囲が重なるような部分をマージするような方法をとったとしても、C==Dの時を考えればわかるように、範囲の数が多くなり、計算量が線形ではなくなるのでTLEしてしまう。


ここで気づきたいのは、各マスでは、「減らす方向への範囲更新」と「増やす方向への範囲更新」の2つの変化をさせられるが、これを行う順番はマスの位置に依存せず、それぞれを何回行ったか?だけでBのマスでの範囲が決まる。


増やす方向の回数をX回、減らす方向の回数をY回とすると、Y=N-1-Xとなる。
このとき、Bマスでの範囲は、[A+X*C-Y*D,A+X*D-Y*C]になる。
Xは、0回~N-1回まで考えられるが、それはループを回せばよいので、範囲内にBが入るかどうかを試せば、O(N)で求められる。

反省

変なコード書いてメモリ使い切ってPC再起動とかやらかしてしまっていた。
(さらに強制終了したせいでPC調子悪くなってダメ)
ちゃんと、計算量的使用メモリ的に問題ないアルゴリズムを考えてから書き始めること。

ARC076 E. Connected?

問題

x,y座標の(0,0)から(R,C)までの長方形を考える。
N個の長方形内の点のペアが与えられる。(各点はすべて異なる)
ペアの点同士を曲線で結びたい。ただし、長方形の外に出たり、交わってはいけない。
可能かどうか判定せよ。

制約

1 <= R,C <= 10^8
1 <= N <= 10^5

解説

Editorial - AtCoder Regular Contest 076 | AtCoder

いくつかサンプルを図で書いてみると、「ペアの点がどちらも長方形の周上にある場合、領域を2分割してしまって、それぞれ異なる領域にある点はどうやっても交差してしまう」というのがわかる。
そうでない場合は、曲線をうまく調整することで交差しないように書くことができることがわかる。


周上を1直線として見て、領域がoverlapしていないかを判定すればよい。


これは、「対応のある括弧の整合性判定(「((()()())((()()())))」みたいなの)」ともみなせるので、stackを使って判定すればよい。

反省

領域のoverlapの判定で、普通にミスってしまった。


領域を周上の座標にマッピングしたとき(l,r)とすると、l側でソートしておき、rをstackに入れながら処理していて、
今(l,r)を考えていて、直前のスタックにあるのがprとすると、

  • l < prの場合、かつ、pr < rの場合、オーバーラップしている
  • l < prの場合、かつ、r < prの場合、領域内にいるので、prとrをスタックに積んで次へ
  • pr < lの場合、新しい領域に入っているので、rだけスタックに積んで次へ

というやり方をしてしまった。
これだと処理が一つ抜けていて、例えば(1,5)、(2,3)、(4,6)のような場合、(2,3)の処理をした後、5と3がスタックに積まれているが、(4,6)を処理するとき、prで考えるべきは5と3両方なのに、3だけ確認して処理して、スタックに5と6みたいな処理をしてしまう。
なので、pr < lの時は、スタックからl < prになるまで全部取り出してあげる必要がある。

  stack<ll> st;
  st.push(R+R+C+C);
  int i=0;
  while(i<v.size()){
    ll l = v[i].l;
    ll r = v[i].r;
    ll pr = st.top(); st.pop();
    if(pr < l) continue;
    if(r<pr){
      st.push(pr);
      st.push(r);
    }
    else if(pr<r){
      cout << "NO" << endl;
      return 0;
    }
    i++;
  }
  cout << "YES" << endl;

ARC075 E. Meaningful Mean

問題

長さNの整数列aに対して、空でない連続する部分列の算術平均がK以上であるものの個数を答えよ。

制限

2 <= N <= 2*10^5
1 <= K <= 10^9, Kは整数
1 <= a[i] <= 10^9

解説

https://atcoder.jp/img/arc075/editorial.pdf
AtCoder Regular Contest 075 / Beginner Contest 063 解説放送 - YouTube


愚直に計算するとO(N^3)や、すぐ思いつく方法ではO(N^2)で、TLE。


ある範囲[l,r)について、条件は「(Σ_{i=l}^{r-1} a[i]) / (r-l) >= K」と書ける。
これを変形すると、

<=> Σ_{i=l}^{r-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - Σ_{i=0}^{l-1} a[i] >= (r-l)*K
<=> Σ_{i=0}^{r-1} a[i] - r*K >= Σ_{i=0}^{l-1} a[i] -l*K

<=> b[r] >= b[l]
   ただし、b[x] = Σ_{i=0}^{x-1} a[i] - x*K

となる。
この変換によって、配列bの要素の大小関係の問題(転置数)になる。


この問題は、値を座圧っぽく変換して、BITを使って0~i-1まででb[i]以下の個数を求めればO(NlogN)で計算できる。

反省

  • 数式で書き出せるものは書いて、変形してみる

yukicoder No.519 アイドルユニット

問題

N人(2の倍数)のアイドルがいる。
全員ペアを組ませて売り出したい。
しかし、ペアには相性度が決まっており、すべてのペアの相性度の合計値が最大になるようにしたい。
相性度の合計の最大値を返せ。

制約

1 <= N <= 24
0 <= 各ペアの相性度 <= 1000

解説

一般的には、グラフの重み付きマッチングの問題らしい。
ここでは、各アイドルがペアを組んでいるかどうかを状態として持つbitDPを考える。

単純に考えると、「各状態でペアを組んでいないアイドル2人を選んで、状態を更新」するように計算する。

int N;
int cost[30][30];

int dp[1<<25];

int main(){
  cin >> N;
  rep(i,N){
    rep(j,N){
      cin >> cost[i][j];
    }
  }

  rep(i,1<<25) dp[i] = -1;
  dp[0] = 0;

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
    }
  }
  cout << dp[(1<<N)-1] << endl;
  return 0;
}

これだとO(2^N * N^2)でTLEしてしまう。


実は上記のループは無駄なところがある。
状態が「100100」の場合を考える。
(この状態でjとkのループでは、「1**100」「1*01*0」「1*010*」「10*1*0」「10*10*」「1001**」を列挙して状態を更新している。)
ここで、
「100100」から「110110」と遷移して「111111」に至るケースと、
「100100」から「101101」と遷移して「111111」に至るケースでは、
同じペアの組み方なのに、2回計算してしまっている。

ペアの推移的には、
(0,3)->(0,3)(1,4)->(0,3)(1,4)(2,5)
(0,3)->(0,3)(2,5)->(0,3)(1,4)(2,5)
のような感じ。

このような場合、同じペアの組み方をするのは1通りだけ考えればよいので、状態の中でまだペアを組んでいないアイドル(状態が0のところ)を一人選んで、そのアイドルを必ず取る場合を考えて、そのペア候補だけ(kのループ)を考えればよい。

  rep(i,1<<N){
    if(dp[i] < 0) continue;
    rep(j,N) if(((i>>j)&1) == 0){
      REP(k,j+1,N) if(((i>>k)&1) == 0){
        int ii = i | (1<<j) | (1<<k);
        dp[ii] = max(dp[ii], cost[j][k] + dp[i]);
      }
      break; //これを入れるだけ
    }
  }

計算量は、O(2^N * N)になり、間に合う。

ARC047 B. 同一円周上

問題

座標平面上にN個の点がある。
各点の座標は整数で、ある点Pとのマンハッタン距離が同じであることがわかっている。(点Pの座標も整数)
点Pとしてあり得る点を一つ出力せよ。

制約

1 <= N <= 10^5
-10^9 <= x,y <= 10^9

解説

arc047


平面座標で、点Pからのマンハッタン距離が同じ点というのは、点Pを中心とするひし形の線上に乗る。
しかし、ひし形のまま扱うのは大変なので、テクニックとして45度回転させた座標を考える。
(x,y)->(x+y,x-y)という変換を考えると、上記の「ひし形の線上」というのが「正方形の線上」になり、とても考えやすい。

また、平面座標のどこかの候補点を探す場合、かつ、単純な方法では候補点が多くなりすぎる場合は、候補点を絞ることを考える。
(x座標・y座標それぞれで、線分の端点や交点などだけ取り出してその組み合わせを考える、など)


今回の場合、正方形の1辺の長さDが決まれば、点Pの座標は各点から距離Dの点のどこかということになる。(これだけだとまだ候補点が多すぎる)
もし正方形の1辺が決まれば、その辺の端点から距離がD/2の点(辺に対して両側が考えれる)が候補点になる。
そこで、正方形の辺を探す。


変換後の平面座標において、各軸について独立に出現している点の座標を考える。
その座標で最小の点と最大の点を見つける。
このとき、これらの点を端点とする辺が「正方形の1辺」の候補になる。
(例外としてN=1の時は1辺が作れないので別処理する)

これより長い辺を考える必要があるかというと、もう片方の軸の方で同じことをして見つけた辺がより長い場合、そちらが1辺の長さとしてふさわしい。
言い換えると、各軸について辺の長さを求めて、その大きな方が正方形の1辺の長さDとしてふさわしい。
(Dも候補として各軸について求めた2つがあると考えてもよい)


そして、候補点はそれぞれの点からD/2だけずれた点となる。(最大点+D/2,最大点-D/2,最小点+D/2,最小点-D/2の4点 最大点-D/2,最小点+D/2の2つ)
あとは候補点すべてについて実際に成り立つ点Pを確認してあげればよい。
計算量は、候補点の組み合わせで4*4=16個2*2=4個(または、各軸のDの候補を別に考える場合は、8*8=64個 4*4=16個)についてO(N)でチェックすることになるので、間に合う。

反省

  • 座標系で絶対値が出てきたら45度回転させてみる
  • 候補点が無数に考えられる場合、端点や中点など候補点としてありえる部分に絞って探索する

AGC015 C. Nuske vs Phantom Thnook

問題

N*Mのグリッドの各マスに色が塗ってある。
ある色の塗ってあるマスから別の色の塗ってあるマスへ移動できる場合、同じマスを通らずに移動する経路は高々1通りである。

Q個のクエリが与えられる。
各クエリは「(x1,y1)から(x2,y2)の長方形範囲でグリッドを切り出したとき、色の塗ってあるマスの連結成分がいくつあるか?」の質問であるので、これに答えよ。

制約

1 <= N,M <= 2000
1 <= Q <= 200,000

解説

Editorial - AtCoder Grand Contest 015 | AtCoder
AtCoder Grand Contest 015 - YouTube

どこから考えるかが難しい。


問題の最初の条件は「森(グラフ理論)」のことを言っている。
任意のグラフで連結成分を求めるにはUnionFindなどが使えるが、森における連結成分は「頂点数 - 辺の数」で求められる。

頂点数は、単純に2次元累積和で求められる。
辺の数も、各頂点に対して下方向か右方向にしか伸びないので、同様に2次元累積和で求められる(縦方向の辺、横方向の辺で独立に累積和を計算すると見通しがよい)。

計算量は、構築がO(NM)でクエリ処理がO(Q)なので、全体でO(NM+Q)。

反省

  • 「森における連結成分が"頂点数-辺の数"」というところに注目できないとほぼ無理そう
    • 連結成分をつないだり外したりみたいな方向で考えてしまうと余計無理そう
  • 一般的な解き方ではなく、「問題の条件に合わせた効率的な解き方」を考察できるようにする必要がある

ARC074 E. RGB Sequence

問題

N個のマスが横一列に並んでおり、各マスを赤、緑、青のいずれかで塗りたい。
しかし、 M個の「マスlからマスrの色の種類数がx」という条件を満たすようにしたい。
条件を満たすような塗り方は何通りか?10^9+7の余りを答えよ。

制約

1 <= N <= 300
1 <= M <= 300
1 <= l_i <= r_i <= N
1 <= x_i <= 3

解説

Editorial - AtCoder Regular Contest 074 | AtCoder
AtCoder Regular Contest 074/ Beginner Contest 062 解説放送 - YouTube
以下、だいぶ自分の解釈が入っているので、間違っているかもしれないことに注意。


種類数を数えたいので、DPが適用できないか考える。

  • 条件がない場合の数え上げ

まず、M個の条件がない場合を考える。
左から順番に塗っていって、i番目までの計算結果があるとする。
このとき、
dp[i][...]:=i番目まで塗ったときの塗り方の総数
を考える。
このとき「赤を最後に塗った場所がr」「緑を最後に塗った場所がg」「青を最後に塗った場所がb」というのがわかっていれば、
i+1に赤を使った場合は、dp[i+1][i+1][g][b] += dp[i][r][g][b]、
i+1に緑を使った場合は、dp[i+1][r][i+1][b] += dp[i][r][g][b]、
i+1に青を使った場合は、dp[i+1][r][g][i+1] += dp[i][r][g][b]、
と更新することができる。
しかし、O(N^4)になってしまっている。が、これはだいぶ無駄で、i番目のとき、rまたはgまたはbのどれか一つはiになっているところだけ考えればよいはずなので、iは必要ない。

dp[r][g][b]のとき、i=max(r,g,b)と計算できるので、
i+1に赤を使った場合は、dp[i+1][g][b] += dp[r][g][b]
i+1に緑を使った場合は、dp[r][i+1][b] += dp[r][g][b]
i+1に青を使った場合は、dp[r][g][i+1] += dp[r][g][b]
と更新できる。
これはO(N^3)なので、間に合う。

  • 条件を満たさないとき、数え上げない

条件を満たすときだけの数え上げをしたいので、dpの更新中にこの判定をいれたい。

(r,g,b)が決まっているとき、i=max(r,g,b)とすると、M個の各条件(l_i,r_i,x_i)について、「l_i<=r<=r_i」「l_i<=g<=r_i」「l_i<=b<=r_i」であるか確認して使われている色の種類数を確認して、x_iと一致するかどうか見ればよい。
そして、条件を満たさない場合はdp[r][g][b]=0としてしまえばよい。

しかし、r,g,bの三重ループの中で単純にM個のループを回してしまうとO(M*N^3)となる。
そこで、「vector < pair < int,int > > v」として、v[r_i][j] = pair(l_i,x_i)のように持たせて、各iでv[i]だけをチェックする。
iは0~Nの範囲で動くが、v[i]のようにM個の条件をiで分割して持たせると、O(N+M)になる。
全体ではO(M*N^3)はO(N^2*(N+M))=O(N^3 + M*N^2)となり、間に合う。

コード

#define MOD 1000000007

int dp[305][305][305];
vector<pair<int,int>> v[305];

int main(){
  int N, M;
  cin >> N >> M;
  rep(i,M){
    int l, r, x;
    cin >> l >> r >> x;
    v[r].push_back(make_pair(l,x));
  }

  ll ret = 0;
  dp[0][0][0] = 1;

  rep(i,N+1){
    rep(j,N+1){
      rep(k,N+1){
        int m = max(i,max(j,k));

        rep(ii,v[m].size()){
          int r = m;
          int l = v[r][ii].first;
          int x = v[r][ii].second;

          int cnt = 0;
          if(l<=i && i<=r) cnt++;
          if(l<=j && j<=r) cnt++;
          if(l<=k && k<=r) cnt++;
          if(cnt != x){
            dp[i][j][k] = 0;
          }
        }

        if(m == N){
          ret += dp[i][j][k];
          ret %= MOD;
          continue;
        }

        dp[m+1][j][k] += dp[i][j][k];
        dp[m+1][j][k] %= MOD;
        dp[i][m+1][k] += dp[i][j][k];
        dp[i][m+1][k] %= MOD;
        dp[i][j][m+1] += dp[i][j][k];
        dp[i][j][m+1] %= MOD;
      }
    }
  }
  
  cout << ret << endl;

  return 0;
}

反省

  • 条件を持つ数え上げとかは、桁DPとかでもよく見る
  • 無駄な状態を減らす
  • O(N)でM個の条件のチェックをする場合、位置に依存するならばO(NM)ではなくO(N+M)に落とせる

ARC074 D. 3N Numbers

問題

長さが3*Nの数列vが与えられる。この数列からちょうどN個の要素を取り除き、「前からN個の配列a」と「後ろからN個の配列b」を考える。
「aの総和-bの総和」の最大値を求めよ。

制約

1 <= N <= 10^5
1 <= 要素の値 <= 10^9

解説

数列vにおいて適当に1か所場所を決めると、そこより前からの要素が配列a、それ以降の要素が配列bと割り当てて考えることができる。
最大値がほしいので、配列aの方は大きい値からN個、配列bの方は小さい値からN個を取ればよい。


愚直に計算してしまうとO(N^2)でTLEしてしまうので、高速に計算できないかを考える。


欲しいのは「集合Sに要素xを追加したとき値の大きいor小さい上位N個の和」が高速に求められるようなもの。
上位N個を保持するのに使えるデータ構造はheap(priority_queue)で、これを使って、

  • 和と上位N個の要素を保持しておく
  • 要素xを追加したら和とheapに入れ、heapから1つ要素を取り出し、和から引いて捨てる

のようにする。
値の追加はO(logN)、上位N個の和の取得はO(1)で求められ、十分に速い。


配列bの方は、小さい方からN個&後ろから前に向かって考えると配列aと同様に高速に求められる。
別途配列などに配列aと配列bの上位N件の和の値を入れておくなどして、最後に線形に「位置iより前の大きい上位N個-位置i以降の小さい上位N個」の最大値を求めればO(NlogN)で答えが求まる。

反省

最初、何も考えずに、位置に対して最大値は"上に凸"になるのでは?と思って確かめずに投げてWAやTLEを出しまくってしまった。
ランダムに生成させてみると、

3
10 5 2 4 2 18 10 10 7

のとき、最大値は各位置で「x,x,4,0,-8,6,x,x,x」のように簡単にそうならないケースが見つかる。

ちゃんと確かめてからコードを書き始めること。