kaikey’s diary

お気持ちと知見の闇鍋ブログ

AtCoder 黄 になりました

（※お気持ち成分多め、あまり実益的な内容は少ないかもしれません。ご了承ください。）

ブログ、久々の更新です。

やはり僕には解説ブログを書くのが向いていなかったようで、参加記or色変記事を書き溜めるブログになりそうです。

 

本題に入ります。

2/6のABCにて、AtCoder黄色になりました。

 今まで黄色は遥か遠い存在だと思っていたので、なれてしまったのが夢のようです。

 

 

 

黄色になるまでにやったこと

実は青変の時と比べてこれと言ってやっていたことに変化はなく、CodeforcesのバチャがDiv3からDiv2, えでゅふぉになっただけでした。

おそらく水色のある時に精進の方法を変えたのがここまで伸びた大きな要因だと思っています。

 この辺りの話は青変記事にも書きましたが、去年の8月ほどから夜にCodeforcesのバチャを走る習慣をつけました。

Div3を埋めて、Div2を埋めて……といった具合に「AtCoderの～色埋め」の精進スタイルから「Codeforcesの～Round埋め」というスタイルに切り替えました。

おそらくこれは自分の性格的な問題もあったのですが、色埋めよりもバチャの方が問題を解く効率がよく、かつ集中して取り組めました。

バチャをする前とした後ですが、圧倒的に期間に対して問題を解くペースが上がっています。

また、AC数を記録していたことも「とにかく問題を解く」というモチベーション維持につながったと思います。

バチャをすることで、どんな問題に対して集中して取り組むことができ、かつ本番形式でやることで、これがとても大事のように感じました。

 

競技プログラミングに対する姿勢

かなり僕の個人的な価値観の話になります。

誰かが「競技プログラミングはe-Sportみたいなもの」と言っていたのですが、僕もその通りだと思います。

単純な本人の地頭や知識量だけでなく、当日のコンディション、出題された問題に対する相性、それだけでなくもしかしたら最後まで粘って問題に向き合った結果自分の実力以上の問題が解けるかもしれない。

ここらへんはゲームやスポーツに通じるものがあるため、まさにe-Sportsと言っても過言ではないと思っていて、それ相応の姿勢で考えていました。

先述の話に繋がりますが、この点においてバーチャルコンテストにはとても大きな価値があるように感じています。

本番形式で行うことでプログラミングコンテストという状況自体に「慣れる」、また集中力をつける、時間まで粘って問題を解く精神力を身に着ける、などなどたくさんあります。

また、ルーティンをコンテスト前とバチャ前にやることで、バチャで慣れているような心持で本番も落ち着いて問題を解くことができます。（僕は必ず決まった曲を１曲聴くようにしています。）

 

同じく、競い合うライバルの存在も大きかったです。

コンテストだけでなく、バーチャルコンテストでも他人の結果と自分の結果を色々と比較して、「負けていた点」を列挙していました。

そうすることで悔しいという感情が芽生えます。溜め込むと病みそうですが、ツイートをすることで吐き出して切り替えることで次こそは勝ってやる、という気持ちになります。（ここらへんはある程度のメンタルの強さが必要かもしれませんが。）

他人を意識することが自分を鼓舞するうえでとても大事なことだと身に染みて感じました。

 そういう意味で、Twitterを開設して自分の実力と同じかそれ以上の方々とたくさん知り合えて競い合えてとてもよかったです。いつもバチャを走ってくださってる方々に感謝をしています。

 

お気持ち

 ３か月ほど前まではまだ水色で、しかも1400台で停滞していました。

 （このあともう２か月ほど停滞します）

 可愛いですね。この時は絶対自分が黄色になるなんて夢にも思っていなかったでしょう。

水色でたくさん停滞したからこそ、青色・黄色の人間はとてもすごいと思っていました。自分より年下で黄色の方々を見ると別次元の人間に見えました。

実は自分は数学に対してコンプレックスを抱えていて、どうせ俺には無理だ……と青色になることすらちょっと諦めていた時期もありました。（いわゆる出来が違うから無理なんだろうな……という感じでした）

しかしある時を境に今まで貯めていたものが噴き出したかのようにレートがもりもり上がり、気づいたら青色後半、あれよあれよと黄色になりました。

当時のことを考えると、たった３か月前のことなのにとても感傷に浸ってしまいます。

 

これからの目標

年内に橙色を目指していこうと思います。ただし今の精進のままじゃダメだと思っていて、

・数学に対する圧倒的な苦手意識

・ライブラリの少なさ

・高難易度に対する粘りの弱さ

があると思うので、この辺りを意識して改善していこうと思います。

最後まで読んでいただきありがとうございます。これからよろしくお願いします。

AtCoder 青 になりました

20/11/22, ARC108で初の黄色パフォをたたき出しようやく青色になれました。

初の色変記事ですがつらつら書いていきます。

 

ここに至るまでの道のり

レーティング遷移グラフをまず貼っておきます。

 こう見ると緑の時代がかなり長いんですが、緑の頃はほぼ精進をしていなかったためあまり長く感じていませんでした。(就活やら他の勉強やらをしていました。)

今年の4月あたりで某感染症によって時間ができたため、精進に力を入れ始めたという感じでした。

ですが、精進してもなかなかレートが伴わないことが多く体感では水色停滞の時期が一番つらかったです。

 

青になるまでにやったこと

各やったこととそれがどの程度実力に結びついたかを時系列順に書いていきます。

 

・緑diff埋め、水diff埋め

まず初めにやりました。とりあえずAtCoderProblemsの円グラフを埋めようと思いました。

これによっては安定性がついてパフォの下限が少し上がったかなと思いますが、上限はあまり変化しませんでした。

 

・PAST、蟻本埋め

PASTの過去問と蟻本のけんちょんさんのこちらの記事を埋めていきました。

こちらもあまりレーティングに反映はされませんでしたが、アルゴリズムに対する知識がつきました。

 

・JOI埋め

JOIの難易度6-7が適正という話を聞いたので埋めていきました。

実装が重く、なおかつ典型力が問われるので良問が多いと感じました。

ただし、こちらはアルゴリズムの勉強問というより応用力を試すためのものでした。

本番で高難易度を解くための練習にはなったと思っています。

 

・こどふぉバチャ埋め

これはめちゃくちゃオススメです。

まず、AtCoderの埋め状況とこどふぉの埋め状況が独立であることで、AtCoderはdiff別に埋めてこどふぉはコンテストごとに埋めるということができます。

バチャとして走ることでコンテスト自体の練習になり、なおかつ問題を解くときの集中力が上がり、さらにフォロワーとやることでモチベーションの向上にもなります。

さらに、div3の難易度が適正水~青ぐらいなので、そこそこ埋めてる感を出しながら全完で気持ちよくなれます。続けるという意味でもかなり大きかったです。

そして具体的な結果ですが、一番大きかったのは問題を解く速度がかなり上がったことでした。

こどふぉは典型が多いため、かなり教育的な問題が多く、広い範囲に応用できるものが多くて結果的に全体的なスピードの向上に繋がりました。

そしてもう一つ。難易度の少し高いdp, グラフ, 構築の練習になりました。AtCoderと傾向が違いここらへんがかなり出るイメージがあります。

こどふぉバチャdiv3を2か月ほどに渡って埋めていきましたが、実力はあからさまな変化がありました。

 

メンタルについて

かなり競プロをやるうえで話題に上がるものなのですが、レートの増減はメンタルがかなり結びついているといっても過言ではないかもしれません。

こどふぉバチャの成績はかなりいいのですが、実際のこどふぉの成績はあまり芳しくなく、おそらく本番に弱いのだろうと思われます。

また、メンタルは循環する、つまりいい成績を取ったあとはいい成績を取りやすいが悪い成績を取った後は冷えやすい、ということはあると思います。

そう考えると、停滞していたのもそういうところに問題があり、冷えなければいいという思考回路で自分を守っていたのかもしれません。

気負い過ぎるのもよくないですが、逆に俺はやれる！！という意識も大事なんじゃないかなと思っています。

 

これから

春までに黄色になりたいです。

卒論さえ終われば無限に精進ができるのでそのタイミングでJOI埋めや青diff, 黄diffやAOJをどんどん埋めていこうと思います。

これからもよろしくお願いします。

第4回PASTお疲れさまでした

記憶が新しいうちに投稿です。

リアルタイム受験ではありませんでしたが、お金を払って土曜の朝から受けました。

午後はHTTFがあったので、気合の7時起きをして臨みました。

 

 

ようやく上級になれました！

半年前に短期間で2回受けてどっちも76点だったのですが、今回は12点上がって上級になれてよかったです。

さてさて、各問題に対する感想解説をやっていきます。

 

A - 中央値

ソートして2番目を出力で終了～～～でサンプルを試さずに提出したらWAが出ててビックリ。問題を読むと何が中央値だったかを出力するらしい。一問目からずっこけるのは少し不吉。

 

B - 電卓

Bが0ならエラー、そうでないなら100倍してから少数の方を0埋めして出力。

 

C - 隣接カウント

愚直に4方向見るだけでOK. こういう実装問題があると競プロ初心者にとってかなり教育的なセットになりそうだなぁと思った。

 

D - 分身

左分身の必要条件が左端の'.'の数、また右分身の必要条件が右端の'.'の数、両方の和の必要条件が'.'の最大連続数以上であることになる。

 

E - アナグラム

場合分けっぽいなーと思って|S|<=2, もしくは全て同じ文字列ならfalse みたいなのを書いたらなかなか通らなくて焦る。

よく見ると制約がN<=5なので愚直に5!でいいことに気づく。コンテストじゃなくてよかった。

 

F - 構文解析

ここらへんで若干実装に工夫が必要になってくる。

とりあえず各文字列に対して出現回数をカウント、そして出現回数でソートする。

そして前からK番目に該当するやつを見て、それの前後に同じ出現回数のやつがあるかを確認、あったらダメ。

 

G - 村整備

これも愚直っぽい。

2重for文で壁を崩す→bfs→壁がないところを全部訪問してるかどうか→壁を戻すという感じでやった。

 

H - マス目のカット

これも愚直。

nが小さいので条件を満たすnを線形探索して、長さnの正方形を切り出したときにある数がn * n - K 以上あるならOK.

そう考えるとにぶたんするような制約でもいけそう。

 

I - ピザ

ここらへんで少し難しくなってくる。

尺取りしようと思ったが、バグったらめんどくさいしlower_boundでやることにした。

合計値 - 累積和を計算して半分くらいに分割する場所をlower_bond, その近辺のindexが答えになりうるのでそれを探していった。

 

J - ワープ

難しい。方針がすぐには立たなかった。

ワープ可能であるなら辺を貼る、ということを考えたがどうしても辺が多くなりすぎる。

そこで、ワープの性質について考えてみると、2回同じワープをするのは無駄ということに気が付いた。

もっと言うと、A→B→CをA→C, A→C→AをA→Aとみなすことで高々1回のワープをするのが最適ということもわかった。

このことから、まず各ワープの疲労度をワーシャルフロイドで最適化しておいて、

始点と終点からそれぞれ最も近いA, B, Cまでの距離を計算してそれぞれに対して最も小さいものを取ればいいことがわかった。かなり面白い問題。

なぜか僕のダイクストラが遅く、地獄のような高速化を求められてしまったが、、、

f:id:kaikey:20201110112608p:plain

地獄の高速化

ダイクストラをちゃんとライブラリ化しようと思った。

 

K - 転倒数

転倒数に関する典型問題を解いていたらかなり見通しが立ちやすかった。

数列内の数字は20以下なので各数列内の各数字の出現数を記録、あと各数列の転倒数も記録。

そしてBITを使って出現数から転倒数と、その数列自体の転倒数を計算する。

サンプル2が一発で合ったからそのまま提出。時間的には10分くらいで解けた気がする。

 

L - マンションの改築

これは少し難しかった。

いまいち方針が立たなかったので、とりあえず色々シミュレーションしてみると、

とりあえず各マンション間の差分を管理するとよさそうなことに気づいた。

さらに偶数番目の加算は差分の偶数番目を+, 奇数番目を-, 奇数番目の加算はその逆……みたいなこともわかり、これをmapで管理するとよさそうなことに気づいた。

というわけで各差分の出現回数を記録したmapと、偶奇の操作の和を記録してそれでうまいことやるとできた。

大体17分くらいで解けた。上の考察がかなり流れるようにできた上に全くバグらなかったのでうれしかった。

 

M - 筆塗り

わからず。

後ろから操作するとよさそうだとは思ったが、それ以上がわからなかった。しっかり復習案件。

 

N - マス目の穴埋め

難しい。1つ上と2つ上の情報が現在に作用されるのでその2つの情報をbitで持ちながらdp。

これ。実はICPC-Eで似た問題が出ていて、解法に感動していたためすぐにわかってしまった。(実装は初めてやったからそれなりに時間かかったけど。)

 

O - 宝箱

難しい。なんだこれ。

累積和を引いたセグ木でdpしようとしたけど答えが一生合わず。無念。

 

というわけで、結果はこんな感じでした。

f:id:kaikey:20201110105152p:plain

解けた問題数が増えたのは当然嬉しかったけど、それよりもめちゃくちゃ早解きができるようになったと感じています。

次はエキスパートを狙います。

ICPC2020参加記

ICPCお疲れさまでした。かなり遅れての投稿で内容もあまりありませんがゆっくり見ていただけると幸いです。

先にささっと結果だけ話してしまうと、僕らのチームは、黄水茶構成で3完でした。2時間半近く椅子を温めていて少し辛かったです。

学内に僕らより成績のいいチームがいたので予選落ちでした。

f:id:kaikey:20201110001214p:plain

戦績

 

参加に至るまでの流れから本番までをだらだら書いていこうと思います。

 

唐突な参加登録

正直、今回のICPCは参加する気がありませんでした。登録とかめんどくさそうとか、同大で出れそうな人がいないとか卒論だりーとかそういうことを考えていたためもういいかなーと思っていました。

そんな矢先。

f:id:kaikey:20201110002007p:plain

パイセンとのDM

クロー大先生からお誘いをいただきました。(かなり嬉しかったです。)

もう一人が決まってなくて茶色(ねおさん)の方でもいいかーと聞かれましたが、僕としては参加できるだけで万々歳だったので僕がお茶くみ係になろうが靴磨き係になろうが寿司職人になろうがなんでもよかったです。

 

ただし、少し残念なことが僕としては元々ICPCに参加しない気で予定を組んでいたため、10月の土日の予定が埋まっていました。

チーム戦の雰囲気を掴むためにPGBATTLEとか国内模擬やるーっていう話をされたんですがまともに参加できませんでした、、、(そもそもPGBATTLEはチーム戦なのか諸説ありますが)

ただまあ、パイセンが国内模擬の日の体調崩したりしたのもあって後日みんなで問題解こうということになりました。

 

初めてのチーム戦

ICPCは少し特殊なのでチーム戦と言っていいのかわかりませんが……

とりあえずチームの構成が黄水茶でかなり凸凹構成だったのでどうしようかという感じになりました。(もはやチーム戦として成り立つのかこれ)

ねおさんには、ICPCというものの空気感を掴むために参加するそうなので、少し雑務よりなことをしていただきました。(提出の管理、出力の差分を取ったり……)

僕とパイセンは、僕が最近精進しまくってるのもあって僕は実質黄色コーダーということで二人で問題をいい感じに分け合って解くことにしました。

とりあえず模擬の問題を解き始めました。

ここらはチーム戦っぽく、Aは僕が解いてBはパイセンが解く。いい感じでした。

C問題から少し雲行きが怪しくなります。ぱっと見解法が思い浮かばない。なんだこれは。

ラバーダックデバッグの如くねおさんに俺の考えを聞いてもらいます。かなり考えがまとまって非常に助かった。

ただし決め手となる考察ができず、惜しいところをぐるぐる回ります。ここでパイセンがD解けねえと言いながら戻ってきました。

パイセンに改めてCの概要と考察を説明すると、パイセンもパッと思い浮かばないようでみんなでうーんとなりました。

ここで俺があるグリッドに侵入したところでカウントすればいいことに気づく。みんなで確かにとなる。

ただし実装がかなり地獄でした。とりあえず僕がある頂点からある頂点に侵入したときにカウントするみたいなコードを書いてパイセンがsxsygxgyの正規化をしましたが、無限バグ地獄に陥りかなり辛い気持ちになりました。

結局この日はCが通せず一旦解散となりました。

 

チーム戦リベンジ

次に集まったのはICPC前日のお昼でした。何しようかでとりあえず前回のupsolveをするかということになりました。

ちなみにC問題は正規化がバグっていたみたいでパイセンが通してくれて助かりました。

「バグ仕込み過ぎてこれじゃ俺バグ仕込ませのプロ・バグ駒瀬だよ……」って言ってたのが個人的にめちゃくちゃ面白かったです。

次にD問題、これもなかなか苦戦しました。各々で少し考えた挙句、詰まってしまったので少し話し合いをしようということで僕が最大最小をキープしたまま計算するのはどうか、という提案をしたらパイセンがめっちゃ綺麗にまとめてくれました。さすが黄色コーダー。

ということでこれを実装したのですがなかなか沼にハマってしまった。サンプルがあってるだけになかなか辛い。

こうなるとそもそも解法の正当性が大丈夫なのかという感じになるのですがあってそうなのでこのまま突っ切ることになりました。

最終的にごちゃごちゃやってたらなんかあってしまいACしました。(正直あんまり覚えてません……)

そしてE問題。C, Dがめちゃんこ難しかったからEも難しいんだろうなーと思ったのですが、見た瞬間にこれただの2-SATじゃん……となりました。

いやまさかそんなやるだけなわけないだろ、とパイセンと話し合ってたのですがどう見てもやるだけだったのでやるだけやってACしました。CDEでEが一番簡単でした。

 

そしてICPC本番へ……

当日。普段のコンテストの100倍緊張していて、前日の夜からかなり落ち着きがありませんでした。

というか僕は構文解析と幾何とサイコロを解いてなかったのでここらへんがめちゃくちゃ不安でした。

とりあえず昼に集まりリハーサルは参加して、軽く確認をしたら16時15分に集合、ということで各々散歩なりしてくることになりました。

僕はというと、手持ちにサイコロがなかったので買いに行くことにしました。

しかしロフトへ行っても置いてなく、近所の怪しげなおもちゃ屋に行っても置いてなく、ダイソーにも置いてなかったのでさすがに敵対チームの影を感じてしまいました。

しょうがなかったので紙でサイコロを作りました。

f:id:kaikey:20201110005556j:plain

手作りサイコロ

なかなか会心の出来でした。あわよくば解法ガチャもこのサイコロでやってやろうと思いました。

そして本番。めちゃくちゃ緊張しながら更新ボタンを押します。

……おそらく色んなところで言及されているので詳しくは省きますが、ICPC側のサーバーエラーで問題が表示されませんでした。

うちのチームのデータが登録されてないよ！みたいなことが書いてあったのでかなりひやひやしたのですが、10分ぐらいで表示され10分延長という文字もあったのでまあ大丈夫か、となりました。

模擬と同じく僕がA, パイセンがBを担当してささっと解く。そしてC, Dもそれぞれやる。

Cはかなりこどふぉっぽい問題だったのでささっと解けました。(実行終了前に提出してしまうトラブルがありましたが)

問題のD。全く解法が見えてきませんでした。

構文解析すらよくわからないのに、わかっていたとしても全く解法が見えません。

ここらで三人でとてもつらい気持ちになります。とりあえずEを見ます。

Eはまだわかりそうな問題でした。とりあえずパイセンが普通のDPを書いてみます。

答えが合わない……

普通のdpじゃダメなんだな、ってことはなんとなくわかったのですがどう重複を削除すればいいのかわからず……

そしてFを見ます。ここで僕は戦犯をしてしまいました。

初手でUnionFindが思いついたのですが、いつものコンテストのノリでO(N^2)の10^10だから無理だな～、いい感じにならし計算量で抑えられそうだな……という思考になっていました。

パイセンはパイセンでずっとEを考察していたので、お互いそれぞれの問題を考えこんで長く苦しい時間が流れました。

さすがにCを通してから2時間半あったのでDを考えなおしたりしたのですが、結局わからず……。

終了10分前に、Fの話をパイセンにしたら「ICPCなら10^10は許容範囲」と言われ、確かにそうなのかと思いました。

ですが10分で実装できるわけもなく、時間が来てしまいました。

最終的には3完学内2位で終わってしまいました。とても悔しかったです。

僕はB4で来年はもう就職するので最後のICPCでしたが、まあなんだかんだでチーム戦もこうやって悔しい思いをしたのも楽しかったです。

最後にここまで見ていただいてありがとうございました。これからもより精進していくのでよろしくお願いします。

(チーム戦お誘いいただければ喜んで参戦します！)

Codeforces Round #600 (Div. 2) (Virtual) 解説感想

20/10/22 21:001から2時間。URL:https://codeforces.com/contest/1253

所感:

A-Eで5完, Bでペナを出しまくったこと以外は好成績だった。

A. Single Push

数列A, Bが与えられ、連続区間に同じ数を1回だけ加算してAをBにできるか。

とりあえずB - Aして正の数の連続区間が1つ以下しか存在しなければOK.

https://codeforces.com/contest/1253/submission/96358643

 

B. Silly Mistake

最近割と見る気がする、setのデータ構造をそのまま使えばいい問題。

ただし一人につき一日一回しか出入りできないので、その日に入った人を保存するsetも用意しておくとよし。

https://codeforces.com/contest/1253/submission/96359613

 

C. Sweets Eating

こちらも典型。まず、小さい飴から使うのがいいのがわかる。さらに、後の日付に食べるのは小さいもののほうがいいということもわかる。これを数列にすると

M = 3とすると、

k = 3 なら A1 + A2 + A3, k = 4なら A1 * 2 + A2 + A3 + A4,

k = 6なら(A1 + A2 + A3) * 2 + A4 + A5 + A6

つまり、最大として取ってる要素の後ろM番目が*2, さらにM番目が*3...となっていく。

これはM間隔の累積和として計算できるのでそのまま素直に書けばOK.

サンプル1が一発で合ったのでそのまま投げたらAC.

https://codeforces.com/contest/1253/submission/96360189

 

D. Harmonious Graph

面白い問題。問題を言い換えると、連結成分の最小値と最大値を区間としてみると交差してるところは繋げてください、という問題になる。

これを言い換えると、A < B < Cで A, Bが異なる集合に属する かつ A, Cが同じ集合に属するということになる。

実装を楽するために、各集合内での最大値を管理して、i と i + 1を比較するように見ていきi内の集合の最大値がi + 1より大きいならマージ、ということをすればよかった。

最大値の更新はiを含む集合内の最大値とi+1を含む集合内の最大値の大きい方を取ればOK.

https://codeforces.com/contest/1253/submission/96361446

 

E. Antenna Coverage

制約が緩いのでO(N * M)が間に合う。

あるアンテナの位置xを始点として、範囲をどんどん拡大していき、sを超えたらコストを増やしていくという方針で更新するDPがよさそう。

ここでサンプルを試すと、合ってるサンプルと答えが1異なるサンプルがあってビックリ。添え字ガチャしても合わない。

少し冷静に考えてみると、今回の問題は[1, M]を満たし、かつ区間は端が隣り合っているなら重なっていなくてもOK, という条件がある。

しかし、上記の方法だと, 伸ばしたアンテナの長さをLとすると[x - L, x + L]の範囲のカバーになってしまう。これだと重なるまで伸ばしてしまうので最小コストとは言えない。

したがって、構築を半開区間に置き換えてみる。

まず全てのindexを1ずらして[0, M)を満たすように伸ばすことを考える。半開区間であれば上記の方法のカバーは[x - L, x + L + 1)という具合になる。

半開区間なので範囲が被ることがないというのが保証されている。これが思いつけばOK. 添え字ガチャしてる時間がもったいなかった。

https://codeforces.com/contest/1253/submission/96364495

 

F. Cheap Robot

解説を見てもわからないので今回は飛ばします……

Codeforces Round #603 (Div. 2) (Virtual) 解説感想

2020/10/15 21:00~から2時間. URL:https://codeforces.com/contest/1263

所感:

A-Dで4完. Eは通せなかったがコーナーとバグにしっかり配慮してペナ0だったのがよかった.

 

A. Sweet Problem

まず「異なる２つを選ぶ」という制約を無視すると、総和/2を切り下げした値が答えになる。

それを加味した上でその制約を入れて考え直すと、一番大きい値が半分以上である場合順当なペアの割り当てができないことがわかる。

したがって、一番大きい値をペアが作れるくらいまで減らすのがよい。

実装を楽するならソートして(小さい２値の和)*2が一番楽そう。

https://codeforces.com/contest/1263/submission/95582292

 

B. PIN Codes

少し難しかった。

まず制約がN <= 10なこと、かつある桁のPINの通り数が１０あることから答えは最大でも９であることがわかる。

より簡単に考えると、変更する桁を固定するのがよさそう。そう考えると一番上の桁を固定して、それ以降の桁で各数字をグループ分けしてなるべく振り分けないような操作が考えられた。

よってグループ分けした際に、桁に対して使用済みflagを管理して一致している数を今ある数と被らないように振り分け直す、という方法で行った。

https://codeforces.com/contest/1263/submission/95583487

 

C. Everyone is a Winner!

こちらは典型。平方を考えると数の分布は√Nまで存在が保証され、逆にそれ以降は徐々に間隔が広まっていくという性質がある。(y = 1/xのようなグラフをイメージ。過去問で得た知見だったため詳しく解説ができない(すまねえ))

なので1~√Nまでsetに入れて、さらにそれを割った数もsetに入れる。最後に0を入れればOK.

https://codeforces.com/contest/1263/submission/95583922

 

D. Secret Passwords

ちょっと焦った。UnionFindで分類分けする問題。

各文字列について行うと, N = 2e5なのでN^2でTLEしてしまう。

しかし、ここで「ある文字が同じなら等価」ということを考える。

言い換えると、ある文字列の中に、例えばaとbが入っていた場合、他のaもしくはbを含む文字列はこの文字列と等価であることがわかる。

従って、文字列内で異なる文字がある場合それらをマージしていけばいいことがわかる。

文字列の長さは高々50なので余裕で通る。

https://codeforces.com/contest/1263/submission/95584401

 

E. Editor

難しい。今回は未upsolveなので飛ばします。

 

F. Economic Difficulties

そこそこ好きな問題。

配列の各位置について、上の木の根もしくは下の木の根とどちらかに連結にさせていき、最終的にすべてを連結にさせたとき最小のコストはいくらか、という問題に言い換えられる。(コストはノード数、大体すなわち根からの距離-1)

ここで考えることは、単純な深さを考えた場合はただのdpでいけるが、木であるためもしかしたらショートカットができるかもしれない(祖先が根でない場合、明らかに距離より小さい値がコストになる)ということだった。

その値は、上もしくは下の木について、最後に使ったノードの位置がどこか、という情報があればいいので祖先をLCAで求めることでdp[現在位置][上の木の最終ノード][下の木の最終ノード]でdpを更新していくことでN^3logNで求まる。

 

……間に合わないじゃん。

頑張ってNを落とす考察をする。

結局30分ぐらいかかったが、よくよく考えるとdpの各状態に対して、最終ノードの片方は必ず直前のノードになっているということがわかる。

したがって、持つべきdpの状態はdp[現在位置][対になる木の最終ノード][上か下か]だけを保持していけばよかった。これでN^2logNなのでAC.

https://codeforces.com/contest/1263/submission/95594849

AtCoder Beginner Contest 142: F - Pure

競技プログラミング AtCoder 問題考察

https://atcoder.jp/contests/abc142/tasks/abc142_f

 

問題文

N 頂点 M 辺の有向グラフ G が与えられます。
このグラフの頂点には 1 から N までの番号が付けられており、i 番目の辺は頂点 Ai から頂点 Bi に向けて張られています。
このグラフは自己辺や多重辺を持たないことが保証されています。

すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ (注記を参照) が存在するか判定し、 存在するならその一例を示してください。
ただし、空グラフは含めないものとします。

 

制約

  • 1≤N≤1000
  • 0≤M≤2000
  • 1≤Ai,Bi≤N
  • Ai≠Bi
  • 組 (Ai,Bi) はすべて異なる。
  • 入力はすべて整数である。

 

最近解いて、ちょっと面白かったのと公式の解説が個人的に若干わかりづらかったので、書き記そうと決意しました。(記念の1個目の解説記事！)

まず「すべての頂点の入次数が 1、出次数が 1 であるような G の誘導部分グラフ」の「すべての頂点の入次数が 1、出次数が 1 であるような」とは何かを考えてみます。

簡単に考えると、１つの閉路のみによって構成されるグラフが条件を満たすことがわかります。

f:id:kaikey:20200715161555p:plain

閉路グラフC_6の例

※これは閉路グラフという名前があり、n個の辺からなる閉路グラフをC_nといいます。

 

従って、誘導部分グラフの定義から、とある閉路に含まれる頂点を抽出したとき、元グラフのそれら頂点間に存在する辺を抽出したら閉路グラフになっていればいいです。

ただし、ここでどの閉路を抽出すればいいのか？という問題が生じます。

なので、もう少し考えてみることにして、例えば先ほどの閉路グラフに辺を追加することを考えました。

f:id:kaikey:20200715162505p:plain

閉路グラフに辺を追加

この点線のどれかに有向辺がつくことを考えてみます。

例えば、左の点線に２から５へ向かう有向辺をつけることを考えたとき、２の出次数、５の入次数が２になってしまい当然求めるグラフの条件を満たさなくなります。

しかし、ここでグラフ全体に着目すると、２→５→６→１→２へと向かう閉路が出来上がります。ここで、閉路グラフに辺を追加すると部分グラフから閉路ができるのではないか？と考えました。

例えば、５→２へと逆の方向に辺を追加することを考えると、今度は先ほどの閉路の部分グラフでは使わなかった辺を使って２→３→４→５→２と閉路が構成できることがわかります。

また、頂点数３の閉路グラフはこれ以上辺が追加できないので条件を満たすこともわかります。

したがって、閉路に対して辺を追加することでより小さい閉路を構成できるため、閉路が存在した場合閉路にどんなに辺を追加しても条件を満たす閉路を構成できる→グラフの閉路から誘導部分グラフを抽出したときかならず条件を満たすグラフがその誘導部分グラフの部分グラフに含まれる、ということになります。

 

実装方法は諸説ありそうですが、僕は頂点を削っていく方法ではなく、全ての頂点に対して最短で戻ってこれるようなパスを探す→そのパスが条件を満たすかどうかを調べるという方法で実装しました。

これの正当性は、条件を満たすグラフはある頂点に対して戻ってくるまでの最短経路になる(寄り道するならそもそも条件を満たさない)ということからわかります。

計算量はすべてがコスト１の辺のグラフと見て閉路検出に幅優先探索を用いてO(M), これを全ての頂点に行うので総計算量はO(N * M)になりました。