2016-01-01から1年間の記事一覧
2015/11/22に競技プログラミングを始めてから丁度1年が経ったので、競技プログラミングをやるにあたって、何をしていたか等を記事としてまとめておきます。 (ためになる話は多分そこまでないです) この記事の流れ この記事は次のような構成になっておりま…
問題 問題のURLはこちらです。 No.409 ダイエット - yukicoder 考えたこと 動的計画法を使います。配列を次のように定義します。 日目にドーナツを食べた時の体重の変化量の最小値すると、その時の漸化式は、 なお、最初の行を簡単に説明すると、 (日目にド…
直線集合L={f_i(x)=a_ix+b_i}に対して、「Lへの直線f_k(x)=a_k x+b_kの追加」(以下、追加クエリ)と、「あるxに対し、Lの中で最小値(あるいは最大値)を取るような直線の値を求める」(以下、最小値クエリ)という2つのクエリを効率的に行うことが出来ます。
初めてのDiv1だ。゚(゚´ω`゚)゚。— satanic@C++ (@satanic0258) 2016年5月30日 今回は色々意外なことがあったので日記として書いておきます。 (この記事に解説は含まれないので予めご了承下さい) 私が前回参加したのはSRM688だった、ということで気づいたら2回分…
概要 の値を効率的に解きます。 使える状況 「をで割ったあまり」が欲しいときに、があまりにも大きいとその計算だけで時間がかかってしまうことがあります。そのような時には、この繰り返し自乗法を用いることで素早く求めることが出来ます。 説明 の値を求…
はじめてのSRM— satanic@C++ (@satanic0258) April 15, 2016競プロのカレンダーを見ていると、2016/04/16 00:00(日本時間)からSRMがあるということだったので、TopCoder SRMに初参戦してみました。 初参戦ということでレートは1200から始まり、Div2の問題を…
問題 問題のURLはこちらです。 No.22 括弧の対応 - yukicoder 考えたこと まず、入力された各括弧の深さを表す配列をいもす法を使って格納しておきます。いもす法に関しては、こちらの記事を参照してください。 satanic0258.hatenablog.comそして、調べる番…
累積和を用いて複数の要素の重なり・深さなどを計算します。
ある配列の任意の区間での部分和を求める。
ある複数の集合における和集合の要素の個数を共通部分に配慮して正しく計算する。
問題 問題のURLはこちらです。 No.21 平均の差 - yukicoder 考えたこと グループの数は以上であるため、「最大値と最小値の差」を求めれば良いですね。 グループの分け方としては、「最大値」「最小値」「余り」とします。以下の図を見たら明らかですね。 (…
問題 問題のURLはこちらです。 No.18 うーさー暗号 - yukicoder 考えたこと 個目の文字について、 文字を数値に変換する その数値から引く 数値を文字に変換する と行えばよさそうですね。 コード(C++) #85751 No.18 うーさー暗号 - yukicoder #include <iostream> #in</iostream>…
問題 問題のURLはこちらです。 No.5 数字のブロック - yukicoder 考えたこと 「をうまく組み合わせてちょうどになるように…!」って問題でも無いので、の小さい順にから引くたびにカウントしていき、がマイナスになった時点でループを終了しその時の個数を出…
問題 問題のURLはこちらです。 No.91 赤、緑、青の石 - yukicoder 考えたこと 「あることが成り立つときの最大値」を求めれば良いため、 アクセサリーを個作ることが出来るかどうかを調べる関数を作る。 の値で二分探索する。 とすることで答えを求めること…
ある条件を満たすものの最大値を求めます。 (ソートされた配列に対してある値を探索したいときも上記の方法で出来ます)
問題 問題のURLはこちらです。 No.327 アルファベット列 - yukicoder 考えたこと 出力する文字列をとおきます。の値とそれに対応する文字列は次の通り。 0 1 2 ... 25 26 27 ... 51 52 53 ... A B C ... Z AA AB ... AZ BA BB ... この表の関係を見ると、ち…
ある非負整数をn進数で表す。(n>=2) また、n進数で表された非負整数を10進数で表す。
こんにちは。satanicです。 最近よく競プロの問題を解いており、「考えたこととかどっかにまとめて書いておけたら便利かな」と思っていたところ、フォロワーさんがはてなブログに競プロの記事を書いているのを見つけたので、私も初めてみました。 ということ…