algoNote

プログラミング関連

Google Code Jam 2017 Round1B A.Steed 2: Cruise Control

A問題のsmallとlargeだけ通して寝落ちしてました。。

A.Steed 2: Cruise Control

問題概要

Dashboard - Round 1B 2017 - Google Code Jam

アニーさんは馬に乗って初め地点 {0} にいて、距離 {D} の地点を目指して直線の道を進む。 道には {N} 頭の馬 {H_i} がいて、それぞれは初め地点 {K_i} にいて最高速度は {S_i} である。 各馬は前の馬に追いついたらそれ以降はその馬と同じスピードで走る。 アニーさんの乗っている馬が減速せずに一定のスピードで進む(他の馬に追いついて減速するイベントが起こらないように進む)とき 距離 {D} の地点に到達できる最短の時間を求めよ。

制約(large)

  • {1 \leq N \leq 1000}
  • {0 \lt K_i \lt D \leq 10^{9}}
  • {1 \leq S_i \leq 10000}
  • {K_i \neq K_i (i \neq j)}
続きを読む

Codeforces Round #380 Div2 C.Road to Chinema

codeforces.com

問題概要

$n$台の車についてコスト($c_i$)と燃料の容量($v_i$)が与えられる。
$s$kmを$t$分以内に走ることの出来る車の中でコストの最小値を求めたい。
ただし、途中$k$箇所($g_i$km地点)では燃料の補給が自由に行える。(何回でも)
また、いずれの車も次の2つのモードがあり自由に切り替えて走ることが出来る。

  • normalモード : 1kmを2分、燃料1L消費
  • acceleratedモード : 1kmを1分、燃料2L消費

制約

  • $ 1 \leq n \leq 2 \cdot 10^{5} $
  • $ 1 \leq k \leq 2 \cdot 10^{5} $
  • $ 1 \leq s \leq 10^{9} $
  • $ 1 \leq t \leq 2 \cdot 10^{9} $
  • $ 1 \leq c_i,v_i \leq 10^{9} $
続きを読む

ブログに競プロのレーティングを表示するようにした

AtCoderCodeforces・TopCoderSRMのレーティングを自動で取得して色付きで表示するスクリプト(javascript)を書きました。

※追記(2017/06/17)
YQLの仕様変更によってAtCoderレーティングが取得できなくなっていたようです。
アルクカ(id:arukuka)さんより解決策を頂いたので修正しました。

YQL で html を読み込む方法が変わった(html table is no longer supported.) - arukukaの日記

これ

AtCoder : loading
Codeforces : loading
TopCoder SRM : loading

AtCoder handle :
Codeforces handle :
TopCoder handle :


機能
動作確認済みブラウザ

(このブラウザだと動かないとかがあれば是非教えてください)

続きを読む

No.437 cwwゲーム

本番では解けずに解説を見て解きました。

初めてbitDPを使う問題に当たりました。

問題

No.437 cwwゲーム - yukicoder

続きを読む

デバッグ用のマクロ(C++)を工夫する

僕は競プロをやるときにいわゆるprintfデバッグをよくするのですが、その時にマクロが大活躍します。

普段使っているdump(x)

#define dump(x) cerr<<#x<<"="<<x<<endl

#xで変数名を文字列として扱えるという機能です。 このマクロがあるとdump(a)やdump(str)で変数aや文字列strの内容を分かりやすく表示できます。

これはこれで簡潔でよいのですが複数の値を並べて確認したいときは少し不便です。 例えば dump(a,b,c) で "a=0, b=1, c=2" のように出来れば便利そうです。

続きを読む