おはようございます。しほみんです。
先々週やったARC相当の企業コンテスト振り返ります。普通に考えたらまあできるなって感じだったので悔しいですね....
（お知らせ）
水曜と金曜日の更新は不定期にします。
あんまり記事たくさん書いてもしょうがないので、
平日は競プロの話、休日は投資、節約の話でもやろうかなって思います。
では本題に戻ります。
自分の競技プログラミングへのスタンスです。
＜自分のプログラミング力＞
・レートは800程度になりました。緑と茶をうろちょろしています。
・C#でクラスとかつかってアプリケーションは作れます。
＜Atcoderでのスタンス＞
・アルゴリズムについて問題でいろいろ学んでいる。第3回PAST70点で中級取得。
・基本的に本番でやっている。現在48回参加、ほぼ1年。
・目標はABCのD問題までをちゃんと短時間で解けるようにすること。パフォーマンスは1000以上、できれば水色（1200以上）は欲しい。
今回はAB、7分でした。C問題解きたかったですね....（問題自体理解するのに1時間以上使っていた）。早く解けたのでパフォーマンスは1103で、レートも 855→883で上がりました。
よく理解したら割と単純だったので今度はちゃんと解きたいですね。
今回はC問題まで振り返ります。前回に引き続き考察をメインに書きます。
コードは別に上げます。
問題A
高橋君がH1時M1分に起きて、H2時M2分に寝ます。
起きている時間のうちK分間連続で勉強することにしました。
勉強の開始時間として使えるのは何分間でしょうか？
まあ起きた瞬間から、寝る時間のＫ分前までの時間ならいつでも初めて良いです。
よって、（眠った時間）－（K分）ー（起きた時間）になります。
このとき、時間ですが、全部分にしてしまうと楽です。0時0分を基準にして、それぞれ起きた時間、眠った時間が何分後かと見据えて、あとはK分引くだけです。
その時間は、(H2-H1)*60 +(M2-M1) - Kです。
問題B
PとDからなる文字列Sがあります。
PDとDの個数の和を博士・PD指数と呼びます。
今、P,D,?でできる文字列Tがあります。
Tに含まれる?をPかDに置き換えて、博士・PD指数を最大化した文字列を答えなさい。
ぱっとみわかりにくいですが、追加できるのはPかDなので,
少しPとDについて考えてみます。
1文字の時
Pだと0,Dだと1
2文字の時
PDだと2, DDだと2, PPだと0,DPだと1です。
上のことを考えると、?が1つの時、前後がPでもDでも、Dを追加すれば、1つ増えます。Pだと逆に増えないので選択肢にはないです。
?が2つあると、DDとしておけば特に問題ないです。PDだと逆に問題です。
もし前にPがあれば、DDなら、PDDで3つですが、PPDだと2つなので少ないです。
結局どのみちDを入れてしまえば、数が最大化できます。
なので、?にDを入れれば答えになります。
C問題
二分木について考えます。それぞれ葉の数が与えられます。このとき、考えられる最大の要素数を求めなさい。
問題は単純ですが、まず何言っているかわからない....
ということでわからんってことで1時間以上考え込んでた....
ようやく理解したのですが、要するに葉の個数によって、それ以外の要素がそれぞれ同できるか考えればよいのです。
そこで大事な要素なのですが、これ実は葉の数の総和と、頭からの分離方法で、一意的に決まります。
・根からの深さをd、一番深いところをNとすると
d番目のありうる要素数の最大はd+1からNまでの葉の数の和です。
なぜなら要素がそれ以上あると分離してしまって葉にならないです。
例えば深さがdのとき要素が20個あるとして、d+1に15個で、ここが一番深いとすると、分岐しかできないのに要素が5個あまり（というか結局葉となって）破綻します。
・そして、頭から見ると分離できる最大の数は決まります。
d番目にありうる要素数の最大はd-1番目の要素の数からd-1番目の葉の数を引いたものを2倍すればよいのです。
なので、頭からとりあえず分離してみて、この下の葉の数の和より多くなったら、制限をかけていけばいいって感じです。（深さから見た和の数は記録しておくとo(1)で取り出せる）
あと、構成的にありえなくなる場合もあるので、それも省く必要があります。
特にn=0のときは根しかないので例外処理します。
それ以外は、d番目の葉の数が頭から考えられる数以上になったらアウトです。
最後の項だけこれが当てはまらないのは注意です。
最後に....
やっぱりARCコンテストもC問題までは解きたいところですね。問題がつかみにくくなっているので慣れもある気がします。もうちょっと精進します。
ではでは。
