【久しぶりの全完】ABC185 参加記&解法メモ

AtCoder Biginner Contest 185 全完しました！

やったぜ。

A - ABC Preparation

1回のコンテストを開くのに100~400点の各問題が1問ずつ必要なので、入力のうち最も小さい数字を出力すればよいです。配列で受け取って最小値を返す関数を使うのが楽だと思います。

B - Smartphone Addiction

家を出る時をB0、家に帰る時をAM+1として、(現在の容量)-(Ai+1-Bi)>0 のチェックと（現在の容量)=max(N,(現在の容量+(Ai+1-Bi))を繰り返せばいいです。

これがBに置かれるの、令和を感じますね……

C - Duodecim Ferra

なんか最初箱とボールと勘違いしました……

鉄の棒の欠片がL個あると考えると、L-1個の欠片のすき間のうち11個を選ぶ通り数、すなわちL-1C11

オーバーフローしそうだな～と思ってL=200を試すと明らかにオーバーフローしていたので、BigIntegerで殴ると通りました。

D - Stamp

ハンコの使用回数を最小にしたいので、ハンコの幅kをなるべく大きくしたいです。

kの上限は白が連続する区間の最長の長さなので、（それを超えると青に重ならずハンコを押すのが不可能になります）白が連続する部分の長さを数えてNに対して切り上げ除算すればいいです。これはAi+1-Ai-1の最小となります。端っこは別途計算しておきました。0除算とかM=0の場合とかいろいろコーナーもあるので気を付けました。

F - Range Xor Query

Dを解き終わった時点で順位表を見ると茶緑の人達が無限人Fを通していたので、先にFを見ました。問題開きながら「タイトル的にセグ木とかかな～」とか思ってました。そしたら親戚のおじさんの顔より見た貼るだけセグ木だったので、貼ったら通りました。

E - Sequense Matching

これ最初全然わかんね～っつってたんですが、A'i!=B'iであるときにコスト1で両者を取り除く、みたいに考えると、DP[i][j]:=AiとBjまで見たときの最小コスト、みたいに管理できそう、と思いつきました。

こんな感じの漸化式に帰着できます。

このDPなんか名前付いてないのかな～とか思ったけどよく考えたらLCSとやってることほとんど変わらないですね。それぞれi,j文字目まで見たときの状況を2次元テーブルの要素として管理する、みたいな。

感想

50分ノーペナ全完、かなりいい出来だと思ったんだけど黄パフォ取れないんですね。壁が高いぜ……。

ABC152-F Tree and ConstraintsをbitDPで解く

ABC152-F "Tree and Constraints"の解説記事です。想定解法やいくつかある解説記事はどれも包除原理を用いた解法でbitDPでの解説記事が見つからなかったので、簡単に書き残しておきます。

問題へのリンクはこちら

atcoder.jp

 

簡単な考察

辺を順番に塗り分けていきます。

最初の段階ではM個の制約はどれも満たされていません。辺を黒く塗ったとき、いくつかの制約が満たされることがあります。

ある時点である制約が満たされているとき、その後どのような塗り分け方をしてもその制約が再び満たされなくなることはありません。

なので、N-1本の辺を塗り分け終えるまでに、すべての制約を1度でも満たせばよいです。

制約（紛らわしいですが、ここでいう制約は入力される値の範囲です）をぐっと睨むとMが非常に小さいのでbitで管理したい気持ちになります。

DP配列の定義

　dp[i][S]:=i個目の辺を塗り終えた時、状態Sとなっている塗り分け方の数

と定義します。

ここでSは、既に満たしている制約の集合です。これをbitで管理します。j番目のbitが立っている(1になっている)とき、j番目の制約が既に満たされていることを意味します。10進数整数で表すと0≦S<2^Mとなります。

初期値はdp[0][0]=1となりますね。

この配列を配るdpで更新していきます。

i本目の辺を白く塗る時

　dp[i+1][S] += dp[i][S]

これはわかりやすいですね。辺を白く塗ったときに制約が新しく満たされることはないためです。

i本目の辺を黒く塗る時

i本目の辺を黒く塗るとき、状態がどのように変化するかを考えます。

ある制約jについて

• i本目の辺が2点(uj,vj)のパスの一部である場合、制約jが満たされます。
• そうでない場合、制約jの状態は変化しません。

ということが言えます。

集合Tを、i本目の辺が2点(uj,vj)のパスの一部であるような制約jの集合とします。

TをSと同じようにbitで管理しておくことで、次の式が成り立ちます。

　dp[i+1][S | T] += dp[i][S]

集合Tは、制約jで与えられる2点(uj,vj)のパス上にある点を事前に計算しておくことでO(M)で求められます。この事前計算はLCAを使うと楽にできますが、今回の問題は小さな木なので、すべての制約に対してBFSと経路復元を行っても十分間に合います。

 

あとはいつも通りfor文でDPやるだけです。

dp[N-1][(1<<M)-1]が求める答えとなります。答えが32bitに収まらない可能性があるので、64bit型整数を使うのがよいでしょう。

計算量はO(N*(2^M))となります。

 

普通にACした時の乱雑コードですが、一応自分の提出を置いておきます。（C#です）

atcoder.jp

包除原理解法もやらなきゃな～

 

 

【色変記事】青色になりました！

はじめに

この記事はどきんさん(@ayoiyouyoeyo)の企画した色変記事 Advent Calendar 2020 2日目の記事です。

きっかけ

色変記事AdventCalendarを作成しました。
みなさまの勇気ある宣言をお待ちしております！https://t.co/1NqMxq7Wu3

— どきん@youtubeはじめました (@ayoiyouyoeyo) 2020年11月4日

やってしまいました…… https://t.co/gJXAdy2SL7 pic.twitter.com/vgTXeDUP5v

— じーふぉーぽんたん (@G4NP0N_kyopro) 2020年11月5日

スクリーンショットを撮ったので、誰がダサいか一目瞭然になっています。

— どきん@youtubeはじめました (@ayoiyouyoeyo) 2020年11月5日

いや怖いよ。「お待ちしております！」から一転してこの圧のかけ方。闇金とかも最初借りる時はニコニコしてて穏やかだけど取り立てが始まると豹変しますからね。ヤミ金ウシジマくんで読んだから間違いない。

そもそもお前は誰

がんぽんです。じーふぉーぽんたんとかG4とかけっこうみんな好き勝手呼びます。

北海道大学工学部の学士4年で、研究室ではプラズマ中の電子挙動のシミュレーションとかをしてます。来春から関東で就職です。

アドベントカレンダー登録時のレートは1400弱でした。

 水色で停滞してもがき苦しんでいる様子が見て取れますね。「入水記事？俺にとっては水色なんて通過点だぜ」とかイキって入水記事を書かなかった自分を殴りたい気持ちでいっぱいですが、まあこうやって色変記事を書けたのでヨシとしましょう。

 前置きはこれくらいにして、本題に入りましょう。

青色になりました！！！！！！

AtCoder青色になることができなくて、顔面が真っ青になりました。 

いかがでしたか？

ごめんなさい。冗談です。いやAtCoder青色になれなかったのは本当なんですけども。

いやあ、悔しい。

言い訳をすると、登録時から12/2までにコンテストが6回しかなかったので、平均してパフォーマンス1850を維持する必要があったんですよね。なかなかハードルが高い挑戦だったんですよ。まあそれにしても、青パフォ2回しか取れず3回1200台取ってる時点で水色適正をわからされてしまった感はあります……。

ただ、アドベントカレンダー登録したからには青色を目指そうと思い、今までの精進方法と趣向を変えてJOI埋めやこどふぉバチャに参加するようになりました。それがHighest更新にきちんと効いた感じはあったので、今後も続けていきたいですね。

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

AtCoder青色になれなかったので書きません。

ところで

 Codeforces青色になりました！！！

これでタイトル詐欺とは言われないな。安心安心。

こどふぉで青になるまでにやったこと

こどふぉ青=AtCoder水,みたいな言説はよく見かけるんですが、実際にはそんなことないと思います。問題の傾向も難易度傾斜も全然違うので、全然別ものなんじゃないかなあ。どっちが上とかではなく。慣れも必要だろうし。

バチャに参加する

これが一番効きました。というかこれしかやってないみたいなところあります。

div2のD,Eくらいまでだと「知らないアルゴリズムを使う必要がある問題」みたいなものはほぼなくて、純粋に知識を引き出しから取り出す練習として非常に効果的だったと感じます。

バチャは主にタイヨウさんの主催しているMornigforcesと、えすえふさん の主催していた夜21時のバチャ(名称はありませんが、参加していると「えすえふさんファンクラブ」というTwitterのリストに追加されました)のうち、都合が付くものに参加していました。あとはAtCoderのコンテストで冷えた後に「二次会」と称してTwitterで並走仲間を探して自分で建てたりもしてましたね。

Codeforces Anytimeを使うと、バチャの結果に応じて仮想のレートが変動して、これがけっこうモチベーションになっていました。

ところでバチャだとすげーいい成績残せるのなんなんだろうな……。

DeepLを使う

 自分の英語力を信用していないので、基本的に問題文はDeepLに突っ込んで読んでいました。数式とか添え字は正しく読んでくれないので元の問題文と並べて読む必要はありましたが、自分で英語を読む苦労に比べたらそれくらい大した問題ではないですね。

ただ、"at most one"を「1つ以上の」と訳すのだけは勘弁してほしい。本当によ。誤読で30分溶かさせんなや。俺の英語力は幼稚園児レベルなんだからよ。

まとめと今後の展望

卒論の中間発表でもこんなタイトルのスライド作った記憶があるな……。

• AtCoder青色になれませんでした
• Codeforces青色になりました
• 大学卒業までにはAtCoder青色になりたい
• こどふぉ紫はなれそうだけどパチンコ要素強いからわかんね～

以上です。ありがとうございました。