読者です 読者をやめる 読者になる 読者になる

競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

ABC#019

ABC

リアルタイムで解いた問題。
スタート時間が遅かったが何とか時間内に全完しました

- A問題「高橋君の年齢」

(http://abc019.contest.atcoder.jp/tasks/abc019_1)

問題概要:
コンテスト中は中央値という単語しか見えなかったので問題文を読んでいませんでした。
友達3人の中央値を自分の年齢として代用するという中々ユニークな問題です。

解法:
問答無用でソートして真ん中を取り出しました。

ソースコード:
https://abc019.contest.atcoder.jp/submissions/345500


- B問題「高橋君と文字列圧縮」

(http://abc019.contest.atcoder.jp/tasks/abc019_2)

問題概要:
ランレングス符号と呼ばれる文字列の圧縮方法ですね。同じ文字が続くケースの多い文字列では絶大な力を発揮します。
画像のピクセルデータに使われたりするそうです。

解法:
いったん配列に圧縮して格納し、文字列を全て走査したのち配列を文字列に変換して出力します。

ソースコード:
https://abc019.contest.atcoder.jp/submissions/345722


- C問題「高橋君と魔法の箱」

(http://abc019.contest.atcoder.jp/tasks/abc019_3)

問題概要:
魔法の箱(役に立つとは言っていない)の動作を理解する問題です。

解法:
xを入れたときと2xを入れたときに出てくる整数が一緒という文に注目します。
ある奇数kを入れたときとk*2^nを入れたときに出てくる数字が一緒ということになります。
したがって入力された数字を奇数になるまで2で割り続け、出てきた奇数の種類の個数を出力すればOKです。
なのですが、出てきた数字の種類のメモに配列を使ってしまうと、メモリ使用量がO(10^9)となってしまいMEになります。
ここで二分探索木が便利です。
数字の種類数自体は10^5程度なのでデータ数もその数だけ保持したいです。二分探索木は要素の追加に\log Nかつ同じ要素の重複ができないためうってつけです。
setに慣れていないためmapを使用しましたが多分どちらでもよさそう。
したがって計算量は\log N の追加がN回、2で割る回数が最大30回ぐらいなのでO(N(30+\log N))で十分間に合います。

ソースコード:
https://abc019.contest.atcoder.jp/submissions/345934


- D問題「高橋君と木の直径」

(http://abc019.contest.atcoder.jp/tasks/abc019_4)

問題概要:
木の直径(木の最も長い2頂点間のパス)を求める問題です。
ABCでは初めてのリアクティブ形式の問題なので焦りました。

解法:
貪欲法で解きました。割と直感で解いたのでうまく説明できないかもしれない()
頂点1,2をそれぞれA,BとしてA-Bのパスの長さを取得します。
次に頂点3をCとしてA-C,B-Cを取得し、A-B,A-C,B-Cの長いものをA,Bに置き換えます。

以下証明っぽいもの
・A-B-Cというつながり方をしていたとき
CをBに置き換えることで現時点での最長パスが保存できます。
仮にB-Dという長いパスがあったとしても、A-DまたはC-Dのほうが必ず長くなるのでBは切り捨ててよいとわかります。
・A-x-B,x-C(T字型)というつながり方をしていたとき
A-Cが一番長かったとしましょう。
仮に長いB-D,B-A-EというD,Eが存在しても
A-D,C-D,C-Eのほうが必ず長くなります。
C-Eのほうが長い理由はC-A>B-Aからくるものです。

ざっくりですが以上で証明終わりです。
今回やった方法は解説スライドのものと少し違うのですが多分やっていることはdouble-sweepと同じです。
書いてた時は逐次追加法をイメージしていました。
質問回数は2N-1です。
ソースコード:
https://abc019.contest.atcoder.jp/submissions/346565