読者です 読者をやめる 読者になる 読者になる

sataniC++

C++、競プロ、数学などについて色々考えたりします。

HackerRank 101 Hack 47 - Basketball Game

問題のURLはこちらです。 [https://www.hackerrank.com/contests/101hack47/challenges/basketball-game:title]

Codeforces Round #400 (Div. 1 + Div. 2, combined) ABCD

コンテストページのURLはこちらです。 Dashboard - ICM Technex 2017 and Codeforces Round #400 (Div. 1 + Div. 2, combined) - Codeforces

ダブリング

「N個次の要素を知りたい」といった状況で頻繁に用いられるテクニックです。

CODE FESTIVAL 2016に参加しました

CODE FESTIVAL 2016の予選に通過できたので、本選にも参加してきました。 それに関してあったことなど、いろいろ書いておきます。

競技プログラミングを始めて1年が経ちました

2015/11/22に競技プログラミングを始めてから丁度1年が経ったので、競技プログラミングをやるにあたって、何をしていたか等を記事としてまとめておきます。 (ためになる話は多分そこまでないです) この記事の流れ この記事は次のような構成になっておりま…

yukicoder No.409 ダイエット

問題 問題のURLはこちらです。 No.409 ダイエット - yukicoder 考えたこと 動的計画法を使います。配列を次のように定義します。 日目にドーナツを食べた時の体重の変化量の最小値すると、その時の漸化式は、 なお、最初の行を簡単に説明すると、 (日目にド…

Convex-Hull Trick

直線集合L={f_i(x)=a_ix+b_i}に対して、「Lへの直線f_k(x)=a_k x+b_kの追加」(以下、追加クエリ)と、「あるxに対し、Lの中で最小値(あるいは最大値)を取るような直線の値を求める」(以下、最小値クエリ)という2つのクエリを効率的に行うことが出来ます。

SRM691(Div1)に参加しました!が…

初めてのDiv1だ。゚(゚´ω`゚)゚。— satanic@C++ (@satanic0258) 2016年5月30日 今回は色々意外なことがあったので日記として書いておきます。 (この記事に解説は含まれないので予めご了承下さい) 私が前回参加したのはSRM688だった、ということで気づいたら2回分…

繰り返し自乗法

概要 の値を効率的に解きます。 使える状況 「をで割ったあまり」が欲しいときに、があまりにも大きいとその計算だけで時間がかかってしまうことがあります。そのような時には、この繰り返し自乗法を用いることで素早く求めることが出来ます。 説明 の値を求…

SRM688(Div2)に参加しました!

はじめてのSRM— satanic@C++ (@satanic0258) April 15, 2016競プロのカレンダーを見ていると、2016/04/16 00:00(日本時間)からSRMがあるということだったので、TopCoder SRMに初参戦してみました。 初参戦ということでレートは1200から始まり、Div2の問題を…

yukicoder No.22 括弧の対応

問題 問題のURLはこちらです。 No.22 括弧の対応 - yukicoder 考えたこと まず、入力された各括弧の深さを表す配列をいもす法を使って格納しておきます。いもす法に関しては、こちらの記事を参照してください。 satanic0258.hatenablog.comそして、調べる番…

Imos法(いもす法)

累積和を用いて複数の要素の重なり・深さなどを計算します。

累積和手法

ある配列の任意の区間での部分和を求める。

包除原理

ある複数の集合における和集合の要素の個数を共通部分に配慮して正しく計算する。

yukicoder No.21 平均の差

問題 問題のURLはこちらです。 No.21 平均の差 - yukicoder 考えたこと グループの数は以上であるため、「最大値と最小値の差」を求めれば良いですね。 グループの分け方としては、「最大値」「最小値」「余り」とします。以下の図を見たら明らかですね。 (…

yukicoder No.18 うーさー暗号

問題 問題のURLはこちらです。 No.18 うーさー暗号 - yukicoder 考えたこと 個目の文字について、 文字を数値に変換する その数値から引く 数値を文字に変換する と行えばよさそうですね。 コード(C++) #85751 No.18 うーさー暗号 - yukicoder #include <iostream> #in</iostream>…

yukicoder No.5 数字のブロック

問題 問題のURLはこちらです。 No.5 数字のブロック - yukicoder 考えたこと 「をうまく組み合わせてちょうどになるように…!」って問題でも無いので、の小さい順にから引くたびにカウントしていき、がマイナスになった時点でループを終了しその時の個数を出…

yukicoder No.91 赤、緑、青の石

問題 問題のURLはこちらです。 No.91 赤、緑、青の石 - yukicoder 考えたこと 「あることが成り立つときの最大値」を求めれば良いため、 アクセサリーを個作ることが出来るかどうかを調べる関数を作る。 の値で二分探索する。 とすることで答えを求めること…

二分法(二分探索)

ある条件を満たすものの最大値を求めます。 (ソートされた配列に対してある値を探索したいときも上記の方法で出来ます)

yukicoder No.327 アルファベット列

問題 問題の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です。 最近よく競プロの問題を解いており、「考えたこととかどっかにまとめて書いておけたら便利かな」と思っていたところ、フォロワーさんがはてなブログに競プロの記事を書いているのを見つけたので、私も初めてみました。 ということ…