足跡-sokuseki-

りかの日進月歩の記録

CODE FESTIVAL 2016 Grand Final B Inscribed Bicycle

競技プログラミング AtCoder

B - Inscribed Bicycle

幾何。

問題概要

三角形の頂点が与えられる。
三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。

制約
0 \le x_i, y_i \le 1000


解法

まず、三角形の内部に半径 x の円がかけるとはどういうことかを考えてみる。
円の中心と三角形の辺の距離が x 以上であれば、半径 x の円がかける。
つまり、三角形の内部で、各辺から x 以上離れた場所(図の緑の三角形)に円の中心があれば、その円の円周は三角形の辺上か三角形の内部にあることがわかる。
f:id:wk1080id:20180220230806p:plain


次に、三角形の内部に半径 x の円が重ならないように2つかけるとはどういうことかを考える。
それぞれの円の中心と三角形の辺の距離が x 以上であり、2つの円の中心の距離が 2x 以上であれば、半径 x の円が重ならないように2つかける。
つまり、三角形の内部で、各辺から x 以上離れた場所(図の緑の三角形)にそれぞれの円の中心があり、2つの円の中心間の距離が 2x 以上ならば、その2円の円周は三角形の辺上か三角形の内部にあり、かつ2円は重ならないことがわかる。
f:id:wk1080id:20180220230751p:plain


ここで、元の三角形の内接円の半径を r とすると、元の三角形の内部で各辺から x 以上離れた点の集合からなる三角形の内接円の半径は r - x である。よって、2つの三角形の相似比は r : r - x 。

2つの円の中心間の距離を 2x 以上にするためには、「元の三角形の内部で各辺から x 以上離れた点からなる三角形」の少なくとも一辺が 2x 以上であればよい。つまり、与えられた三角形の3辺のうち最も長い辺の長さを A とすると、内部の三角形の最も長い辺の長さは A \times \frac{r - x}{r} になるので、これが 2x 以上ならば、与えられた三角形の内部に半径 x の円が重ならないように2つかける。


よって、半径の長さ x を二分探索で決め打ちして、それぞれの x について、三角形の内部に半径 x の円が重ならないように2つかけるかどうかを判定すればよい。

Submission #2118930 - CODE FESTIVAL 2016 Grand Final(Parallel)

ABC036 D 塗り絵

競技プログラミング AtCoder

D - 塗り絵

はじめての木DPです。

問題概要

N 頂点の木が与えられる。
両端の頂点が黒で塗られるような辺がないように、頂点を白または黒でぬるとき、塗り方の通り数を 10^9 + 7 で割ったあまりを答えよ。

制約
1 \le N \le 10^5


解法

漸化式を立てて木の上でDPをしましょう。

f( x ) := 頂点 x を親とする部分木に含まれる頂点をすべて白または黒で塗り、両端が黒で塗られた辺が存在しないようにする方法の通り数。
g( x ) := f( x ) と同じ。ただし、頂点 x は必ず白で塗らなければならない。

とすると、以下の2つの漸化式を作れる(ただし、 y_1 , y_2 , … , y_k は x の子とする)。

  • f( x ) = g( x ) + g( y_1 ) \times g( y_2 ) \times … \times g( y_k )
  • g( x ) = f( y_1 ) \times f( y_2 ) \times … \times f( y_k)

なぜこの漸化式がつくれるのかは、次のサイトがわかりやすいです、これで理解しました。
漸化式を立てて「tree DP問題」を解く D - 塗り絵 - マツシタケイタの技術ブログ(勉強中)

あとは、木の葉から順番に f( x ) と g( x ) を埋めていくことで、 O(N) で求められる。
葉から根にむかって順番に求めるには、dfsをつかって根まで行き、帰りがけに計算すればよい。

Submission #2117216 - AtCoder Beginner Contest 036

TPC追いコン A 不完全迷路

競技プログラミング AtCoder

A - 不完全迷路

問題概要

高さ H 幅 W の迷路が与えられる。
壁のマスを1マスのみ道のマスに変えたとき、スタートのマスからゴールのマスへの最短経路長が最長となるようにしたい。
そのときのスタートからゴールまでの最短経路長を求めよ。

制約
1 \le H, W \le 298


TLE解法

それぞれの壁のマスに対し、そのマスを道に変えたときのスタートからゴールまでの最短経路をすべて求めて、その最大値を出力する。
計算量は O((HW)^2) になる。

Submission #2039448 - TPC追いコン

解法

ある壁のマスを道に変えたとき、そのマスを通るスタートからゴールまでの最短経路長は、
（そのマスの上下左右どれかのマスの、スタートからの最短経路長） + （そのマスの上下左右どれかのマスの、ゴールからの最短経路長） + 2
であることがわかる。
f:id:wk1080id:20180218192951p:plain
また、変更するマスは1つのみなので、「そのマスの上下左右どれかのマスの、スタートからの最短経路長」と「そのマスの上下左右どれかのマスの、ゴールからの最短経路長」は、与えられた迷路から求めることができる。

与えられた迷路の道のマスすべてについて、スタートからとゴールからの最短経路長を前計算しておき、それぞれの壁のマスに対し、そのマスを道に変えたときのスタートからゴールまでの最短経路を求めて、最大値を出力する。
この場合、計算量は O(HW) になる。

Submission #2107477 - TPC追いコン

立命館NAIST競プロ合宿参加記

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

2/10-11に立命館大学にて1泊2日の競プロ合宿を行いました。

 

1日目

昼に集合して、自己紹介からスタート。

きりんさん以外は面識があったので、NAISTの方々とはお久しぶりです〜みたいなノリだった。

 

その後、レートが水色未満の人はAOJ-ICPCのばちゃ、それ以外の人はこどふぉばちゃをしていた。

Dashboard - Codeforces Round #443 (Div. 2) - Codeforces

A問題は誤読してWAをだしつつもAC、B問題は条件が足りてなくてWAってた。C問題は読んだけどビット演算苦手だな〜と思って手をつけられず。（最悪か？

 

ばちゃ終了後は感想戦をして、あとはらてあさんとTwitterの話をしていた。

 

その後、学内の宿泊施設にチェックインして荷物を置いてから、やざてん先輩オススメの天天有というラーメン屋に行きました。おいしかった。

 

 

部屋に戻ったら9時前だったので、NAIST部屋にお邪魔してみんぷろオンサイトをした。

「みんなのプロコン 2018」 - 「みんなのプロコン 2018」 | AtCoder

 

開始早々ABの2完して、Cをずっと考えてたけど嘘解法しか浮かばず。2人が最適に行動するの苦手。

コンテストが終わってから感想戦をした。みんなCに詰まってたみたい。

 

そのあとは部屋に戻って、シャワー行ったりTwitterしたりしてた。

Twitter見てたら、らてあさんが徘徊してるみたいだったから、参戦して575探索とかした。

 

2日目 

1日目と同じ部屋で同じようにばちゃした。

Dashboard - Codeforces Round #326 (Div. 2) - Codeforces

 A問題は誤読してWAをだしつつもAC、B問題は素因数分解して各素数かけたら合わないな〜ってなってた。C問題はビットっぽい気配がして読むのをやめた。（最悪か？（あれデジャヴか？

 

感想戦を少しして、コンビニに昼ごはんを買いに行き、快適な部屋を求めて部室棟へ移動。

 

昼ごはんを食べてからAPCばちゃをしました。

https://not-522.appspot.com/contest/6395698329157632

Aはなんか勘違いしてて2WAした。Bは意味不明。

ということで1完で終わった。かなしいね。頭がない。

終わってからBを通した。むずすぎか？

 

その日は19時から第2回 RCO日本橋ハーフマラソン 予選 - 第2回 RCO日本橋ハーフマラソン 予選 | AtCoderがあったので、早めに解散した。

解散の前にみんなでおはなしして、次は夏ごろに合宿できたらいいねってことになった。

 

また合宿やるぞ！！

 

 

一応立案者で準備とかしたんですが、やったのは

  • 参加希望者の予定を聞いて日程を決める
  • 学内宿泊施設を予約する
  • 活動場所を確保する

だけなのでそんな手間でもなかったです、合宿の楽しさがINFなので苦でもない

CODE FESTIVAL 2017 Final C Time Gap

競技プログラミング AtCoder

C - Time Gap

問題概要

N 人の都市について、高橋君の都市との時差が与えられる。
高橋君を含めた N+1 人の都市のうち、すべての2つ都市の時差の最小値を s としたときの、 s の最大値を求めよ。

制約
1 \le N \le 50


解法

num[ i ] := 高橋君との時差が i 時間の人数
とする。

num[ i ] > 3 となる i が存在するとき、高橋君との時差が i 時間の人の中で、互いの時差が0時間となる2人が必ず存在することがわかる。よってその場合の答えは0となる。

そうでないとき、 高橋君の都市が0時であるとする。
num[ i ] = 2 となる i については、 i 時の都市と 24 - i 時の都市が存在することが確定する（時差を最大にしたいので2人の時差を0時間にしたくない）。

num[ i ] = 1 となる i については、 i 時の都市か 24 - i 時の都市かがわからないので2通りある。
よって、num[ i ] = 1 となる i について全探索する。
このような i の数を a とすると、 a は高々12であり、すべての場合に対しそれぞれの都市間の時差を調べるので、この全探索にかかる計算量は O(a^2 \times 2^a) となる。


Submission #2099469 - CODE FESTIVAL 2017 Final (Parallel)

[追記]
解が13個しかないので、決めうちしてから2-SATで殴ることもできます。
Submission #2150954 - CODE FESTIVAL 2017 Final (Parallel)

C#でプログラミングしてみた

Unityとかやってみたいなあと思ってC#の勉強を始めました。


本気で開発するならIDEを使う必要があるんですが、簡単なC#プログラミングしかしない予定(?)なのでとりあえず端末上でコンパイルして実行できればいいか〜みたいな気持ちです。

ということで、次のコマンドでC#のコンパイラ(Mono*1 )をインストールします。

$ brew install mono

インストールが終わったらコードを書きます。

using System;

class HelloWorld
{
        static public void Main ()
        {
                Console.WriteLine("Hello World");
        }

}

名前はなんか適当にhello.csとかにしておく。拡張子は「.cs」です。

保存できたらコンパイルします。次のコマンドでコンパイルするとhello.exeという実行ファイルができます。

$ mcs hello.cs

実行します。

$ mono hello.exe

実行すると端末上に「Hello World」と表示されます。


作成したソースコードをhttp://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A&lang=jpに投げます。

ACになります。

めでたしめでたし。

*1:Mono Basics | Mono

COLOCON -Colopl programming contest 2018-　D すぬけそだて――トレーニング――

競技プログラミング AtCoder

D - すぬけそだて――トレーニング――

問題概要

スタミナの上限が X で、 スタミナを全て消費する時間の候補が N 個ある。
時刻 0 のときにスタミナが X で、 1 単位時間にスタミナが 1 回復するとき、 i (1 <= i <= N ) 回スタミナを消費する場合の消費したスタミナの合計の最大値を各 i について求めよ。

制約
1 \le N \le 5000
1 \le X \le 10^9
1 \le T_i \le 10^9

TLE解法

dp[ i ][ j ]:= 最後に起動したのが i 番目の候補で、今までに j 回起動したときの消費したスタミナの最大値
とすると、遷移が O(N) かかるので、計算量は合計で O(N^3) になる。

Submission #2074687 - COLOCON -Colopl programming contest 2018-

解法

最大値を求めるDPは最大値になりうる遷移以外は無駄なので、必要な遷移のみを考えることによって高速化する。

スタミナを消費する回数がたくさんある場合、上限までスタミナが回復してからスタミナを消費すると、上限まで回復したあとから消費するまでにかかる時間ぶん、スタミナを無駄にしてしまう。
また、スタミナを消費する回数が少ない場合、上限まで回復するまで待った方が、上限まで回復する前にスタミナを消費するより、多くのスタミナを消費できる。
よって、スタミナを消費する回数によって、2通りの遷移が考えられ、

  • スタミナが上限まで回復する1つ手前の候補
  • スタミナが上限まで回復した直後の候補

だけを考えれば良い。
これで遷移にかかる計算量が O(1) になるので、全体で O(N^2) となり間に合う。

Submission #2075190 - COLOCON -Colopl programming contest 2018-