n-knuu's logs

憧れ駆動。だいたい競プロ

区間 mex クエリ問題

集合の中に含まれない最小の数を求める操作は mex(minimum exclude に由来) と呼ばれている。 Mex (mathematics) - Wikipedia 区間に対する mex を求める問題を見かけたので備忘録として書いておく。 問題 はじめ、集合 S は空集合であるとする。 Q 個のクエ…

CODE THANKS FESTIVAL 2017 H. Union Sets

この記事は 解説 Advent Calendar 2017 の10日目の記事です。 昨日は unko08658932 さんで「Code Thanks Festival 2017 F Limited Xor Subset 解説 (ありがとう2017F問題の想定解じゃないのを書きます)」でした。 問題 H: Union Sets - CODE THANKS FESTIVAL…

AtCoder Regular Contest 075 E. Meaningful Mean

以下のことを考えて、やっぱり解説を書くことにした 復習のときに思いつかなかったので、ちゃんと記憶に残すために書いておくべき 自分用のメモは残したりしているけど、人に読んでもらうために文章を考えることは、記憶に残す上でも文章を書く練習上でも重…

CODE FESTIVAL 2016 Elimination Tournament Round 1 B. 数字列をカンマで分ける問題

問題 B: 数字列をカンマで分ける問題 / Problem where Commas Separate Digits - CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel) | AtCoder

AtCoder Beginner Contest 009 D. 漸化式

問題 D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder

AtCoder Beginner Contest 004 D. マーブル

最小費用流の問題が欲しくて探していたら、以前別解で解いた問題があったので、解き直した 問題 D: マーブル - AtCoder Beginner Contest 004 | AtCoder

DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 C. アメージングな文字列は、きみが作る!

Suffix Arrayのライブラリ整備のために解いた 問題 C: アメージングな文字列は、きみが作る! - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder

京都大学プログラミングコンテスト 2016 E. 柵

問題 E: 柵 / Fences - Kyoto University Programming Contest 2016 | AtCoder

天下一プログラマーコンテスト2015予選A C. 天下一美術館

問題 C: 天下一美術館 - 天下一プログラマーコンテスト2015予選A | AtCoder

AOJ2594 Reverse Roads

問題 Reverse Roads | Aizu Online Judge

AtCoder Beginner Contest 010 D. 浮気予防

問題 D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder

AOJ2328 Mobile Network

Mobile Network | Aizu Online Judge 問題 無向フローが与えられるので頂点1からNへの最大フローを求めよ。 ただし、枝の重みがxの多項式で与えられるものとする。 制約 2 0 多項式の次数 0 多項式に含まれない)

yukicoder No.177 制作進行の宮森あおいです!

8月後半〜9月末まではインターンとかで忙しくて中々書けなかったが、そろそろCodeFestival2016本戦に向けて再開していきたい。 問題 No.177 制作進行の宮森あおいです! - yukicoder

SRM696 div.1 300 Gperm

寝坊したので出れなかった。 問題 50個の頂点とM個の枝を持つグラフ(単純グラフとは限らない)が与えられる。初め、各頂点は全て塗りつぶされていないとする。毎回、どこか1つの頂点を塗りつぶした後に、枝の両端の頂点がともに塗りつぶされている枝の数だけ…

Codeforces Round #367 (div. 2)

Codeforces Round #367 (div. 2)に参加した。 officialだと230位くらいでレートが下がりそうな順位だった。 A. Beru-taxi 問題 タクシーiが(x_i, y_i)にいて、速度v_i(1 解法 距離/速度を計算するだけ 計算量 O(N) コード B. Interesting drink 問題 N個の商…

技術室奥プログラミングコンテスト#2 D - エンブレム(Emblem)

問題: D: エンブレム(Emblem) - 技術室奥プログラミングコンテスト#2 | AtCoder 解説: http://www.slideshare.net/maroonrk/ss-64770318

AtCoder Beginner Contest #041 (Nim-langの練習帳)

いつも通り、Nim-langでABCに出た Nim-lang: index - Nim Programming Language Nim-lang Tutorial: Nim Tutorial (Part I) Nim Standard Library: Nim Standard Libraryabc041.contest.atcoder.jp A - 添字 echo(s[i-1]) B - 直方体 A*Bしたあとに一度modを…

SnackDown 2016 Online Elimination Round

SnackDown 2016 Online Elimination Roundにe-monさんと出た 361位でTシャツラインにあと61位届かなかった VCake 解法 制約から、切るのは2回だけなので、切り方は2回に対して[縦に切る, 横に切る]の2通りあるから、計4通りある。 また、どの大きさのケーキ…

Yandex.Algorithm 2016 Online Round 2

Algorithm 2016 — Yandex.Algorithm 2016 Online Round 2 — Enter 午前3時からという日本人を潰しにかかったような時間だったけど、2完242位だった これで総合4完327位なので、頑張ればTシャツいけそう? A. Role Distribution 解法 問題文の例では長い部分…

AtCoder Beginner Contest #039 (Nim-langの練習帳)

いつも通り、Nim-langでABCに出た Nim-lang: index - Nim Programming Language Nim-lang Tutorial: Nim Tutorial (Part I) Nim Standard Library: Nim Standard Libraryabc039.contest.atcoder.jp A - 高橋直体 2 * (A*B + B*C * C*A) B - エージェント高橋…

SRM552 div.1 250 FoxPaintingBalls

練習会で1完だった 問題 TopCoder Statistics - Problem Statement リンク先の図のように、ボールを並べてN段のtriangleにR,G,Bの3色で、ボールどうしで色が隣り合わないように色を塗る(図はN=3)とする。 R, G, Bで塗れる回数がそれぞれ決まっているときに、…

SnackDown Online Pre-elimination round A

SnackDown Online Pre-elimination round Aにe-monさんと出た。 1000位以上が次のOnline Elimination roundに進めて、204位だったので進めた。 Art(MAKEART) e-monさんが読んで解いたので知らない N different palindromes(NDIFFPAL) 僕が読んで書いた 問題 …

Codeforces Round #355 div2 C. Vanya and Label

問題 文字列S(0..9, A..Z, a..z, -, _)を64進数とみなす。このとき、論理和をとってSと等しくなる文字列の個数を求めよ(ただしmod 10^9+7を取れ) 制約 1 解法 64進数なので、ちょうど6桁ごとに論理和を取って一致すればよい。 よってまず、64×64の組み合わせ…

Codeforces Round #355 Div.2 A. Vanya and Fence / B. Vanya and Food Processor

Dashboard - Codeforces Round #355 (Div. 2) - Codeforces4問解くか、3問早解きか、みたいな回だった A. Vanya and Fence 問題 数列Aの各値を、H以下なら1、Hより大きいなら2と変換する。変換後の和を求めよ。 こんな問題文だからreadforcesとか揶揄される…

AOJ1241 Lagrange's Four-Square Theorem

AOJ

Lagrange's Four-Square Theorem | Aizu Online Judge 問題 整数Kが与えられるので、4個以下の数の二乗和がちょうどKになるような数の組の個数を求めよ 制約 K テストケースの個数 T 解法 2乗して2^15以下となる最大の数は181なので、下のように4乗ループを…

Yandex.Algorithm 2016 Online Round 1

Algorithm 2016 — Yandex.Algorithm 2016 Online Round 1 — Enter2完523位だった Tシャツ圏内が3回合わせて512位なので、3回きっちり出て、解ける問題を解けばなんとかいけそうかなあという感じ? ただ残り2回が、午前3時からと午後4時からという、日本人を…

SRM551 div.1 250 ColorfulChocolates

練習会に出て1完。Medは解けそうでダメだった。 問題 数列が与えられる(長さ50以下)。隣どうしをswapして良い最大の回数が与えられるので、同じ数が連続する長さを最大にしたい。最大の長さを求めよ。 解法 一箇所を固定してシミュレーションすればよい。 具…

SnackDown Online Qualifier 2016

SnackDown Online Qualifier 2016にe-monさんと出ました。 1問解けば次に進めますが、僕とe-monさんで2問ずつ解きました。 Kitchen Timetable 僕が解いた。 問題 各人が料理を始めるタイムテーブルA_1, ..., A_N(A_1 最後まで完成できる人は何人か? 解法 A…

AOJ1356 Decimal Sequences

AOJ

問題 Decimal Sequences | Aizu Online Judge 解法 nが10^3以下なので、作れる数はn*(n+1)/2 *1 コード *1:n*(n+1)/2個の数を全てstringで作るとMLEする

AOJ2639 Yamanote Line

AOJ

問題 Yamanote Line | Aizu Online Judge 解法 1周60分なので、60回起きて寝れば、必ず最初の状態に戻る。よってシミュレーションをして、起きてる間に到着することがあればそれを出力し、60回起きて寝てもダメなら、-1を出力すればよい。 コード