2014-09-01から1ヶ月間の記事一覧
SRM 617 Div2 Easy n, 合成数であるx,yの組でx+y=nを満たすものを一つ エラトステネスの篩なりを使って合成数を見つける。 Med 在庫のうち、stale_limit日以上前に精算されたものを破棄 今日をi日とするとmorning[i]個以下の任意の数だけ生産 最大customers[…
SRM 618 Div2 Easy Aを入力するには1タップ、Zは26タップ、文字列が与えられる。全て入力するには何回タップすればいいか 数える Med 文字列が与えられる。同じ文字が連続してなくて、部分列がXYXYとならない文字列は"Likes" 4つ以上ある文字が存在すればダ…
SRM 619 Div2 Easy N人の社員のいる会社。0番目以外のi番目の社員にはsuperior[i]という上司がいる。各社員はひとつの部署を持っている。部署の中で同じ仕事をしている社員のいない部署の数はいくつか。 それぞれの部署に対して好ましい部署か調べる。 Med 1…
SRM 621 Div2 Easy 文字列が辞書順なのか短い順なのか両方なのかどちらでもないのか Med 配列に含まれる整数の和で作れない最小の整数。 何が作れるかをdpみたいに計算する Hard colorに含まれる全ての色をつくるのに必要な絵の具の数。２つの絵の具を混ぜる…
SRM 622 Div2 Easy Nに最も近いフィボナッチ数とNの差を求める。 フィボナッチ数を先に求めておけば、全探索でも十分に間に合う Med いくつかの大きさのものを2xの無限個ある箱に入れてく、ものは自分より大きい箱にしか入らない、ある箱は、その箱よりも小…
謝辞 面白い本を見分けるには - クソログ 上の記事に触発されて。100年以上立ってない本は読めないって面白いですよね。私はプログラミングやってるんで、100年以上たった本って言われるとユークリッド原論とか算術とかぐらいしかないんですよね。 自分が計…
SRM 623 Div2 Easy CatchTheBeatEasy 2dゲーム。(0,0)をスタート、x軸上を移動できる。1ずつ。N個のフルーツがY軸マイナス方向に向かってくる。全部取れるか フルーツのyが0の時にしか取れないのでyの昇順に取っていく。sortする。あとは現在の場所と時間を…
SRM 624 Div2 Easy costの中からk個選んだ時の最小コスト dpで解いた。自分で漸化式考えて、dpに落としたのは初めてです Med heightsの要素を1増やしていってM個の同じ要素作るには最低なんかインクリメントすればいいか 最初に思いついた方法では時間が足り…
SRM 626 Div2 Easy 数列aが与えられる。aの部分列の要素の和をすべて合計するといくつになるか 累積和を使った。 Med aとb、それぞれの数字までが書いてあるサイコロがある。aを持っているアリスが勝つための期待値でいいのかな 勝ったときの数字と勝った回…
特に書くこともないです。一緒に組んだのは後輩です。 1から3問目は、後輩にいろいろ教えながら通した。 4問目はWA出しすぎた。 5問目、方針は決まったけど例外吐いて、デバッグできなかったり 6問目、バグらせた。 4完。 visual studioとかどうやってデバッ…
Easy なんか四角を表示する。実装するだけ。 Med (0,0)から(x,y)まで移動したい。len[i]ずつ移動できる。(x,y)までたどり着けるか。 シュミレートとか必要なくて、計算するだけで解けるらしい。短すぎと長すぎがなければいいようです。 Hard 読んでない 結果…
SRM 626 Div2 Easy 数列aが与えられる。aの部分列の要素の和をすべて合計するといくつになるか 累積和を使った。 Med aとb、それぞれの数字までが書いてあるサイコロがある。aを持っているアリスが勝つための期待値でいいのかな 勝ったときの数字と勝った回…
SRM 627 Div2 Easy 棒がいくつか与えられる。その棒を使って何個正方形が作れるか。 数えるだけ。 Med 文字列が与えられる。違う文字を２つ選んで消してく。最後に必ず同じ文字が残る場合はhappy letter 同じ文字が半分より多いならhappy letter Hard 数列が…
SRM 627 Div2 Easy 棒がいくつか与えられる。その棒を使って何個正方形が作れるか。 数えるだけ。 Med 文字列が与えられる。違う文字を２つ選んで消してく。最後に必ず同じ文字が残る場合はhappy letter 同じ文字が半分より多いならhappy letter Hard 数列が…
SRM 628 Easy ビジョップを使って、最低何手で(r1, c1)から(r2, c2)にたどり着けるか？たどり着けない場合は-1を出力。 BFSで解いた。ビジョップの移動をシュミレートするだけ。 Med '(',')','[',']','{','}','X'からなる文字列が与えられる。Xはどの文字に…
SRM 629 Div2 Easy 地表に長方形の穴が開いた。長方形の板があるから、その板で穴を完全に防げるか。 板を回転させても構わない。 解けた。 Med N人の生徒が持ってる容器の大きさとほしいキャンディの重さが与えられる。キャンディは均一の密度のものしか作…
一セットずつやった。 SRM 630 Div2 Easy 文字が2つ連続していれば消す。最後に文字が残っているか 解けた。 Med k個の都市間の距離が等しくなることがあるkの最大値を求める。 バグらせた。 Hard SuffixArrayがわからない。ソース読んでもわからない Codefo…
問題 Formation 解く 最初簡単だろうと思って、貪欲法で解いたら、WA。 DPで解こうとするとMLEになる。 適当な人数になるまではCANにしとけばいいことに気づく。 cとaが小さくなるまでCANに割り振って、そこからDP,runtime error 数分悩む。1000 1000 3とか…
問題 Highway Express Bus 解法 拡張ダイクストラ法。初めて解いた。拡張グラフのダイクストラとかなんとか、 グラフを３次元方向に掘ってく 心臓に悪いコード typedef pair<int, int> pi; // 残りの割引券 現在の街 typedef pair<int, pi>P; // コスト pi struct edge{ int to,</int,></int,>…
