selpo's diary

主に競プロの解説をします。C#erです。

AtCoder

問題E『数式とクエリ』: codeFlyer 本選

問題文 : 数式とクエリ 概要 以下のBNF表記の<expr>で表される数式Sと、S中の左からi番目の変数aの初期値が与えられる。からなるQ個のクエリに答えよ。 S中の左から番目以外の変数は初期値のままで、番目の変数にを代入したときの数式の値をで割ったあまりを出力す</expr>…

問題C『+/- Rectangle』 : AtCoder Grand Contest 016

問題文 : +/- Rectangle 概要 の盤面に整数を書き込んで、次の条件を満たすようにできるか?できるなら具体的に作れ。 の大きさの部分長方形を任意に取ってくると、その中での総和は必ず負 盤面全体の総和は正 制約

問題B『チョコレート』 : AtCoder Regular Contest 025

解法しか見当たらなかったので。問題文 : チョコレート 概要 の盤面上に整数C[x,y]が書かれており、市松模様の色(白、黒)が塗られている。 盤面上に含まれる長方形領域のうち、その中に書かれた白と黒の総和が一致するようなものの面積の最大値を求めよ。 制…

問題C『N!÷K番目の単語』 : ARC(AtCoder Regular Contest) 047

問題文 : N!÷K番目の単語 概要 の並び替え( 個ある)を辞書順に並べたとき、 1-indexedで番目にくる並び替えは何か。 制約 解説 並び替えといえば階乗進数。 0-indexedで番目の数に対応する階乗進数表記が求まればよい。 階乗進数と順列の対応付け - 猫尾製作…

DDPC 2016 本選 問題Cの補足

計算量がよくわからないとか言ってましたが、実はらしいです。というのも、長さの括弧列に対する計算量をとすると、 (1) (2) となるはずです(は正の定数)。仮にとしてみましょう。(1) となるためには、であればよいです。 (2) となるためには、であればよい…

問題C『特別講演「括弧列と塗り分け」』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選

問題文 : 特別講演「括弧列と塗り分け」 概要 きちんと対応の取れている、括弧のみからなる文字列がある。 非負整数が与えられたとき、以下の場合の数(をで割った余り)を求めよ。のそれぞれにを割り当てる方法のうち、以下の条件を満たすものの個数。 (条件)…

問題B『DDPC特別ビュッフェⅡ』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選

冷静に考えればそこまで難しくはないのですが、 朝だと頭が働かず、本番中には解けませんでした。問題文 : DDPC特別ビュッフェⅡ 概要 種類の料理があり、i番目の料理は時刻までしか食べられない。 また、それぞれの料理にはスコアが決まっており、一度食べた…

問題A『DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016 Ⅱ』 : DDPC(DISCO presents ディスカバリーチャンネル プログラミングコンテスト)2016 本選

めっちゃ簡単ですが、最初の記事ということで。問題文 : DISCO presents ディスカバリーチャンネルプログラミングコンテスト 2016 Ⅱ 概要 順位に応じて以下のように賞金が決まっている。1位: 100000 2位: 50000 3位: 30000 4位: 20000 5位: 10000 6位以下: 0…