ctyl's problem solving

競技プログラミングが主な話題です。

yukicoder No.348 カゴメカゴメ

★4昇格.Union-find,木DP,DFSなど色々な要素が入っている問題でためになるのだけれど,実装がかなり難関.個人的には今までyukicoderの問題の中で最凶クラスの実装難の問題でした.


方針:輪の包含関係を根付き木で表現する.Union-findなどで各輪の強さを求め,あらかじめ構築しておいた木において『ある輪と,その輪のすぐ外側にある輪の両方を使用することは出来ない』という条件を満たすようにDPを行う.

Step 1:根の'.'が飛び地になることがあるので,周囲をもう一周'.'で囲む.サンプル4にこの操作をすると下の図のようになる(縦と横が2マスづつ増える).こうすることで一番外側の'.'はすべて共有されることになる.

f:id:ctylim:20160227173727p:plain:w300

Step 2:Union-findを使って'.'のつながり,'x'のつながりを一つの代表元にまとめる.上の図の丸で囲ったところが各素集合の代表元(の例)である.ここで注意すべき部分は'x'は周囲8方向に存在する'x'とマージできるが,'.'は上下左右の4方向の'.'としかマージできないことである.時間計算量: O(NM)

Step 3:根を左上の'.'を含む'.'のつながりとし,そこから一枚づつ'.', 'x', '.', 'x', ...と交互に剥がしていくようにグリッド全体を走査しながら木を作っていく(dfs).木に追加した素集合を訪れたかどうかはメモしておく(vis).ここでも'x'の内側にある'.'を探すときは周囲8方向をチェックすれば良いが,'.'の内側にある'x'は上下左右の4方向しかチェックできない.サンプル4では下のような木ができる.青が'.'で赤が'x'に対応する.時間計算量: O(NM\log (NM))

f:id:ctylim:20160227173658p:plain:w300

Step 4:赤のノード('x')のみを辿ってDPを行う(dfs_m).一例として,配列dp[i][0]には「マス目iにある輪より内側にある輪のみを使ったときの最大の強さ」,dp[i][1]には「マス目iにある輪を使い,かつ内側にある輪を使ったときの最大の強さ」を記録しておく方法がある.時間計算量: O(素集合の数)

サンプル4での計算例(更新則):

 dp[28] [0] = \max (dp[80][0], dp[80][1]) + \max (dp[89][0], dp[89][1])

 dp[28][1] = dp[80][0] + dp[89][0]

最後にノード0の子の強さをすべて足しあわせることで答えとなる.

yukicoder No.348


BFSもいいけどDFSの実装のコンパクトさが体感できたので,徐々に再帰は慣れていきたい.

yukicoder No.209 Longest Mountain Subsequence

DP★3.3ヶ月位前にも一度挑戦していて,その時は自分の方針のアラが探せず出来ずじまいだったが,今回は一発でACできた.

方針:{S_{i-1}-S_{i-2} \lt S_i-S_{i-1}}を満たす最長の上昇部分列の長さを今選んでいる要素のindex,直前に選んだ要素のindexの情報を持った上で求める.下はA= \left\{1,7,5,3,1,6,3,9,1 \right\} のときの例.各 iに対する最大値が A_iを最後に使ったときの最長の上昇部分列長である.自分の提出は左からの上昇列長を求めたら,Aを反転して同一の処理をしている.

f:id:ctylim:20160224181654p:plain:w500

yukicoder No.209


想定解が Q \leq 100, N \leq 100 O(QN^3) なのだけれど,意外と間に合うのね.

Codeforces AIM Tech Round Div.2 C Graph and String

本番はSCCに固執しすぎて実装が間に合わず.その後冷静に考えたらもっと単純な方法があった.

解法

まず気づきそうなこと:実線は辺,点線はそうでないとする.次のようなグラフの場合,bは一意に決定する.

f:id:ctylim:20160206160557p:plain:w250

そこで点線を辺とする(完全グラフから与えられるグラフを引いた)グラフに着目する.このグラフが下のように2つ(以上)に独立していると仮定する.

f:id:ctylim:20160206160600p:plain:w250

点線の両端は(a,c)で一意に決定する.

f:id:ctylim:20160206160603p:plain:w250

上と下のa,c同士は必ず結ばれる.

f:id:ctylim:20160206160604p:plain:w250

よってそのようなグラフの仮定は間違っていて,点線で構成されるグラフは連結である.それを確認した上で,(a,c)は辺で結ばれ,(a,a),(c,c)は結ばれないような判定をすればよい.幅優先探索などで深さの順番にa,c,a,c,...とメモして行って,最後に全ての頂点の組み合わせで前述の判定をすると上手くいく.

AIM Tech Round 2C

二部グラフの判定方があればそれを使えばよさそうですが,自分はあるかどうかすら知らないです.もっといい方法があれば教えて下さい). 時間内に解けたら美味しかっただけに悔しい回でした.

プログラミングが苦手な自分が競技プログラミングを始めた話

この記事はCompetitive Programming Advent Calendar 2015 Day22の記事です.

www.adventar.org

始めてから4ヶ月間競技プログラミングを無事に続けられているのですが,自分がどういう思いで競技プログラミングに対して取り組んできたのかを振り返っていこうと思います.アルゴリズムなどの具体的な話題は一切ありません.


自己紹介(前科)

まず自分の話をさせてください.実は(競技)プログラミングの世界はかなり前から知っていました.高校時代にまで遡りますが,当時は情報オリンピックの問題を見たりしていました.言語の基本文法やら何やらで躓いて時間ばかりが過ぎていき,その当時は結局「プログラミングというのは自分ができる技ではない」という結論に終わりました.余談ですが,数学オリンピックの方は中学のころから予選を通過し続けていて,最後の年はあともう少し頑張れば本選通過できるのではないかという感覚だったので,そちらに集中することにしました.結果として,代表にはなれなかったもののなんとか本選を通過することができました.数学オリンピックの日本代表や本選通過者がかなり高い割合で情報オリンピックでも高い成績を出しているのを知ったのはその後になってからでした(最近の動向は追いかけていませんが,今もその傾向はおそらく変わっていないでしょう).

次に競技プログラミングに触れることになったのは学部2年のときで,蟻本とAOJを使った授業を履修していました.やはりそのときも入出力がうまくいかなかったり,謎のエラー(謎ではない)に悩まされたりして肝心の内容にはほとんどついていけず, X Cubic(AOJやっている方なら知ってますよね)を通せる程度でした.話を聞いていて各アルゴリズムの概要は理解できたけれど,ほとんどの問題は力不足で実装のちACには至りませんでした.ただX Cubicのような簡単な問題であっても,Acceptされるとなんとも言えない嬉しさがあったのもまた事実です.

X Cubic: x の3乗 | プログラミング入門 | Aizu Online Judge

それから4年の年月が経ち,CODE FESTIVALというお祭りが開かれる情報を入手し,なんとなく思い出作りに挑戦してみようということで,ABCに参加したりして,他のことを投げ出して予選突破に向けて問題を解いたりしていました.修士課程2年目なので,始めるタイミングとしては最悪だという自覚はありました.来年は学生ではなくなるので集中して取り組む時間も少なくなると思いますし,一通りのアルゴリズムを学ぶには年度末までの時間だけでは十分とは言えません.ただ何か上手く行ったという自信が欲しかったんだと思います.後は断続的に大学での演習や研究などでプログラミングを道具として使ってきて,その行為自体に慣れてきていたのもあるかもしれません.その後ですが,練習の甲斐もあってかCODE FESTIVALは予選Bで通過し,決勝に進むことができました.それと同時に遥か上の世界を生で見ることができました.大会の運営の方には本当に感謝しています.この「遥か上の世界を見上げる」というのがなかなかやりたいと思ってもできないことで,こういう機会を学生の最後の年に体験できたのは本当に運が良かったと思います.レーティングの数字でも「遥か上」感は伝わるのですが,やはり目の前で見せつけられないと人間って納得しないんだなと思いました.

recruit-jinji.jp

しかし,競技プログラミング周りの環境が4年前に比べても変化していたのは事実で,そのおかげもあってか以前と違いハマっていきました.


yukicoder

数年前に諦めた時と比べて競技プログラミング周りの環境は激変していました.その一つがyukicoderです.

yukicoder

自分がアルゴリズムを学ぶ場所として選ぶとしたら今あるオンラインジャッジサービスの中だとyukicoderが一番だと思っています.学習の用途としてのyukicoderの自分にとっての良さを挙げると以下のような理由です.他のサービスとかぶっている点もありますが,これが全て揃っているサービスはなかなかないと思います.

  • テストケースの中身を見ることができる
  • 解説のリンクが問題ごとについている.しかも複数ある場合も多く,色々な人の解説を見ることで独りよがりの解釈を回避できる可能性が高い.
  • 問題にタグリンクが付いていて,似た手法を使った問題を簡単に参照できる
  • スマートサブミットやサンプルコピーボタンなど,検証や提出にかける労力をできる限り少なくするような工夫がある

このタグというのが始めたばかりの段階で特に重宝することになります.今の自分もそうですが,初心者の実力では客観的に質の良い問題,悪い問題の区別がつけられません.難易度も結局自分主体なので,低い難易度でもいつまでたっても解けないことなどもよくあります.その際に,タグで飛んで類題を通すことで「そのタグのついた問題を1問解いた」という自信が得られるので,モチベーションにつながります.調子が良い場合はわからなかった類題が解決することもあります.自分の場合は,まだアルゴリズム自体に慣れていない場合はAOJのIntroductionの該当部分を事前に確認しておきます.

それにしてもyukicoderはオンラインジャッジサービスとして出来すぎていて気持ち悪いくらいです.機能やシステムも流動的に変化したり追加されたりしていて,今後の期待度は高いです.今後も面白い問題を見つけていきたいですし,あわよくば自分も作問できればと思っています.

AtCoder

もう一つはAtCoderの存在です.

AtCoder (アットコーダー)

初心者がプログラミングに興味を持ってもらうファーストステップとして競技プログラミングを推進する理念(?)があるからか,初心者も足を踏み入れやすいコンテストが定期的に開かれています.また,自分が知る限り日本語で行われる唯一の競技プログラミングサイトです.自分が始めたきっかけもABCで良い成績が取れたからで,ABCの存在は間違いなく自分のモチベーションに貢献しました.

主観ですが,ライブラリに頼らず思考力と実装力を試すような問題が多い印象をうけます(この形式は好きです).また問題ごとの難易度もうまくばらついていて,かなり広いレベル帯に対してケアされている気がします.AtCoderにはまだレーティングで競うという文化がないので,勝ちに行くスタイルではなく,何か新しい知見を得る,という目的で参加しています.

ABC, ARCに関しては解説放送がコンテスト終了後にあります.でもスライドを読んでいるだけの部分もあって(特にスライドがわかりにくい場合)わかりにくいことも・・.難しさには少なくとも解法の難しさと実装の難しさがあるので,両方をカバーしながらうまく解説というのはなかなか難しいのかもしれません.

Twitter

Twitterでのコミュニティーの活性化も競技プログラミング周りの環境の変化として挙げないわけにはいきません.

Twitterを見ているとコンテスト前後ではツイート数が増加し,コンテストに対するモチベーションを上げることができます.また,コンテスト後では問題の感想などがツイートされ,色々な解法を流し読みでき簡単なレビューができます.最近だとアルゴリズムや問題のわからないことを呟いたらリプライが飛んできたこともあって,こういうことが自然にされるのは驚きでしたし,自分もできる限り手を差し伸べられる範囲でやっていこうと思いました.この節だけ分量が少ないのは単純に競技プログラミングの知り合いがほとんどいないからです・・色々とオンサイトのイベントなどに行って面識を広げることも必要だと感じています.競技プログラミング系のイベントはこれからも参加できる範囲で参加したいと思っているのでもし会ったらできる限り挨拶したいと思います(CODE FESTIVALの時は周りが全員赤い人に見えて全然声をかけられませんでした).


自分の競技プログラミングに対する取り組み方

TopCoder SRMCodeforcesはそれぞれ月に3~4回開かれていて,それに全て出るだけでも月6回程度コンテストに参加することになります.AtCoderも含めると月7,8回になることだってあります.コンテストに出れば出るほど色々な問題に触れることになりますし,レートもたくさんのコンテストを経験した分上がるかもしれません.一方で,世の中には超強い競技プログラマー(赤い人たち)がいて,上のようなコンテストだけでなくHackerRankやCodeChefなどのコンテストにも参加されていたりします.ですが自分はまだ緑コーダー.身の程をわきまえなくてはいけません.難しくない問題であっても実装に結構な時間をとられてしまうことだってあります.それだけたくさんのコンテストに出て,解けなかった問題のレビューも怠らず,しっかりと物にするほどのキャパシティは今は持ち合わせていません.特に,まだ未習のアルゴリズムが想定解になっているような問題をいくら考えても時間の無駄です.普段は自分はあらかじめ解くと決めていた問題とか設定が面白いと感じた問題を好きなように解いているのですが,できるだけ早く成長するために少し意識していることを書きます(正確とは限らないので,何かコメントやアドバイスがあると嬉しいです)

1. 取り組むジャンルを数問単位で固定する

とにかく一通りのアルゴリズムを早く習得したいと思っているので,3~4問単位で同一の(または類似した)手法が解法として想定されている問題を解きます.例えば「2分探索」「DP(動的計画法)」というようにテーマを縛り,yukicoderのタグをたどったり,AOJから問題を選びます.また自分は必ず日本語で読める問題を選びます.英語を読むための余計なエネルギーを消費したくないからです.蟻本を読むだけだとやった気になるだけだし,長い間1ジャンルに粘着するとモチベーションが落ちるので,モチベーションの維持という観点ではある程度の成果が出ているのではないかと思います.タグ別にこの順番で解くと理解が深まるというガイドってなかなかないからお膳立てがけっこう大変.みなさんはどうしているのでしょう.

2. コンテスト中以外で進展のない長考をしない

自分は手がかりがつかめない状態で10~15分経ったら解説を見てしまいます.そして大体の場合,解説を読んだからといってすぐに実装してACできるということは起こりません(発想で一発という場合を除く).長考する意味がある部分は,どういうアルゴリズムやデータ構造に落としこむかを思いつくところだと思っています(違ったらすいません).アルゴリズム自体に不慣れな最初のうちはアルゴリズムやデータ構造の適用に慣れることが最優先だと信じています.多分解説を読んでからどう実装しようか考える部分の方が学習効果は高いのではないかと思っています.これがどう影響するかは今後数か月の自分のレート変動にも関わってくるでしょう(怖い).自分の実力が上がってきたと感じたら長考スタイルにシフトしていくと思います.

3. 作問者によるEditorialがないコンテストには不用意に参加しない

始めたばかりのうちは解ける問題より解けない問題の方が多いので,復習は何が何でも必要です.特に時間いっぱい考えてもどうしてもわからなかった(通らなかった)問題はすぐにでも解説が見たい.あとはTesterがいるコンテストの方が参加していて安心感がありますね.解けていない問題のうち一番手前の問題を復習すると良いと言われているので,大体はそれに従って復習しています.

4. 同じ日に複数のコンテストに参加しない

単純に疲れるし,復習の量もかさむので2つ以上のコンテストが同じ日にあるときはどちらかを捨てます.SRMCodeforcesの日程がかぶるのは本当に勘弁.

5. AtCoder Beginner Contest(ABC)には極力参加する

これはワンパスで解ける問題を速く通す練習にはもってこいのコンテストだと思います.ただD問題はA,B,Cに比べて結構難しい傾向があるので,A,B,Cを早めに解いて残り時間でDをゆっくり考えるという時間配分になりやすいです.自分はA,B,Cは速さを意識して,Dは時間内に通せれば最高,という感じで参加しています.ACが速くつくので気分的にも乗りやすいコンテストです.

6. 自分を雑魚だと思わない

自分のことを不用意に雑魚と公言するのは一種のハラスメントだと思っています.と同時にそう思ってしまうと,「自分は雑魚だからこんな難しい問題解けなくて当然」という暗示をかけて実力向上に歯止めをかけてしまう恐れがあります.自分の場合はコンテスト中になかなか解き方がわからない問題に出会ったときは,「人間が出題している正解のある問題なんだから解けないわけがない」と暗示をかけて(自分を騙して)います.

最近は専らハラスメントが横行しているとのうわさです.例えば自分が弱い(具体的に何がとは言い難いですが,例えばレーティングの数値とか?)ことを主張することで自身を擁護し,言いたい放題ものをいうのは見ていてつらいです.TopCoderなどで他人のコードを撃墜するのと,コミュニティーでの他人そのものを潰すのは違うと思います.プログラマー界隈はただでさえギスギスしている印象があるので(主観です),少しでも優しい世界になってほしいものです.(自分はプログラミングが苦手ですが,そのような理由でプログラマーも苦手ですね・・)


おわりに

ここまで読んでくださった方,本当にありがとうございます.今思うともっと早く競技プログラミングを始めていたら,周りの環境も変わるだろうし,自分の考えも違う方向に行っていただろうと少し後悔しています.また中学生や高校生で高レートの人は本当にすごいなあと思ってしまいます.自分は今以上に強くなりたいと思っていますし,またプログラミングコンテストに定期的に参加することで自分の頭も多少は腐りにくくなるかと思っているので,できる限り続けていきたいと思います.あとはチームで何かコンテストに出るのがいつか達成したいことです.まずはチームを組みたいと思われるような実力にならないといけませんね.(同じ思いの方がいたら是非...!)

次(23日目)の担当者はnico_shindanninさんと_ehaさんです.

yukicoder 100問AC

先ほどyukicoderの解いた問題数が100問になりました.通過点記念に記録しておきます.始めてからおおよそ3ヶ月ですね.もう3ヶ月経ってしまったのか・・

解いた難易度の内訳:

難易度 AC数
8
★★ 22
★★★ 52
★★★★ 18
★★★★★ 0
★★★★★★ 0

始めた頃はDPや全探索などの基本的な手法を中心に練習していました.そもそも始めた当時はDFSやナップサックすら書けませんでしたからね.

100問目は★3の経路復元DPでした.経路を0,1のstringで管理してしまったのだけれど,もっと上手い方法がある気がする.

問題:No.258 回転寿司(2) - yukicoder

yukicoder No.258

始めた頃に比べて★4に対する恐怖感はだいぶ減った気がします.今後は★5にも挑戦していきたいと思いますが,現状はまだ未習のアルゴリズムもあるので,そちらに手をつけるのが先になりそうです.

今後はグラフ系のアルゴリズムを重点的に学習しようと思っています.

具体的には最小全域木やEuler Tour,強連結成分分解などが未習です.理解してしまえば経験を積むごとに消費するエネルギーも指数的に下がると信じて今はゆっくりやろうと思います.あとは記述量が少ないアルゴリズム(BIT, Union findなど)のライブラリなしでの再現の練習などもやっていきたい.早くAtCoderタグ機能ついてくれないかなー・・・

pythonとの二刀流も検討したいですね(多倍長などに対応できると楽な時もあるので).

次は200問かな.


宣伝:Competitive Programming Advent Calendar の22日目に記事を書くことになりました.よろしくお願いいたします.実は既にあらかた書き終わっていますが,どうなることやら.

Competitive Programming Advent Calendar 2015 - Adventar

yukicoder No.119 旅行のツアーの問題

最小カットを最大フローに言い換えて解くタイプの問題に挑戦してみました.おそらくフローを使った簡単な応用問題だとは思うのですが,初めて触れたので発想が斬新だと感じました.(この記事はフローを学んで2日目の記事です,間違いがあれば遠慮なく指摘してください.まだフローを知らない方は記事の後半から見た方がいいかもしれません.)

問題:No.119 旅行のツアーの問題 - yukicoder

解法:まずはこの手の問題が最小カットを使えば解ける問題と見抜く実力が必要.とはいいつつ,yukicoderにはタグという超助かる機能が存在するので,今回はそれを前提として解きました.問題には「最大の満足度」とあるので最小カットに適用できるように「最小の満足損失」に言い換えます.

ここではサンプル1を例に説明します.問題文から,ある国には「ツアーに参加しかつ訪れる」「ツアーに参加しないが訪れる」「ツアーに参加しようがしまいが訪れない」の3種類の扱いをすることができます.それぞれについて,ツアーに参加し訪れる場合は B_i,ツアーに参加せず訪れる場合は C_i,訪れない場合は 0の満足度を得ることができます.損失に言い換える際は,損失0が3種類の選択の中で最も満足度が高い数字(つまり \max (B_i,C_i))とします.つまり各選択肢は損失に言い換えると順に \max (B_i,C_i)-B_i \max (B_i,C_i)-C_i \max (B_i,C_i)となります.下の表はサンプル1の場合の各国,各選択肢の損失です.

ツアー参加 ツアー参加せず 訪れない
0 0 10 20
1 20 0 50

唐突ですが,次のような有向グラフを考えます.

f:id:ctylim:20151201151945p:plain:w300

例えば国0のツアーに参加し,国1には訪れないという場合,次のようなカットで表現します.

f:id:ctylim:20151201151954p:plain:w300

このようにしていろいろカットを試して最小になったものが満足度最大の国の行き方であるといえます. ただ,この問題には複数の組み合わせにおいて,「国Cをツアーで訪れた場合,国Dはツアーしないで訪れるということができない」という制約が存在します.例えばサンプル1では「国0をツアーで訪れた場合,国1はツアーしないで訪れるということができない」と解釈します(ここの辺りが問題文を1回縦読みするとよく分からなくなってしまうところであり,少し作為的な気もします).これをグラフとカットを用いて表現します.つまり,サンプル1において

「国0をツアーする」かつ「国1をツアーしない」を実現するカットは存在しない

と表現することができます.つまり下の図のようなカットはありえません.

f:id:ctylim:20151201151958p:plain:w300

ただ,その他の組み合わせにおけるカット( 3 \times 3-1=8通り)は実現可能でなければいけません.そこで下の図のようにコスト \inftyの有向辺を張ります.

f:id:ctylim:20151201152002p:plain:w300

すると,上手い具合に1通りの成立してはいけないカットの合計コストが \inftyになり,最小カットとはなりえないことが確認できると思います.他の8通りのカットは今まで通りの合計コストとなります(この部分の辺を張ったり辺を入れ替えたりして上手いグラフを作るのは試行錯誤がある程度必要な部分ですが,分かると楽しいです).

Max-flow Min-cut Theoremより,最小カットは最大フローと同じなので,SからTに流せる最大のフローをDinicなどのアルゴリズムで求め,求まった最小損失を最大満足度に言い換え直せばOKです.

yukicoder No.119


ここからは自分がこの問題に取り組む前にやった事前準備について書いておきます.

まずフローを知らなかったので(学部の授業で触れたことはあるけれど,忘却の彼方に行ってしまった),色々なページを参考にしました.フローの定義や最大フローを求める過程,各アルゴリズムに関しては下のページが詳しかったです.

http://hos.ac/slides/20150319_flow.pdf

アルゴリズム(Dinic)の実装は有名な蟻本を参考にしました.(当たり前ですが証明を読んだり,アルゴリズムの吟味をしたりしたこともあって,ここまでの理解が結構時間かかりました)

次にAOJの最大フローをストレートに聞いてくる問題とyukicoderのフローの基本問題を解きました.

最大流 | グラフ | Aizu Online Judge

No.177 制作進行の宮森あおいです! - yukicoder

その後に下のスライドを見つけてどうやらフローを使った面白い解き方があるということで,No.119に取り組んだという順です.

www.slideshare.net

フローをこれから学ぼうとしている方は参考になるかもしれないと思って,あとがきとしました.

yukicoder No.19 ステージの選択

強連結成分は定義しか知りませんが,考えればその界隈のアルゴリズムを知らなくても解ける良い問題でした.

問題: http://yukicoder.me/problems/62

解法: あるステージAがクリアできたらステージBのコスト(難易度)が半分になることをA→Bの有向辺で表現し,グラフにする.配列E(from, to)を作り,from→toに有向辺をたどるパスがあるかどうかを求める(ワーシャルフロイドなど).このとき,頂点(ステージ)Aと頂点Bが同じ強連結成分に含まれることはE[A][B]=E[B][A]=trueであることと等価である.なるべく合計コストを下げる戦略としては,有向辺が伸びていない強連結成分を全て洗い出し,各成分の中でコストが最小のものがinitialにクリアするべきステージである.なぜなら有向辺が伸びている頂点はその親のステージをクリアすればわざわざ最初にクリアして等倍のコストを支払う必要がないし,同じ強連結成分内であれば,どれか1つのステージをクリアすればその他のステージはコストが半分で済むからである.

アルゴリズムの実装方針としては各強連結成分のminimum costを導出する必要があるので,(多分)強連結成分ごとに処理するのが良いと思います.

yukicoder No.19

線形時間で強連結成分分解できるアルゴリズムがあるらしいので,近いうちに見ておこう. Reference: Kosaraju's algorithm - Wikipedia, the free encyclopedia