Code Festival : B - 枕決め

問題:

http://code-festival-2014-morning-middle.contest.atcoder.jp/tasks/code_festival_morning_easy_d
m人の人がいる。それぞれの人は好みの枕の高さの範囲[xi,yi]が与えられる。
n個の枕がある。それぞれの枕の高さはh[i]で、これも与えられる。
枕は一人一つ使うものとして、最大で何人の人が枕を使うことが出来るか、人数を求めよ。

解法:

貪欲法で解ける。
まずは点と区間でソートする。
priority_queueを用意する(突っ込むものは区間で、ソート基準は右側の座標の小さい順)

点x[i]について、
1.その点を含むような区間をすべてpriority_queueに入れる。
2.priority_queueから区間を取り出し、もしそれがx[i]を含むものであったらx[i]はその区間とマッチング。そうでないならばpriority_queueから点を取り出し続ける。
3.マッチングの個数を出力

CF Round310 Div1 C : Case of Chocolate

問題

http://codeforces.com/problemset/problem/555/C
n×nのグリッド上にチョコレートがある。
直線:x+y=n+1上の点からスタートして上または左に食べ進んでいく。
すでに訪問済みの座標にくるまで直進していく。
座標と方向のクエリが与えられるので、各クエリごとに何個のチョコレートを食べることができるかを求める問題。

解法

(sx,sy)から上に進む場合を考える。
この時、今までのクエリの開始地点のx座標の中でsxより大きいものの中で最小の座標mxを求める。そのクエリq'が
・上方向のクエリだったら、xからmxの間にあるチョコレートに対するクエリは存在しないので、q'が進めた分 + mxとxとの距離 が食べられるチョコレートの数となる。
・左方向のクエリだったら、そのクエリの開始座標のy座標まで進める。
つまりq'を二分探索で求めれば良い。

AOJ埋め

簡単な問題をたくさん解いた。

2021 : 姫血液の問題。memo[ノード][冷凍残り時間]でdjikstra
1145 : ゲノム文字列の問題。構文解析. 長さがインデックスになるまで解凍する感じ。
1138 : 馬車チケットの問題。memo[ノード][持ってるチケット]でdijkstra
1140 : 掃除ロボットの問題。bfsで各汚れ間の距離を出して10!通り試す。
1136 : 折れ線を探す問題。回転したやつとかを全部探索するだけ。回転は虚数掛けると楽
1127 : 宇宙ステーションの問題。最小全域木やるだけ。
2399 : プライバシーを守る問題。やるだけ。
2019 : 姫が護衛を雇う問題。貪欲法。
1165 : 角角画伯の問題。やるだけ。
2151 : 姫が護衛を雇う問題。memo[ノード][残り予算]でdjikstra
2402 : 星間ダイクストラの問題。五角形にして星同士の距離やってdijkstra
2182 : Eleven Loverの問題。なめるだけ。
1189 : 素数洞窟の問題。メモ化探索。
1187 : ICPCのランキング付けの問題。プレディケート書いてソートするだけ。
2014 : WとBの柵の問題。やるだけ。
1335 : 漸化式立ててメモ化。漸化式考えるの楽しかった。
2007 : お釣りを渡す店員が親切な問題。持ってる金全部渡してみるというのがわかれば楽
2012 : 宇宙ヤシガニの問題。探索の順番。
1142 : 列車の文字列の問題。やるだけ。
1125 : できるだけ沢山木をとる問題。英語読むだけ。
1137 : ローマ数字の足し算の問題。YARUDAKE.

こんな問題がDとかに来てていいのかよ、って感じの問題が散見された。

AOJ 2182 : Eleven Lover

問題:

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2182

解法:

11の倍数は
偶数桁目の和 - 奇数桁目の和 ≡ 0 (mod 11)
で判定できる。
そこで、F[i][j] = 0からk桁目まで「先頭から足し引きを交互にして11を法としてjになる」ようなkの個数(k<=i)
とすれば良い。
ただし0-leadingは許さないので、string[i+1]='0'ならばF[i][j] = 0にする。

ソースコード:

https://gist.github.com/knewknowl/a31bbb3cc1a625a0989a

ARC 39 C:幼稚園児高橋君

問題

http://arc039.contest.atcoder.jp/tasks/arc039_c

解法

C[座標][i]=方向iに訪問済みマスが何個連続してるか
を持たせながら移動しつつ更新した。

C[移動 前][i番目のコマンドの向き]=歩いた距離
C[移動後][i番目のコマンドの逆の向き]=歩いた距離
C[移動後][向きj] = C[移動後+j][j]+1
みたいな感じで更新した。

AOJ 1164 : 締まっていこう

問題:

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1164

簡単にいうと板に釘がいくつか打ち付けられていて、あとヒモが通っているのでヒモをピンッってした時のヒモの長さを答える問題。

解法:

引っかかっている釘、その直前に引っかかった釘、どれだけ巻き付いているか(角度)をスタックに入れる。角度は符号つき角度[-π, π]で考える。

ヒモABがACに連続的に移動する時を考える。

ABからACに移動する時に次に引っかかる釘をKとする。(もしそのような釘がなければK=Cとする)

この時, ∠BAKとスタックの先頭の角度を比較し

・それらが異符号ならばスタックの先頭は外れるので、

B ← pre(A)(Aの直前の釘)とAを結んだ直線と直線BCとの交点

A ← pre(A)

としてスタックをpopする。

・それらが同符号ならばスタックの先頭は外れないので、三角形ABC内の釘を凸法みたいな感じで選んでいき、スタックに入れていく。

解けた時は最高に「ハイッ」てやつだった。

https://gist.github.com/knewknowl/88bec89ce563a6755719