SRM 714

Easy:Range Encoding 問題概要 単調増加の配列がarrが与えられる. 配列の中で連続した部分(arr[i] + 1 = arr[i + 1]) があるとき,その部分を [a, b]として置き換えることができる. 例えば,{3,4,5,6} であれば [3, 6] と置き換えることができる. arr配…

Codeforces Round #321 (Div. 2) A~C

A問題 連続した非減少数列の長さを求めれば良いので、前日の稼ぎ以上を今日稼いでいればカウント+1そうでなければカウント=1とする。 前日と今日の稼ぎしかみないので配列は使わず変数2つを使いコードを書いた。 #include <iostream> #include <algorithm> int main() { int </algorithm></iostream>…

KUPC2016 A~D問題

kupc2016.contest.atcoder.jp A問題 問題概要 A時間目からB時間めの始まる直前まで授業は中止される。 N個の履修中の授業のうちいくつの授業をうけることができるか。 解法 各授業の時間に対して の範囲内でないものをカウントしていけば良い。 #include <iostream> in</iostream>…

CodeIQ 「トライアングル・メイズ」

問題 問題はこちらhttps://codeiq.jp/challenge/2833 コード 入力が 程度だったので埋め込みをしました。 回程度のループなら1秒もかからず実行できるので10個埋め込みをすれば十分です。 あとは、入力 にたいして を計算します。 #include<iostream> int main() { </iostream>…

Codeforces 371 Div2 C

問題 codeforces.com 個のクエリが与えられます。それぞれのクエリの内容は以下のとおり : をリストに加える : をリストから1つ削除する。 この はリストの中に1つ以上存在する。 : リストの中に を満たす の個数を求める。ただし、 は0と1のみで構成され…

python3でコードゴルフをするためのテクニック

':'の後ろに式を書くことができる。 for や if のあとにつく : の後ろに続けて式を書くことで余分なスペースを省くことができる。続けて式を書きたい時には ; で区切る。 しかし、2重for や for:if: のように : の後ろに更に : がつくような式は書くことがで…

SRM696 div2 med

自分が参加した部屋(room19)がこの惨劇であったのでとりあえずどういう解法で解いたかを書いていきます。 ちなみに自分は見事に落ちました。 問題概要 配列Aを配列Bと同じにするために、Aの値を配列Fの値で置き換える。しかし、置き換えられるのは1つの要素…

yukicoder No.385 カップ麺生活

考え方 この問題でとりあえず必要なのは素数のリストが必要なので作っておいたものを用意しておく。(逐一素数判定をしても良いが素数のリストを先に作っておいたほうが楽だと思ったので素数のリストが必要ということにする。) あとはi円で買えるカップ麺の…

AtCoder Beginner Contest 039:C ピアニスト高橋君

問題内容 abc039.contest.atcoder.jp高橋君が白鍵の上に立っている。そこから右に20個分の鍵盤の色が与えられるので高橋君がどこにいるのか当てる問題。 解法 全探索で解ける。 (高橋君がドの上にいたと仮定して、入力とマッチしているか確かめる。 違ってい…

AtCoder Beginner Contest 039:D 画像処理高橋君

問題 abc039.contest.atcoder.jp2値画像を一回収縮した2値画像が与えられるので元の画像としてありえるものを出力する。 解法 黒画像(#)がどこにあるのかを探すのは面倒な感じなので白画像(.)のところを求めていくと楽にできる。 C++のコード 6重ネストがあ…

AtCoder Regular Contest 019:こだわりの名前

問題 文字列 が与えられる。 を一文字だけ変更した文字列 を作る。しかし が回文にならないようにしなければならない。 そのような変更の仕方は何通りあるか求める。 解法 ならばどのように文字を変更しても回文になってしまうので、そのような変更の仕方は0…

ディビジョン・ナイン

問題概要 1 から 4 の数字を使って n 桁の整数を作ります。このとき、9 の倍数となるものを考えましょう。 例えば n = 3 であれば、234、333、441、などが 9 の倍数です。必ずしも 1 から 4 の全ての数字を使う必要はありません。 1 から 4 の数字を使って作…

the art of computer programming 1.2.5 を読む

置換と階乗 非負整数に関して の階乗は以下のように定義される。 しかし、 が整数でない時には という記法は余り使われない。 その代わり、以下の記法を用いる。 この関数はガンマ関数と呼ばれ、次のように定義される。

Chokudai Contest 001

問題概要 のマスがあり、あるマスには1以上100以下の整数が書かれている。 すべてのマスを0にするまで以下の動作を続ける。 ①あるマスの値を1減らす ②そのマスの上下左右いずれかのマスが今いるマスの値と同じ時、そのマスに移動し①を実行する。そのようなマ…

the art of computer programming 1.2.4 を読む

1.2.4 整数関数と初等整数論 modについて (a) なら (b) なら (c) は の整数倍 となる。例えば、 となる。最後の式は を考えると、あまりは2,1,0,2,1,0となっているので-1を3で割った余りはその順序に従って2となる。なので、-2を3で割った余りは1となる。 mo…

lay_contest beta round 00001 (in Japanese) B問題 月日

問題概要 m月d日をm/dとする。2016年においてa月b日からc月d日まで異なる有理数はいくつあるか。 解答内容 本来は分子と分母の組ををsetに突っ込んでいくのが想定解答かと思うけど、自分は小数で保持しました コード #include<iostream> #include<set> int main() { int n; </set></iostream>…

lay_contest beta round 00001 (in Japanese) A問題 勝者

問題概要自分とライバル、どちらの点数が高いのか勝負!A問題は4点、B問題は7点、C問題は17点、D問題は22点。自分が解いた問題とライバルが解いた問題が与えられるので自分がライバルに勝てば”WIN"を出力、負ければ”LOSE"を出力、引き分けなら”DOTEN"を出力…

the art of computer programming 1.2.3 を読む

1.2.3 総和と乗積 式(13)について この式の左辺の計算量はで、右辺はである。 この2つの計算量の違いは大きく、左辺はで、1億回の計算することになる(実際は5千万回ほど)。 しかし、左辺は同じでも計算回数は1万回(実際は1万回の計算が2回あるので2万回の計…

the art of computer programming 1.2.2 を読む

対数を使う場合コンピュータの分野では2進対数が用いられるが、 その最大の理由は、コンピュータアルゴリズムが2方向の分岐を多用するから。 if-elseに代表されるように大なり小なりの判定や、ある文字列sとtが同じ文字列かどうかの判定などはyesかnoの2方向…

the art of computer programming 1.2.1 を読む

1.2.1 数学的帰納法 数学的帰納法は以下の方法で証明を行う。 P(n)を整数nについての何らかの言明だとする。 (a) P(1) が真であることを証明する。 (b) [P(1), P(2), ... , P(n)が全て真なら、P(n + 1)も真である。]ことを証明する。 ただし、nを適当な数に…

the art of computer programming 1.1 を読む

1.1アルゴリズム アルゴリズムは単に特定のタイプの問題を解決するための一連の作業手順を定める有限個の規則という以上に、5種類の重要な特徴をもっている。 (1)有限性 アルゴリズムは有限回のステップを実行したあと、必ず終了しなければならない。 以下の…