2018-02-18

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追いコン

2018-02-17

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

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

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

1日目

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

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

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

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

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

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

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

らめーん pic.twitter.com/iHFGos77Yy
— りかっち (@wk1080id) 2018年2月10日

部屋に戻ったら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なので苦でもない

2018-02-17

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)

2018-02-13

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

2018-02-11

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-

2018-02-11

ABC034 D 食塩水

競技プログラミング AtCoder

D - 食塩水

問題概要

$N$ 個の食塩水があり、 $i$ 番目の食塩水は $w_i$ グラムで濃度が $p_i \%$ である。
この中から $K$ 個選んで混ぜるときの濃度の最大値を求めよ。

制約
$1 \le N, K \le 1000$
$0 \le w_i \le 10^9$

解法

濃度が $T \%$ の食塩水を作れるかで二分探索していく。
それぞれの食塩水について、濃度を $T \%$ にするために必要な水の量（または、濃度を $T \%$ にするために取り除いても良い水の量）を求める。
食塩水を適切に $K$ 個選んだときに、
（濃度を $T \%$ にするために必要な水の量の合計） $\le$ （濃度を $T \%$ にするために取り除いても良い水の量の合計）
となっていれば、濃度が $T \%$ の食塩水を作ることができる。

Submission #2083176 - AtCoder Beginner Contest 034

2018-02-05

CODE FESTIVAL 2016 Grand Final A 1D Matching

競技プログラミング AtCoder

A - 1D Matching

問題概要

一次元の世界に $N$ 個のパソコンと $N$ 個の電源がある。 $i$ 番目のパソコンの座標は $a_i$ であり、 $i$ 番目の電源の座標は $b_i$ である。
それぞれの電源は一つのパソコンにのみつなぐことができるとき、ケーブルの長さの合計を最小化する場合の数を $10^9+7$ で割ったあまりを答えよ。

制約
$1 \le N \le 10^5$
$0 \le a_i , b_i \le 10^9$

解法

前から順に計算していくことができる。が、証明が難しいので他の人のブログを参考にしてください（最悪）

CODE FESTIVAL 2016 Grand Final: A - 1D Matching · うさぎ小屋
 CODE FESTIVAL 2016 Grand Final A - 1D Matching - ferinの競プロ帳

未割り当てのパソコンが $A$ 個の状態で電源を見ているとき、その電源につなぐことができるパソコンの数は $A$ 個ある。よって答えに $A$ を掛けて、未割り当てのパソコンの数を1減らす。また、電源を見ているときに、未割り当てのパソコンがひとつもない場合は、未割り当ての電源の数を1増やす。（この操作はパソコンと電源が入れ替わっても同じ）

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

足跡-sokuseki-

りかの日進月歩の記録

TPC追いコン A 不完全迷路

問題概要

TLE解法

解法

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

1日目

2日目

CODE FESTIVAL 2017 Final C Time Gap

問題概要

解法

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

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

問題概要

TLE解法

解法

ABC034 D 食塩水

問題概要

解法

CODE FESTIVAL 2016 Grand Final A 1D Matching

問題概要

解法