足跡-sokuseki-

りかの日進月歩の記録

GitHubで過去のcommit logのメールアドレスを変更する

GitHubのメールアドレス変更が終わった後の話
基本はこれ：https://help.github.com/en/articles/changing-author-info#

変更したい repository の名前を repo とする

ローカルのその repository の外で
git clone --bare https://github.com/user/repo.git
cd repo.git
をして repo.git に入り、その中で

#!/bin/sh

git filter-branch --env-filter '

OLD_EMAIL="your-old-email@example.com"
CORRECT_NAME="Your Correct Name"
CORRECT_EMAIL="your-correct-email@example.com"

if [ "$GIT_COMMITTER_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_COMMITTER_NAME="$CORRECT_NAME"
    export GIT_COMMITTER_EMAIL="$CORRECT_EMAIL"
fi
if [ "$GIT_AUTHOR_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_AUTHOR_NAME="$CORRECT_NAME"
    export GIT_AUTHOR_EMAIL="$CORRECT_EMAIL"
fi
' --tag-name-filter cat -- --branches --tags

を書いて、hoge.sh として保存する。
OLD_EMAIL（変更前のアドレス）、CORRECT_NAME（名前）、CORRECT_EMAIL（変更後のアドレス）は書き換える。

sh hoge.shでスクリプトを走らせる。
これでローカルでは変更ができたはず。
（git logで変更されているか確認する。）

git push --force --tags origin 'refs/heads/*'
これでpushできる。あとは
cd ..
rm -rf repo.git
で repo.git を消せば良い。

その後、ローカルの repo を書き換えたいので、 repoのフォルダに入り
git pull --rebaseし、
git logで書き換わっていれば完了。

AOJ0310 枠

競技プログラミング AOJ

枠 | Aizu Online Judge

この高速化テクは典型らしいです。

問題

N \times N のグリッドがあり、各マスに数が書かれている。
このグリッドに太さ1マス分の長方形の枠をのせ、枠が覆っているマスの数の総和を最大化する。
ただし、枠は 1 \times 1 や 2 \times 2 や 1 \times 10 のように、中央に穴が空いていない場合もある。（詳しくは問題文の図を見て）

制約

1 \le N \le 300
-1000 \le p_{i,j} \le 1000

想定TLE

累積和をしてから、枠の左上と右下を全探索（ O(N^4) ）して、それぞれの枠についての総和をO(1)で求め、最大値を答える。
2次元累積和＋長方形領域の総和を求めるパートくらいバグらせずに素早く書けるようにしましょう。

ちなみにこの問題を見た当初は 300^4くらいいける！w と思って書いてTLEしました（バカかな？）

解法

累積和して区間の総和を O(1) で求めるのは変わりません。

しかし、枠の4辺を全探索すると O(N^4) で間に合いません。 O(N^3) に落としたいので、とりあえず2辺を O(N^2) で全探索して、残り2辺を O(N) で決めることにします。
ここで、2辺を O(N) でしようとしたときに、しゃくとりを思い浮かべると、対辺をペアにするという発想ができます。
上下と左右、どっちを全探索しても本質的には同じなので、ここでは上下を全探索することにします。


i 行目を上の辺、 j 行目を下の辺として、総和が最大になるように右辺（ r ）と左辺（ l ）を決めます。
f:id:wk1080id:20190413181021p:plain
まず i 行目と j 行目を採用することは決まっているので、 i 行目と j 行目のマスの総和を計算しておきます。ここでは、枠を決めたときのその総和からの差分を最大化していきます。

右辺と左辺を一度に考えるのは難しいので、先に右辺から考えます。
右辺を r 列目にすると決めたとき、

  • i 行目の r 列目以降の部分
  • j 行目の r 列目以降の部分

は、枠には関係ない部分なので、不要になります。
逆に、

  • r 列目の i+1 行目から j-1 行目の部分

は枠の一部なので必要になります。
f:id:wk1080id:20190413182753p:plain
よって
（ r 列目の i+1 行目から j-1 行目の部分） - （ i 行目の r 列目以降の部分） - （ j 行目の r 列目以降の部分）
を計算してあげればよいです。
これを 0 \le r \le n-1 のすべての r について求めてあげます。

そして、左辺の l についても同様で、

  • i 行目の l 列目より前の部分
  • j 行目の r 列目より前の部分

は、枠には関係ない部分なので、不要になります。
逆に、

  • l 列目の i+1 行目から j-1 行目の部分

は枠の一部なので必要になります。
f:id:wk1080id:20190413183500p:plain
よって
（ l 列目の i+1 行目から j-1 行目の部分） - （ i 行目の l 列目より前の部分） - （ j 行目の l 列目より前の部分）
を計算してあげればよいです。
これを 0 \le l \le n-1 のすべての l について求めてあげます。


これで前計算が終わったので、あとはこれらをうまく組み合わせて右辺と左辺を最適に選びます。
たとえば、 l を決めると、最大となる r は、 l < r をみたすもののうち、さっき計算した差分が最大となる r です。これは「右端が r 列目以降であるときの最大値」などを前計算してあげると O(1) で求められるので、右辺と左辺を計算するのは全体で O(N) でできます。（実際は l = r の場合などは別で計算した方が簡単になります）


AIZU ONLINE JUDGE: Code Review

競プロ合宿の開き方

競技プログラミング 参加記

はじめに

競プロ合宿といえば RUPC （立命館大学競技プログラミング合宿）や ACPC （会津大学競技プログラミング合宿）が有名だと思います。*1


最近、競プロ合宿の需要が増えている気がしていて、たとえば RUPC の参加登録はページ公開後1時間もしないうちに埋まってしまったり、



のように新たに競プロ合宿が開催されたりしています。


競プロ合宿は楽しいので、もっとたくさんの合宿が開催されてほしいなーと思い、合宿の運営のノウハウなどをみんなに共有したい気持ちになったので書きます。


ちなみに、そすうさは RUPC2017 / RUPC2018 / RUPC2019 の運営を経験しているのですが、この記事は自分から見た部分しか書いてないので、もし何か不備等があれば言ってください。
また、もっと詳しいことが知りたい場合は直接聞いてください。

RUPC / ACPCとは

RUPC は立命館大学が主催する競プロ合宿、 ACPC は会津大学が主催する競プロ合宿で、それぞれ例年3月と9月に開催されています。

これらの競プロ合宿の主な特徴は

  • 3日間にわたり、オンサイトでチーム戦のコンテストを行う
  • コンテストで使う問題は、どこかのコンテストの過去問ではなく、運営が用意する

となっています。

問題セットは立命館大学、会津大学、北海道大学が提供し*2、（主観的には） ICPC っぽい問題が出題されているみたい*3です。
コンテストは Aizu Online Judge （AOJ）で行っています。

競プロ合宿（RUPC）の運営の大まかな仕事

RUPC でやっていることを書きます。時系列じゃなさそう。

はやめにすること
  • 日程を決める

RUPC ではジャッジ（作問）をする3大学の予定をうまくすりあわせて日程を決めています。（だいたい1月上旬くらいに、いつにするか話し合い始めている気がする。）
日中に行われる他のコンテスト（企業コンや有志コン）と日程が被ってしまうと悲惨になってしまうので、コンテストを開催しそうな大学の人やちょくだいさんとDMで相談して避けるのがよいです。
3月は卒業式や学会が行われやすいので、そういうのも外そうと考え始めると、だいたい候補の日程は固まってきます。

  • 問題セットを提供してくれる人を探す

RUPC では例年会津大学と北海道大学に頼んでいますが、新しく合宿を開催するなどであてがない場合は、作問できそうな知り合いに声をかけてみるか Twitter などで募集するとよいと思います。
作問を頼む場合は、早めにコンテストの時間（3時間など）を決めましょう。何時間セットにするかを決めないとどういう難易度の問題をどれくらい作る必要があるかわからないので。慣れていないと作問は時間がかかりがちなので、作問者はできるだけ早く募集するといいと思います。
ちなみに RUPC では3時間セットで7問程度、5時間セットで13問程度出題されているようです。

  • 会場を抑えて参加人数を決める

日程が決まったら、会場を押さえましょう。遠方から来る人は大きい荷物を持って来ることが予想されるので、広めの部屋だと嬉しいです（コンテスト前・コンテスト後の交流とかも広いとやりやすい）。コンテスト中はみんなPCを使うので、会場に電源がたくさんあると良いです。もし電源が少なければ、その分たくさんタップを用意しましょう。
参加人数は、会場の広さや風船運びなどの運営の都合を考えて決めると良いです。

  • 懇親会の場所を決める

参加人数が多いと懇親会の会場を探すのが難しいがち。
たくさんの人と交流できるように、席を移動できるタイプのお店だと嬉しいなあという気持ちになります。

  • ジャッジシステムとして AOJ が使えるように会津大学の先生と連絡をとる

コンテスト開催の日程と時間が決まったら、先生と連絡をとりましょう。*4

  • ATND とフォームを書く

ATND には、どういう合宿か、場所や日時、スケジュールはどうなっているか、参加人数の枠や参加費はどのくらいか、懇親会はどうするか、みたいなのを書きます。（RUPCのATNDを参考にしてください）
RUPC の募集には ATND を使っていますが、昔はこくちーずを使っていたみたいです。こういうイベント告知サイトは他にもありますが、どこがいいかはよくわかりません。
ATND では懇親会の参加の出欠確認ができないので、Google フォーム を併用していて、そこでコンテスト・懇親会の出欠や名札の情報を集めています。
ATND とフォームの募集を締め切ると合宿の参加人数や懇親会の人数が確定できるので、締め切りの日時は懇親会の人数の確定日時とかに設定すると良いです。*5

  • 無線 LAN が使えるか確認する

無線 LAN が使える環境がないとコンテストがつらいです。

  • 風船や名札ケースやゴミ袋などを買っておく

RUPC の場合はだいたい Amazon で買い揃えます。
風船や問題文を入れる封筒は使いまわすので一度用意すればそれでいいんですが、紙コップやウェットティッシュやゴミ袋等は消耗品なのでちゃんと買いましょう。
名札は回収が面倒なので毎回使い捨てのやつを買ったりしています。別のオンサイトで RUPC の名札持ってる人を見かけると嬉しくなりがち。

  • 企業に協賛してもらえるなら連絡をとっておく

昔は RCO さんとかに協賛してもらっていて、そのときは懇親会費が無料になってましたね。その節は大変お世話になりました。

  • 大学の宿泊施設の予約など

立命館には学生のみが宿泊できる施設があって、ジャッジの3大学の人は大学に宿泊したりしています。

  • 作問

作問の仕方は Rimeの使い方 - beet's soil を参考にすると良いです。余裕をもって作問しないと炎上しがち。

直前にすること
  • お菓子と飲み物を買いに行く

買ったものは部室等に置いておき、当日の朝に会場に並べるのがいいと思います。もしそのような場所がなければ、当日の朝に買いに行くのが良さそう。
ちなみになんですが、70人分の3日間のお菓子と飲み物を一度に買おうとすると結構大変で、7人くらいいないと運ぶのが不可能。

  • 名札や受付の準備をする

参加者リストを作ってそれぞれ懇親会の金額を書いておくと、当日の受付のときに計算しなくてよくて便利だったりします。
名札にはアイコンと名前を書いていますが、もしかして所属の情報とか入れた方がよかったりしますか？（まあ必要なら勝手に余白に書いてもらうといいんですが）

  • 問題文の印刷

事前に問題が完成していれば先に印刷しましょう。 RUPC の立命セットは例年間に合ってないので Day 1 の朝に印刷していますが、非常にバタバタします。

  • 会場の設営の準備

チーム戦のために机や椅子をいい感じに配置します。これは当日の朝にやってもいいと思います。大掛かりな移動は前日までにやっておくと当日楽になる程度。

  • ネット接続のチェックとか

まあいらないと思うけど一応。*6

当日すること
  • 会場の設営

受付の場所をつくったり、お菓子や飲み物を並べたりします。飲み物は紙コップで飲むことになるので、紙コップを置くスペースや紙コップに名前を書くペンなどを用意しましょう。コンテスト終了後とかに感想戦などで人がお菓子の周りに群がりがちなので、スペースに余裕があるといいと思います。
あとはコンテストで使用するプリンターやコピー用紙も準備しておきましょう。

  • 受付で参加費等を回収する

同人即売会みたいに百円玉とかたくさんあるといいと思います。行ったことないから知らないけど。
RUPC2019 ではチーム決めにアプリケーションを使っていたので、それに使う AtCoder ID を聞いたりもしていました。
参加人数が多いと受付が混みがちなので複数人いたほうがいいです。名札は受付のところに並べておくと、来た人に勝手に取っていってもらえるので楽です。

  • 合宿中の司会・進行とか

社会性とコミュ力が試されます。スケジュールとか臨機応変にするのむずかしいね。*7

  • コンテスト中のあれこれ

風船を運んだり、clar （質問）対応をしたり、First Accept の記録をしたり、印刷クエリに対応したり、いろいろ

  • 解説後の片付けと懇親会への案内

風船や問題文を入れた封筒は使い回しているので、ちゃんと回収しましょう。あとはよしなに。




漏れがありそうだけど、だいたいこんな感じな気がします。
どこまで詳しく書けばいいかわかんないね。

最後に

運営は大変なこともありますが、参加した人に楽しかったって言ってもらえるのが一番嬉しいです。あと参加記を読むのも好き。
競プロ合宿は他のオンサイトに比べて参加のハードルが低い（予選があったりするわけではない）ので、普段会えないようないろんな人と知り合いになれるのも良い点だと思っています。

運営でわからない点があったら気軽に聞いてもらっていいので、ぜひ競プロ合宿やりましょう！！応援します！！

*1:会津大学競技プログラミング部によると、2012年から毎年開催していて歴史がありますね

*2:昔は他の大学だったらしいです

*3:もともと RUPC / ACPC は ICPC 対策の色が強いので

*4:新しい合宿を開催する場合は、いきなり日時のメールを送るんじゃなくて、この時期に開催を考えているんですけど…みたいな連絡を事前にするべきだと思う（しらんけど

*5:RUPCでは懇親会が大人数の予約になるので、1週間前までに人数を確定して連絡してくれみたいなのをお店から言われます。

*6:一番怖いのが同時接続に耐えられるかなんですが、事前の接続チェックで70台を一気につなぐことは無理なので

*7: RUPC や ACPC の Day3 は朝が早いので遅刻する人がいる

競プロで Σi*f(i) を求める問題

競技プログラミング

競プロで Σi*f(i) （ Σi/f(i) でもよい）を求める問題で、f(i)のとる値が少ない場合、「f(i)の値ごとにiの総和を求めてからf(i)をかけて、それらをすべて足す」というテクを使えばよいという知見を得た。

最近解いた問題でいうと、yukicoder No.737 PopCount（No.737 PopCount - yukicoder） と ABC020 D LCM Rush（D - LCM Rush） はこの考え方を使うと解ける。

PopCount の桁DP解法は popcount(i) の値が j になるような i の総和を桁DPで求めて j をかけるということをしてる。
（参考：http://kmjp.hatenablog.jp/entry/2018/09/28/0900）

LCM Rush は Σlcm(i,K) = K Σi/gcd(i,K) という言い換えをしたあと、Σi/gcd(i,K) を求めるところで、 gcd(i,K) の値が j になるような i の総和を包除原理を使って求めて j で割るということをしてる。
（参考：AtCoder Beginner Contest 020 D: LCM Rush - hogecoder）

RUPC2019（立命合宿）参加記

競技プログラミング 参加記

3/5(火)から3/7(木)に行われたRUPC2019（立命館大学競技プログラミング合宿2019 : ATND）に参加しました。

Day0

今年は前泊をしていたので、同じく前泊していた北大の人とまぜそばを食べました。


Day1 立命館大学セット

運営なので受付をしていました。
自己紹介フェーズでネタに走っている人がいて面白かったです。
チーム決めは今回から自動でいい感じにやってくれるアプリケーション（Competitive Programming Team Maker）を使うことにしました。結構良かったと思います。tsutajさんありがとうございます。


コンテストは3時間7問のセットでした。
去年のRUPCでは風船配りがなかったんですが、今年はぜひともしたいという気持ちになったのでしました。最初30分くらいのABの風船を配るフェーズがバタバタしていたのでつらかったです。
すぐにACが量産されないように、次からはAやBの難易度を上げたい気持ちになりました。

FGが防衛問題になっていたんですが、オンサイトでも2時間くらいで全完が出てしまいました。（といいつつ、ランダムではなく事前にチームを組んでいた強いところだったので、セットの難易度は悪くなかったんじゃないかと思っています）



コンテスト後の解説はC問題を担当しました（後で何度も間違えられたんですが、原案ではないです）。自分もC問題の原案を初めて聞いたときはぼっちオセロで実験したなあと昔を思い出しながらしゃべっていました。

懇親会はいつもの学内のところでやっていました。デザートがあったのは初めてな気がする。
いいセットだったといろんな人に言ってもらえて嬉しかったです。
いつもの勢とばかり懇親していたのでもう少しいろんな人と話せばよかったなあと今になって思います。


Day2 会津大学セット

Day2は事前にチームを組んでいたので、はい。

以下時系列がちょっとあやしいかも。

実装が嫌いなので考察しかしませんと宣言して、はじめはAとBをtsutajさんとえびちゃんに任せてCを読むことに。Aがすぐに通ったので、Cの問題概要をtsutajさんに伝えると、配置の9!通りを全探索すればいいと言われて、それぞれで文字列をなめてコストを求めるのは時間がかかるので、任意の2つの数字間の移動を何回行うかを前計算しておくといいって伝えたら実装してくれました。Bがつらそうだったので、Cの実装の間にBの解法をえびちゃんと考察すると、割り算をするだけだったのでえびちゃんに実装を任せるとpythonで書いてくれました。
順位表をみるとGが結構解かれていたけど、ちょっと考えたくらいだとわからなかったのでDEを考察しはじめる。DはtsutajさんがDPでできそうと言ったので任せる。Eは4近傍ではなく8近傍の移動を遷移として最短経路を求めると良さそうとえびちゃんに伝えると実装してくれる。DバグったみたいだったのでえびちゃんがEを実装する間にtsutajさんとHを考えようとすると、すぐにtsutajさんが燃やす埋めるで解けると言い始めたので、プロか？ってなった*1。DのバグがわかってACして、Eも考察漏れがあったのを直してACしたので、tsutajさんにHの実装をたのむ。
Gはよくわからなくて、Fの幾何も無理そうだったのでI以降に目を通すことにする。HがACしたあと、えびちゃんとtsutajさんがGを考察すると解けたっぽいので実装してもらうとACした。
あとは、
I：えびちゃんが実験してた。あと、dからkを復元するときに、復元できる数は区間で表せそうとかなって、-1判定は難しくないのでは？とかなる
J：なんか無理そう。
K：AとBを決め打ちすると、それぞれが近づく場合は面倒だけど、遠ざかる場合はあとは独立に考えられるよねというところまでは考察できる。
L：数学ができないのでつらいなあと思っているとえびちゃんがいっぱい頑張ってくれた（原始根？とかよくわからないんですが、惜しいところまでいったみたい？（よくわかってない
M：答えを決めるとXが一意に定まるので、答えを二分探索してSAをしてうしろにあるXから被らないように貪欲に3つとってきたいんですが、具体的な方法がわからずひるど
みたいなかんじだったので、Iの解法を生やして実装したらサンプルが通らなくて嘘って気づいてえーんってなってるうちにコンテストが終わりました。

コンテスト後は大学から懇親会の会場まで歩きました。雨が降ってて険しかった。
懇親会では即興で作問してみんなに解いてもらう会みたいなのをしていたのを見ていて、おもしろかったです。ビールにガリガリ君を入れて飲んでいた甜菜がいてウケた。


いま気づいたけどこのツイートの画像の背景にメイド服がある…？
いつもの勢とばかり懇親していたのでもう少しいろんな人と(ry

懇親会後はゲーセンに行きました。たのしかったです。

Day3 北海道大学セット

集合時間が日に日に早くなっていくことで有名な会津合宿・立命合宿なので、朝がつらいです。

Day3も事前にチームを組んでいたので、はい。


参加者でAtCoderレート1位のびーとくんがいればこわくない！wって気持ちで。

戦略はびーとくんが後半を解くので、せいかちゃんと一緒に前を埋めるって感じでした。
順当にレート順で自分がAを担当してBをせいかちゃんが担当することになりました。

コンテストが始まったのでAを実装すると思っていたより面倒でつらい気持ちになりました*2。AC。せいかちゃんがBを実装していて、自分がCを読んでいたらびーとくんがいきなりEわかったとか言い始めて怖かったです（プロすぎでは？）。
せいかちゃんとびーとくんが交互に(?)実装している間、Cを考察する。Cは最初、今までに宣言した数よりも小さい数しか宣言できないって誤読していてサンプル意味不明か？ってなってた（申し訳なさ）。いろいろあって、BとEが通ったあと、最大値は 約数の個数-1 で最小値は 素因数の個数 であることがわかったので実装しました。その間せいかちゃんがD、びーとくんがFを考察していて、CがACしたあとDの考察に加わる。Dは区間ごとに損失がiであるような個数をしゃくとりっぽく(?)求めてあげるといいねってなって、書いてサンプルを試すとあわなくて悲しい気持ちになりました。
びーとくんのFの考察をきくと、赤と黒の間の辺の数え上げ方法がわからないってなってるみたいで、3人*3で少し考えると片方の使わない数を決め打ちして包除ぽいことがわかる。
Dをデバッグしていると、一番最初の区間だけは任意の長さの矢について区間の長さの数だけ損失が起こることがわかったので、それを直すとAC。びーとくんもそのあとFを通す。すごい。

3人でGの考察をするとDPであることがわかるんだけど、閉路検出のためには状態をたくさん持つ必要があって、正気か？みたいな空気になる。「まああと1時間あるのでがんばりましょう（主に実装するびーとくんが）」ということで、自分とせいかちゃんが一緒に遷移を考えながら、びーとくんが7次元DP（異常）を実装していく。実装が終わってサンプルを試すと1つめは合うのに2つめはあわなくて、3人でデバッグをしていると、実は閉路検出をするときにはもっと状態が必要で、サンプル1ではそれがなくてもうまくいくみたいで、うく。びーとくんが11次元DP（やばい）に直してサンプルを試しても合わなくて、つらい気持ちになりながらデバッグを再開すると、添字ミスがあったみたいでAC。
15分残して全完です！！

オンサイト1位で、オンサイト2位のBurningkotatsuが終了までに全完するとペナで負けるなあとか全体1位のrickythetaさんはGみたいなのすきそうとかいう話をする。
その後は全完チームがでないままコンテストが終了し、オンサイト優勝！！

その後の解説では、ほむ愛してるチームがtsutajさんが解説する問題でFAをとって てんほむ をしていたりして面白かった。

そして、tsutajさんが閉会のあいさつをして、RUPC2019は無事終了しました。とっても楽しかったです。
参加者のみなさんが、RUPC2019を楽しんでくれたみたいで、運営としても嬉しいです。
参加者のみなさん、会津大学・北海道大学のみなさん、ありがとうございました。

*1:Day1で燃やす埋めるをずっと考えていたらしい

*2:制約をちゃんと読んでいなくて、入力がuniqueではないと思っていた

*3:3人といいつつ、ほぼびーとくんとせいかちゃん

Codeforces Round #540 Div.3 F1: Tree Cutting (Easy Version)

競技プログラミング Codeforces

Problem - F1 - Codeforces

問題概要

N 頂点からなる木が与えられ、各頂点は赤・青のどちらかで塗られているか、何も塗られていないかのいずれかである。

木の辺を 1 つだけ取り除き、同じ連結成分内には色が高々 1 種類まで登場するようにしたい。これを達成できる辺の取り除き方は何通り存在するか？

制約

2 \le N \le 3 \times 10^5
木には赤の頂点と青の頂点がそれぞれ1つ以上存在する

解法

まず、木に存在する全ての赤を含む最小の連結成分と、木に存在する全ての青を含む最小の連結成分を作り、作った連結成分の頂点は赤や青に変えてしまいます。これは帰りがけdfsで、自分の子孫に赤/青の頂点があるか？を調べながら色ぬりをしてあげるとよいです。
f:id:wk1080id:20190303011849p:plain
このとき、赤の連結成分と青の連結成分の両方に含まれる頂点が存在した場合、答えとなるような辺は存在しないので、この時点で 0 を出力してプログラムを終了します。

赤と青の連結成分がそれぞれ 1 つになったあと、答えとなる辺を探索します。
赤の連結成分と青の連結成分を繋ぐパスは必ず 1 つだけ存在し、そのパスに含まれる辺が問題の条件をみたす辺になるので、パスを探してその長さを出力します。

まず、与えられる辺を順に見ていきます。

辺に繋がっている2つの頂点が同じ色の場合は、その辺は求めるパスに含まれていないことが明らかなので何もしません。2つの頂点がどちらも塗られていない場合も何もしません（この辺が求めるパスに含まれているケースも存在しますが、そのときは求めるパスの長さが 3 以上であり、この辺で探索しなくても良く、別の辺のときに求めるパスであるかを判定します）。

そうでない場合で、2つの頂点が赤と青の場合は、この辺がパスになるので 1 が答えになります。

上のどちらでもない場合は、この辺が求めるパスに含まれているかを探索します。片方の頂点が赤でもう片方の頂点は塗られていない頂点の場合、色が塗られていない頂点から赤の頂点とは反対方向に、青の頂点が見つかるまで探索します。ここで、青の頂点が見つかれば、最初の赤の頂点から見つけた青の頂点までのパスが求めるパスなので、そのパスの長さを出力します。
もし見つからなければ、この辺は求めるパスに含まれる辺ではないことがわかるので、別の辺を探索します。

「今見ている辺が求めるパスに含まれているか？」を調べる回数は、与えられる木によっては多くなることがありますが、全体でそれぞれの辺は高々2回ずつしか見ないので、辺に繋がっている2つの頂点の色が違うときに毎回調べても O(N) になります。


Submission #50535438 - Codeforces

技術室奥プログラミングコンテスト #3 E - デフレゲーム

競技プログラミング AtCoder

E - デフレゲーム

問題概要

N 面のサイコロがあり、前に出た面がもう一度出るまでサイコロを振り続ける。
前に出た面がもう一度出るまでの出た目の総和の期待値を求めよ。
1 \le N \le 5 \times 10^5

解法

期待値の線型性より
\displaystyle \sum_{i=1}^N （サイコロを i 回振ったときの目の総和） \times （ i+1 回目で初めて目が重複する確率）
を求めればよいことがわかる。

サイコロを i 回振ったときの目の総和は、サイコロを i 回振ったときの目の総和の期待値を考えると良くて、
サイコロを1回振ったときの目の期待値が \frac{N+1}{2} なので、サイコロを i 回振ったときの目の総和の期待値は \frac{N+1}{2} \times i となる。

また、 i+1 回目で初めて目が重複する確率は、初めの i 回は目が重複せず、 i+1 回目にいままで出た i 個の目のうちどれかが出ればいいので
\frac{N}{N} \times \dots \times \frac{N-i+1}{N} \times \frac{i}{N} = \frac{_{N} P _{i}}{N^i} \times \frac{i}{N}
になる。
よってこれらの積の和が答えとなる。

Submission #4013511 - 技術室奥プログラミングコンテスト #3