MEMORANDUM CEDRETABRI

ARS LONGA VITA BREVIS

AtCoder Regular Contest 014 の C 問題

C - 魂の還る場所

古い ARC は難易度が読めなくて、ワクワク感がある反面、練習には微妙かもしれない。

この問題はとても面白かったので解説したくなった。

概要

赤、緑、青のボールが  {N} 個並んでいる。これを、順番に両端が開いた筒の中に入れていく。
右から入れても左から入れてもいいが、同じ色のボールが接触すると消滅する。
上手く筒の中のボールの数が少なくなるように入れていった場合、最後には何個のボールが筒の中に残っているか。

 {1\leq N\leq50}

考えたこと

 {N} がとても小さい。
なので、その辺りを工夫してどうにかできないかなぁ、と最初は考えた。
のだけど、色々試しているうちに何となく思えてくることがあった。

「あれ、これって上手くやれば偶数個までなら消せるのでは?」

というわけで、これを証明(?)してみた。

証明っぽいもの

筒の中に何個ボールが残っているか、何色のボールが入ってくるか、で場合分けをする。
ここで、筒の中のボールの色を固定しても一般性を失わないような気がするので、それで説明していく。

筒の中のボールが【】の時、赤色のボールを入れる

右から入れても左から入れても同じ。
筒の中には赤色のボールが1個残る。

筒の中のボールが【赤】の時、赤色のボールを入れる

同じ色なのでボールは消滅する。
筒の中のボールは無くなる。

筒の中のボールが【赤】の時、緑色のボールを入れる

この場合も、右から入れても左から入れても同じ。
何故なら、これ以降の処理を全て左右逆にすることで、反対側の操作と全く同じ結果になるから。

筒の中には赤、緑2個のボールが残る。

筒の中のボールが【赤緑】の時、赤色/緑色のボールを入れる

同じ色なので、ボールを消すことができる。
天下り的かもしれないが)【赤緑赤】のように、敢えて消滅させない入れ方は考えない。

筒の中のボールが【赤緑】の時、青色のボールを入れる

筒の中のボールは3個になる。
この時、あり得る形は【赤緑青】か【青赤緑】かのどちらで、これは「左右を操作することで、真ん中に来る色を選ぶことができる」という意味。

さて、ここまで考えると、筒の中にボールが3個の時というのは、必ず3色のボールが残っているということがわかる。

筒の中のボールが【赤緑青】の時、赤色/青色のボールを入れる

ボールは消滅し、筒の中には2個のボールが残る。

筒の中のボールが【赤緑青】の時、緑色のボールを入れる

この場合は、緑色のボールを消すことはできず、筒の中のボールは4個になる。

が、筒の中のボールが2個の時に述べたように、3つ並んだボールの真ん中の色は選ぶことができる。
そして問題の条件から、  {i} 番目のボールの左右を決める段階で、  {i+1} 番目のボールが何色かは判然としている。
つまり、筒の中にボールが3個になる時、その次のボールを消すような入れ方にしておくことは必ず可能となるわけだ。

よって、上の場合分けから、「筒の中に入っているボールはどのタイミングでも高々3個」にできるし、「その色は全て異なる」ことが言える。
言い換えると、「ある色のボールを筒に入れる時、もし筒の中に同じ色のボールが既にあるのなら、その2つのボールは消滅する」

さて、与えられた  {N} 個のボールのうち、赤色が  {R} 個だったとする。
 {R} が偶数なら、上で述べた手順で全てのボールを消滅させることができる。
 {R} が奇数の場合は、最終的に筒の中に1個の赤ボールが残ることとなる(1個だけだと消滅させることはできないので)。そして、赤色のボールをこれ以下の個数にすることはできない。

これらのことは、緑も青も同じに言える。

以上から、この問題は「赤、緑、青色のボールをそれぞれ数えて、奇数の色の数」が答えになることがわかる。

実装

import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.bigint;

void main()
{
    readln;
    auto S = readln.chomp.to!(char[]);
    int r, g, b;
    foreach (c; S) {
        switch (c) {
            case 'R':
                ++r;
                break;
            case 'G':
                ++g;
                break;
            case 'B':
                ++b;
                break;
            default:
        }
    }
    writeln(r%2 + g%2 + b%2);
}

感想

考えるのが楽しい問題だった。

意図したかどうかはわからないが、  {1\leq N\leq50} という制約はちょっと意地が悪いなぁと思ったり。
 {N} の最大が  {50} の条件で、まさか  {O(N)} で解けるとは瞬時には考えないような気がする。
(勿論、制約から解法を見繕うみたいなことをするのが悪いのだけど。)

AtCoder Regular Contest 017 の C 問題

C - 無駄なものが嫌いな人

また古い問題を持ち出してきたなぁ、と思うかもしれない。まぁそうなんだ。
今、 ARC のA問題とB問題を毎日解く、みたいなことをやっていて、解けるならC問題まで解くようにしている。

このC問題、今まで僕は半分全列挙の問題をあまり解いたことがなく、解いてみて面白いと感じたので、丁寧に考えてみることにした。

概要

 {N} 個の品物がある。それぞれの重さは  {w_i} である。合計が  {X} になるような組み合わせは何通りか。


1\leq N\leq32 \\
1\leq X\leq10^{9} \\
1\leq w_i\leq5\times10^{7}

何を考えたか

まず制約を見てぱっと思いつくことは、

  •  {X} が大きい
  •  {N} はやたら小さい

ということだろうか。

問題文にはナップサック問題っぽいことが書いてあるが、この  {X} のサイズだと動的計画法では難しそう、という予感がある(でも1回試しちゃった)。

というわけで、  {N} が小さい点に着目してみる。小さいとは言っても  {32} なので、組み合わせを全列挙するのは難しそう(  {2^{32}=4294967296} )。そう、全部列挙するなら……。

というわけで、半分全列挙が出てくる。

半分全列挙

典型テクニックの1つだと認識している。
対象を半分に分け、それぞれの中で全列挙して、その後でそれぞれの要素を突き合わせるような手法である。

例えば今回の問題。  {2^{32}} は非常に大きい数になってしまうのだが、その半分の  {16} 個の組み合わせを全列挙するだけなら、  {2^{16}=65536} ですむ。なので、まず半分ずつ全部の組み合わせを試した後、それぞれのグループから1つずつ取り出して合計が  {X} になる組み合わせを数え上げれば良い。最後に突き合わせる処理に二分探索を用いることで、計算量を抑えることができるのがポイント。

二分探索

上に挙げたように、最後に組み合わせを数える際に愚直にやってしまうと、結局  {2^{N}} かかってしまう。しかし、合計が  {X} になればいいのだから、ソートした後に二分探索をすることで  {O(2^\frac{N}{2}log2^\frac{N}{2})=O(N\times2^{\frac{N}{2}-1})} の計算量ですませることができる(この時、同じ数値が複数個出てくる場合を考えなければいけないので注意)。

二分探索はあらゆる場面で役に立つのだ。

ハッシュテーブル

この記事を書いている間に気付いたのだが、合計がきっちり  {X} になる場合のみ数えればいいのだから、別にソートして二分探索しなくても、ハッシュテーブルに突っ込んでしまえばいい。

これで全体の処理はかなり簡単になる。

実装

実際のコードはこんな感じ。

import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric, std.bigint;

long[32] WS;

void main()
{
    auto nx = readln.split.to!(int[]);
    auto N = nx[0];
    long X = nx[1];
    foreach (i; 0..N) WS[i] = readln.chomp.to!long;

    auto ns = [0L], nss = [0L];
    foreach (i; 0..N/2) {
        foreach (j; 0..ns.length) ns ~= ns[j] + WS[i];
    }
    foreach (i; N/2..N) {
        foreach (j; 0..nss.length) nss ~= nss[j] + WS[i];
    }
    int[long] ND;
    foreach (n; nss) {
        if (n in ND) {
            ++ND[n];
        } else {
            ND[n] = 1;
        }
    }

    int res;
    foreach (n; ns) {
        auto x = X - n;
        if (x in ND) {
            res += ND[x];
        }
    }

    writeln(res);
}

Ruby でも実装してみた。かなり簡潔に書ける。

n, x = gets.split.map(&:to_i)
ws = n.times.map { gets.to_i }

def zr ws
  ws.reduce([0]) { |ns, w|
    ns[0...ns.length].each do |n|
      ns << w + n
    end
    ns
  }
end

ns = zr ws[0...n/2]
nd = zr(ws[n/2..-1]).reduce(Hash.new { 0 }) { |nd, n| nd[n] += 1 and nd }

puts(ns.reduce(0) { |a, n| a + nd[x - n] })

感想

最初やった時は「半分全列挙と二分探索との組み合わせで解けるの、応用っぽくてカッコいい」と思ったのだが、よく考えてみたら二分探索は不要だった(解説では二分探索の利用に触れていたけど)。

半分全探索がかなり綺麗に嵌る問題に見えるので、練習にはとても良かったと思う。

株式会社ドワンゴを退職しました

孔雀は折らない(新卒入社ではないので)。

8月いっぱいで株式会社ドワンゴを退職します。
つまり今月で終わりなので、退職エントリを投稿しておこうと思う。
「退職しました」じゃなくて「退職します」が正しい……はい。

いつ入社したのか

去年の末、2018年12月に入社した。9ヶ月前だね。
この期間で退職してしまうというのは、つまりまぁ、それなりの理由があるわけだけど、そういうことを書いても気分が明るくなるわけもないので、ここでは楽しい話だけをしたいと思う。

そういうわけで、ドワンゴの良い(僕が良かったと感じた)ところを挙げていく。

ドワンゴの良いところ

たくさんある。

競技プログラミング

ドワンゴ競技プログラミング部は強くて優しい人たちがたくさんいる。
前職のように毎週定例があるというわけではなかったのだけど、オンラインやオンサイトのコンテストには皆積極的に参加していた。

どうして定例がなかったかという話だけど、実はスケジュールだけは毎週入れてあって、パラパラと人が集まって黙々と問題を解いていた。皆で同じ問題を解いたり、解説をしたりといった活動も、試してはみたのだけど、定着しなかった。これは何故かと言うと、部員間の実力に結構な差があって、上は赤コーダから下は僕のようなのまでといった広いレート層の人々が参加していたので、共通の問題を解いたり解説したりと言った活動にあまり意味がなかったのだと思う。

ただ集まって同じ問題を解かないからと言って、部としての活動がなかったわけではなくて、例えば AtCoder のコンテストの後では、会社の Slack で問題の検討とか解説とかが行われたりしていた。
また、休日に観光地に赴いて1泊2日の合宿などもした。この時は ICPC の過去問を解いた。幹事を務めてくださったやおっち、本当にありがとうございました。とても楽しかったです。

ocaml_lunch

毎週 ocaml_lunch というイベントがあって、 OCaml に興味のある人達と一緒にランチができた。こういう名前だけど、話題が OCaml 限定ということはなくて、関数型言語とか型理論とか定理証明とか、そういう話題を広く論じることができる場だった。僕はそっち方面に関しては素人同然だったのだけど、専門で学んでいる方々の話が聞けてとても為になった。

僕自身は仕事で OCaml を使うことはなかったけど、社内では OCaml で開発している部署もあって、そういう部署の人達に実用的な OCaml の情報を聞くこともできた。主催者のよしひろさん、本当にありがとうございました。

ちなみにドワンゴで開発している、 OCaml 製のプロダクトというのがこの fialyzer
Erlang の静的型解析ツールである。

KBKZ.rb

ドワンゴには Ruby で開発している部署が幾つかあって、社内に Rubyist も結構いる。
そういう人達が集まって、 Ruby についての話題を語り合う場として KBKZ.rb という社内勉強会が催されていた。

週一のペースで開催されていたのだけど、話題が尽きることはなくて、 Ruby の言語仕様とか面白い挙動、「こういう事やりたいんだけどどうすればいい?」みたいな質問相談などなど、皆で話し合って情報を共有したり、疑問を解決したりすることができた。
Ruby そのものについての知識は深まったし、 Ruby のライブラリや周辺環境に関する見識も涵養された。本当に有意義な時間だったと思う。

主催者のただしさん、本当にありがとうございました。

ちなみにドワンゴRuby を使って開発している部署には、例えば教育系がある。

【教育事業】Webアプリケーション開発エンジニア(正社員)

エンジニアLT

ドワンゴには毎週エンジニアが LT をする場としてエンジニア LT というものがある。
管掌部署の消滅で一緒に消えかかったりしたのだが、無事有志のボランティアで継続されたという、社員からも愛されているイベントだ。

僕もこの LT で何度か発表させてもらった。内容は……うん、まぁ。いや、こういうのは発表することに意義があるのではなかろうか。
9ヶ月ドワンゴにいたのだけど、合計で9回LTをした。つまり1月に1回のペースだ。
発表の為に調査し、資料を作り、練習をする経験って貴重なものだと僕は思っているので、そういう経験を何度も積ませてもらったこのエンジニア LT は本当にありがたいイベントだと思う。

ボードゲーム

ドワンゴでボートゲーム部と言った時、実は似たような活動がたくさんあって、大きく「ポーカー」「ボードゲーム」「TRPG」などに分かれている。
その他に「麻雀部」「囲碁将棋部」があったみたい。カードゲーム部もあったかな?

この内最大派閥は(派閥、というかメンバーが被ってたりするのだけど)多分ポーカー部で、業務後に社内のカフェに集まってポーカーに興じるなどしているのだけど、4日連続で集まっていた週などもあった。

僕もこのポーカー部の活動にちょっと参加させてもらって、生まれてはじめてテキサスホールデムを遊んだりした。
これはとても楽しかった。と、同時に、なるほどポーカーは確率と考察力と観察力の勝負なのだな、と痛感したりもした。

ボードゲーム部は、多分エンジニアの強い会社には大抵あると思っていて(前職でもあった)、いわゆるアナログなボードゲームを使って遊ぶ集団だ。
ドワンゴのオフィスにはたくさんボードゲームがあった。どのくらい「たくさん」かと言うと、ボードゲームが棚を埋め尽くしていて、入り切らない分は秘密の場所に格納していたくらい。週に1回とか2回の頻度で会を開いて、そのボードゲームで遊んでいた。
カタンドミニオンといった定番から、ちょっと名前が思い出せないマイナーボドゲまで様々あったが、新しく出たボードゲームを皆で遊んでみることが多かったように思い出せる。
うっかり重いゲームに手を出してしまったが最後、危うく終電を逃しそうになることも何度かあった(ドワンゴは近距離手当の制度があり、かつ自転車通勤も認められていたので、終電なんかに束縛されない同僚も多かったけど)。

TRPGボードゲーム部からの派生。ただしこれは、その遊戯の性質上「仕事終わりにさくっと」とはいかないので、休日に集まってプレイする形だった。 オフラインセッション、興味はありつつも手を出せずにいたのだが、ドワンゴに入ってようやく機会を得ることができた。とても楽しくて興味深い経験となった。

その他、麻雀に関しては、ちょっと時間的な都合が合わず、とても残念ながらほとんど参加することはできなかった。

銀座のご飯

お手頃価格でとても美味しい。
「銀座って高そうじゃない?」というイメージがあるかと思うのだけど、ランチは1000円くらいだよ(1000円でも高いよ! って突っ込まれたこともあるけどね……)。しかもそういうランチを、夜に高いお金で食事を出す優良なお店が提供してくれる。これは最高。
店の数も多く、種類も多く、よりどりみどり。道はよく整備されているから、少し遠くのお店でも散歩がてら食べに行くのが苦にならなかった。裁量労働なので一番の混雑期を外して食べに行ける点も大きい。

退職した人達が、お昼だけはわざわざ銀座までやってきて食べているのも目撃している。それくらい美味しいお店が多い。

銀座ランチ、機会があれば是非とも体験してみて欲しい。

なんで辞めるの?

これについては割愛する。

次は何をするの

次は教育系の開発のお仕事をする。

言語やフレームワークは、 RubyRails 、 TypeScript と React などになる。
これらの、「今まで浅くは関わっていたけど仕事でちゃんと触った経験が少ない」技術をきっちりと考えたいと思っていたので、とても好ましい環境だ。
強い、尊敬する Rubyist の人達がいるのも嬉しい。

じゃあ Scala に対する興味を失ったかと言うと、全然そんなことはなくて、今でも Scala は仕事で使いたい言語のトップである。
機会があればまた Scala で仕事をしたい。

また、今は BuckleScript と ReasonML にどっぷりはまっているので、これも続けたい。
仕事で使うのは……まぁ難しいかもしれない(けど、機会があれば是非!)

株式会社オプトを退職しました

2018年11月いっぱいで株式会社オプトを退職した。
……退職エントリ書くのに随分間が空いてしまった。

いつ入社したのか

2016年の1月。なので、オプトでは2年11ヶ月働いたことになるね。
僕が入社した時は、社内にエンジニアはいても「エンジニア組織」が存在しない時期で、ちょうど「これからエンジニア組織を作っていくぞ」という段階だった。

何をやっていたのか

Web の広告代理店なので、 Web 広告に関するシステムに手を入れたり作ったりしていた。
広告の効果測定ツールとか、データフィードの最適化ツールとか、そういう感じのもの。
使っていた技術としては、概ねサーバサイドが Scala 、フロントエンドは色々(古いものは CoffeeScript や AngularJS 、新しいものは TypeScript や React )だった。他にも RubyJavaPHP のプロダクトもあったけれど、僕は触っていない。
僕は主にサーバサイドとバッチとかを書いていたのだけど、時々フロントを触ったりもしていた。インフラは、少なくとも新しいものに関してはほぼ全てクラウドで、その設定とか操作とかをやることもあった。

上から下まで、割と色々と経験できて、とても良かったと思う。

どんな環境だったの?

上に書いたように、僕が入社した段階ではまだエンジニア組織を組成する段階で、エンジニア向け制度含めて諸々が何も決まっていない段階だった。
なので、いわゆる一般的な「エンジニア向け」制度とかは一切存在しない環境からスタートしたわけだけど、僕が在席している間に開発部の部長(現 CTO )を中心としたエンジニア勢で頑張って制度を整備していった(僕も微力ながら力添えできたと信じたい)。これは、会社側の経営陣や非エンジニア社員達の理解があったことも大きいと思う。
まず、入社から半年弱後の6月くらいにエンジニアは裁量労働制に移行した。移行したその日から、12時くらいに出社する人がたくさんいた(この頃は12時でも遅かったんだなぁ)。

それを嚆矢として、例えば「飲み物を好きなだけ飲みたい」とか「良い椅子じゃなきゃヤダ」とか「本買って」とかたくさん出てきた要望を、エンジニアが主体となって交渉して、制度を作って、整備するという流れができていった。「自らの手で自らの組織を改善していく」みたいな仕組みが作られていったわけだ。もちろん、何か制度作ったり環境を良くしたりといったことにはお金が必要となるわけで、それは降って湧いてきたりはせず、会社との交渉が必要だったのだけれど、その辺り、とても上手いことやっていたなぁと今では思う(というか、上に挙げた元部長現 CTO の並々ならぬ努力と粘り強さが功を奏した、といったところだろうか。本当にありがたい)。

このように、就業環境に関してはとても快適で、自由度が高いものだったと思う。それが、単に与えられたのではなくて、徐々に形作られていった過程を目撃しているので、有難味も一入だった。

それらを含めた就労環境や、現在の制度については、会社の公式ページや技術ブログに書いてあるようなので、そちらに説明を譲りたい。
僕が退職してから時間も経っていて、記憶が曖昧だったり制度が変わっていたりすると思うから。

Opt Technologies
Opt Technologies の評価制度について

どんなところが良かったの?

幾つか挙げていきたい。

自由度

圧倒的に高かった。
上で書いたように、裁量労働制で、ミーティングなどの約束を守り成果を出している限り、出勤と退勤の時間は自由だった。
17:55 に出勤して 18:00 に退勤したこともある(本当なんだ。まぁ家で仕事してたのだけど)。
あと、週に1回の完全リモート勤務と、好きなだけの部分リモート勤務(午前家で仕事して午後出社、とか)が認められていたので、そういうのも活用できた。
完全リモートは前日までに Slack などで周知必須だったけど、部分リモートはそういう制約もなかった。会議へのリモート参加とかで準備が必要な場合は、その面倒は見ないといけなかったけれど。

この完全リモート勤務の「週1回まで」というのはあくまで原則なので、妥当な理由があれば調整はきいた。僕自身は同僚と全く顔を合わせないで仕事することをあまり好まなかったけど、活用していた人はいた。

その他、開発環境など。
妥当性があれば利用する技術やツールは好きに選べた。妥当性がそれほど強くなくても、説得すればなんとかなるようなところがあったと思う。

技術好きな人が多い

純粋に色々な技術が好きな人が多かった。
あまり偏りもなく、純粋に数学や言語理論とかが好きな人もいれば、競技プログラミングが好きな人、インフラや IoT が好きな人、特定の言語が好きな人、フレームワークやライブラリが好きな人、フロントエンドヤクザ、設計手法や方法論が好きな人、チームビルディングやスクラムが好きな人、経営や起業に興味がある人など、人数はそれほど多くないのに興味は多岐に渡っていた。
社内勉強会とかでも色々なジャンルの、仕事に関係あったりなかったりする LT が毎回話されていたし、仕事終わりに机の周りや、社内にあるカフェや、あるいは社外の居酒屋や飯屋で集まって、そういう話を尽きず語ることが日常茶飯事だった。
何より良かったのは、そういう好きな分野、好きな対象がアチラコチラに向いていたにもかかわらず、お互いの主義主張をきちんと尊重するような空気があったことだと思う。いわゆる HRT がかなり高い水準で守られていたように思える。

競プロ部

これはかなり個人的な理由。僕はオプトの競プロ部がきっかけで競技プログラミングを初めた。
今のオプトの競プロ部にはそれなりの人数がいるのだけど、創設者でもある部長は ICPC の OB で、その方が毎週競プロ会を開き、問題やアルゴリズムの解説などを粘り強く行われた結果、着実に成長していったものだ。僕が競プロを知れたのもその人のおかげなので、本当に感謝する他ない。
2018年、2019年ともに、オプトは ICPC のスポンサーをしているわけだけど、そういうことができているのも、偏にその競プロ部部長の努力の賜物だと思う。

有給が多かった

これは、実は僕が無知でオプトを辞めた後に知ったのだけど、オプトの有給は(少なくとも Web 系では?)多い方みたい。
初年度、9月までの入社で15日付与、10月以降は10日付与、とかそんな感じ(月が間違ってたらごめん。気になる人は自分で調べてね)。
その後年度初めに、2年目が16日、3年目以降は毎年20日付く。
僕は1月入社だったので、最初に10日もらい、3ヶ月後の4月1日に16日増えた。オプトに入社するなら3月がおすすめということだね。
ついでに一応言っておくと、試用期間中(最初の3ヶ月間)も利用できる。

そして、これは僕の個人的な例なのだけど、あまり有給を使う方では無いので(あまり旅行したりしない)有給を余らせまくっていた。年を跨ぐ時20日しか持ち越せないわけだけど、そこで無駄にしないためにどうするか困るくらい。
上で書いたように2年11ヶ月しか勤めていないのだけれど、退職時には40日近い有給が残っていて、2ヶ月くらい有給消化に使うことになった。
有給の取得は、まぁ普通にできるような職場だったので、他の人は旅行とか行ってたみたい。いわゆる「リフレッシュ休暇」みたいな制度もあったから、長期旅行に行く人も多かった。僕はちょっと制度を活用できなくて損をしてしまったなぁ。

オプト辞めて他の会社に行った時、「え、これだけしかもらえないんだ」「え、試用期間中は使えないの?」と驚いてしまったよ……世間知らずは怖い。
まぁ世の中には初年度から20日もらえるような場所もあるみたいなので、あくまで相対的な話ではあるけれどね。

何で辞めたの?

良さそうなことばかり書いてるけど何で辞めたの? となると思う。
正直、ネガティブな理由はあまり無い。

  • toB の仕事の経験しかなかったので、 toC の仕事もやってみたかった
  • もっと別の、 Scala の強い人がたくさんいる環境で働いてみたかった
  • 面接受けたら内定もらった

あたりがメインの理由かな。

まぁ本当に「ネガティブな理由が全く無い」のかというと、それは流石に嘘になって、色々辛いところはあったのだけど、どんな会社にも多かれ少なかれ問題点というか、制度上の欠点や足りない部分はあると考えているので、それを殊更あげつらう意味は無いかな。

AtCoder Beginner Contest 133 E

E - Virus Tree 2

この問題はコンテスト中には時間が足りなくて解けなかったのだけど、その後解いたので、何を考えたかを書いておきたい。

こういう木の問題、僕は割と好きだ。

概要

木がある。各頂点を  {K} 色以下に塗り分けたい。ただし、頂点同士の距離が  {2} 以下の場合は別の色にしなければならない。さて、何通りの塗り分け方が考えられるだろうか。

よくある  {\mod10^9+7} で組み合わせの数を求める問題だ。

何を考えたか

ここでは、コンテスト中(と、終わった後少し)に僕が考えたことをつらつらと書いていく。

当時、ここまで筋道だって考えたわけではないと思うが。

順列を考える

まず、組み合わせについて色々考えてみた。

上のような条件無しで、同じ色は  {1} 度しか使えないこととして、  {N} 個の頂点を  {K} 色で塗り分ける方法はいくつあるだろうか?

これは順列なので、  {{}_K\mathrm{P}_N} で求めることができるのはわかる。

これをもう少し解きほぐしていくと、

  1. 頂点  {1} の色を選ぶ
    •  {K} 色残っているので、  {K} 通りの選び方がある
  2. 頂点  {2} の色を選ぶ
    •  {K-1} 色残っているので、  {K-1} 通りの選び方がある
  3. 頂点  {3} の色を選ぶ
    •  {K-2} 色残っているので、  {K-2} 通りの選び方がある
  4. ...
  5. 頂点  {N} の色を選ぶ
    •  {K-N+1} 色残っているので、  {K-N+1} 通りの選び方がある

それで結局、  {\dfrac{K!}{(K-N)!}} というご存知の公式が出てくるわけだが、ここでわかることは、

  • ある頂点で色が決まると、他の頂点が使える色の数は  {1} つ少なくなる
  • 全体の場合の数は、各頂点が選べる数の総乗

ということである。

(ここまでは多分中学生の数学の内容だと思う。のだが、僕の記憶は怪しかった……。)

距離  {2} 以下の頂点

ここで、問題を振り返ってみる。

上の条件だと、「その色を使えるのは全ての頂点で  {1} 回だけ」としたので  {1} つの頂点で色を決めたら他の全ての頂点で使える色が  {1} 少なくなったわけだが、今回の問題の条件だとそこが少し違っていて、

  • 距離が  {2} 以下の頂点で同じ色が使えない

これはつまり、

  • ある頂点で色を決めると、距離が  {2} 以下の頂点で使える色が  {1} つ少なくなる

と言い換えることができる。

そして、「全体の場合の数は、各頂点が選べる数の総乗」という点に変化はないはずなので、上手いこと各頂点の「使える色」を決めていってやればこの問題は解けそうである。

しかし、距離  {2} 以下の使える色を制限する、という状態をどのように持たせればいいだろうか?

最初は、全ての頂点に仮に  {K} の色を持たせておき、各頂点で色を決めたら、そこから距離  {2} 以下の頂点全ての色の数を減らす、みたいなことを考えたが、これだと計算量が大きくなりすぎる。

次に、各頂点の色を決める時に、距離  {2} までの頂点を見に行って、色が決まっていたら自分が使える色を  {1} つ減らす、みたいなことも考えたが、これもやはり計算量が大きくなりすぎる。

というわけで「配る」アプローチと「貰う」アプローチとの両方を考えたが、この  {2} つは結局やっていることは同じなので、どちらも上手くいかない。

なのだが、その両方を組み合わせるとどうだろう?

中間地点

ある頂点で色を決めることを考える。もし距離  {2} 以下の頂点のどれもがまだ色を決めていなければ、この頂点は  {K} 色の中から色を決めることができる。

そして色を決めた後で、自分に隣接する頂点の「隣接した頂点で色が決まっている数」カウンタに  {1} 加える。こいつが管理する数は、名前の通り隣接する頂点で決まった色の数だけだ(距離  {2} 以下の頂点全てではない)。

では最初に戻って、ある頂点が色を決める時、距離  {2} 以下の頂点でどれだけ色が決まっているか、どうやって判断すればいいだろうか?

まず、自分自身のカウンタを見る。これは、自分に隣接する頂点で色が決まった数なので、当然距離  {2} 以下に含まれる。

次に、自分に隣接する頂点全てのカウンタを見に行く。これは、自分に隣接する頂点に隣接する頂点、すなわち距離  {2} の頂点で色が決まった数を表す。

この時、自分自身をカウントしてしまう恐れはない。まだ自分の色は決まっていないからだ。また、同じ頂点を重複してカウントしてしまう恐れもない。何故ならグラフは木なので、ある頂点からある頂点への経路は高々  {1} つしか存在しないはずだからだ。

これらカウンタでカウントされている数の合計を  {K} から引けば、その頂点で使える色の数が出てくる。

要するに、「色を使った」という情報を中間地点にある頂点を経由して伝播させるわけだ。

この作業の計算量を見積もってみよう。全ての頂点を巡るので  {N} 回の処理。かつ、全ての辺を  {2} 回巡るので(配る時と貰う時)  {(N-1)\times 2} 回の処理。この  {2} つはそれぞれ独立しているので、計算量は  {O(N + (N-1)\times 2)} つまり  {O(N)} で収まりそうだ。

これはなんとかなりそう。

順序の問題

上の説明だけだと、どの頂点をどういう順番で処理していっても問題ないように思える。残念ながらそうではない。根付き木として、根から順に処理していく必要がある。

どうしてそうなるかと言うと、あまり上手い説明はできないのだが、たとえば直径  {4} 以上のある木の色を両側から塗っていったとして(当然、両端のノードで選べる色の数は  {K} だ)、それらが重なる付近で矛盾が起きる組み合わせが出てくる。

もう少し考えてみると、ある木の任意の  {2} つの頂点は、距離  {2} 以下の頂点同士を通って辿り着けることは自明なので、最初に色を決める頂点以外が  {K} 色から選べるということは絶対に起こらないはずなのだ。

そういう矛盾を防ぐためには、根付き木の根から順番に処理していく他ない。

(ごめんなさい、この節は僕の理解力不足でかなりいい加減なことが書いてあります。お叱りとか受けますので、もし変なことが書いてあったら容赦なく突っ込んでください。)

コード

解法が決まればコードに落とし込むだけだ。 よくある DFS なので迷うことはなかった。

import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

enum P = 10L^^9+7;

long[][10^^5] T;
long[10^^5] D;
bool[10^^5] M;

void main()
{
    auto nk = readln.split.to!(long[]);
    auto N = nk[0];
    auto K = nk[1];
    foreach (_; 0..N-1) {
        auto ab = readln.split.to!(long[]);
        auto a = ab[0]-1;
        auto b = ab[1]-1;
        T[a] ~= b;
        T[b] ~= a;
    }

    long r = 1;
    long[] ss = [0];
    M[0] = true;
    while (!ss.empty) {
        auto i = ss[0];
        ss = ss[1..$];
        auto ir = K - D[i];
        foreach (j; T[i]) {
            if (!M[j]) {
                ss ~= j;
                M[j] = true;
            }
            ir -= D[j];
            ++D[j];
        }
        r = (r * ir) % P;
    }
    writeln(r);
}

感想

好きなタイプの問題だった。

それだけに、コンテスト中に解ききれなかったことの後悔は大きい。

おのれ C 問題……。

AtCoder Beginner Contest 133 C

C - Remainder Minimization 2019

最初に言うと、僕はこの問題に大変な時間を取られ、大きくレートを下げてしまった。 なので、自戒としてこの問題の解説を書くことにする。

概要

 {L..R} の間で  {i} {j} とを定めて、  {(i\times j)\mod2019} を最小化せよ、という問題である。ただし  {0\leq L\lt R\leq2 \times10^9} なので全探索みたいなことはできない。

解法

 {\mod 2019} ということなので、  {i} {j} との差が  {2019} 以上の場合を考える必要はない(何故ならその場合、間には必ず  {n\mod 2019=0} なる  {n} が存在し、それを選ぶことで  {(i\times j)\mod 2019} {0} になるから)。 それさえわかれば、話は単純である。 解法の本質は以下のようなものとなる。

for i in L .. min(L+2019, R)
  for j in i+1 .. min(L+2019, R)
    result <- min(result, (i * j) mod 2019)
  end for
end for

見る範囲は  {L..R} {L..(L+2019)} かの狭い方になる。

実際のコードはこのような形。

import std.stdio, std.algorithm, std.conv, std.array, std.string, std.math, std.typecons, std.numeric;

void main()
{
    auto lr = readln.split.to!(long[]);
    auto L = lr[0];
    auto R = min(L+2020, lr[1]+1);

    long x = long.max;
    foreach (i; L..R) {
        foreach (j; i+1..R) {
            x = min(x, i*j%2019);
        }
    }
    writeln(x);
}

感想

掛け算の性質と剰余の性質とをちゃんと理解しておきたい(できていなかったのが敗因)。

簡単とか難しいとかは、解く人の経験とかに依存するから一概に言うことはできないと思うけど、少なくとも僕の経験を考えれば、「簡単に」解けて然るべき問題だったと思う。 強く強く反省したい。