集合の中に含まれない最小の数を求める操作は mex(minimum exclude に由来) と呼ばれている。 Mex (mathematics) - Wikipedia 区間に対する mex を求める問題を見かけたので備忘録として書いておく。 問題 はじめ、集合 S は空集合であるとする。 Q 個のクエ…
この記事は 解説 Advent Calendar 2017 の10日目の記事です。 昨日は unko08658932 さんで「Code Thanks Festival 2017 F Limited Xor Subset 解説 (ありがとう2017F問題の想定解じゃないのを書きます)」でした。 問題 H: Union Sets - CODE THANKS FESTIVAL…
以下のことを考えて、やっぱり解説を書くことにした 復習のときに思いつかなかったので、ちゃんと記憶に残すために書いておくべき 自分用のメモは残したりしているけど、人に読んでもらうために文章を考えることは、記憶に残す上でも文章を書く練習上でも重…
問題 B: 数字列をカンマで分ける問題 / Problem where Commas Separate Digits - CODE FESTIVAL 2016 Elimination Tournament Round 1 (Parallel) | AtCoder
問題 D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder
最小費用流の問題が欲しくて探していたら、以前別解で解いた問題があったので、解き直した 問題 D: マーブル - AtCoder Beginner Contest 004 | AtCoder
Suffix Arrayのライブラリ整備のために解いた 問題 C: アメージングな文字列は、きみが作る! - DISCO presents ディスカバリーチャンネル プログラミングコンテスト2016 予選 | AtCoder
問題 E: 柵 / Fences - Kyoto University Programming Contest 2016 | AtCoder
問題 C: 天下一美術館 - 天下一プログラマーコンテスト2015予選A | AtCoder
問題 Reverse Roads | Aizu Online Judge
問題 D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder
Mobile Network | Aizu Online Judge 問題 無向フローが与えられるので頂点1からNへの最大フローを求めよ。 ただし、枝の重みがxの多項式で与えられるものとする。 制約 2 0 多項式の次数 0 多項式に含まれない)
8月後半〜9月末まではインターンとかで忙しくて中々書けなかったが、そろそろCodeFestival2016本戦に向けて再開していきたい。 問題 No.177 制作進行の宮森あおいです! - yukicoder
寝坊したので出れなかった。 問題 50個の頂点とM個の枝を持つグラフ(単純グラフとは限らない)が与えられる。初め、各頂点は全て塗りつぶされていないとする。毎回、どこか1つの頂点を塗りつぶした後に、枝の両端の頂点がともに塗りつぶされている枝の数だけ…
Codeforces Round #367 (div. 2)に参加した。 officialだと230位くらいでレートが下がりそうな順位だった。 A. Beru-taxi 問題 タクシーiが(x_i, y_i)にいて、速度v_i(1 解法 距離/速度を計算するだけ 計算量 O(N) コード B. Interesting drink 問題 N個の商…
問題: D: エンブレム(Emblem) - 技術室奥プログラミングコンテスト#2 | AtCoder 解説: http://www.slideshare.net/maroonrk/ss-64770318
いつも通り、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にe-monさんと出た 361位でTシャツラインにあと61位届かなかった VCake 解法 制約から、切るのは2回だけなので、切り方は2回に対して[縦に切る, 横に切る]の2通りあるから、計4通りある。 また、どの大きさのケーキ…
Algorithm 2016 — Yandex.Algorithm 2016 Online Round 2 — Enter 午前3時からという日本人を潰しにかかったような時間だったけど、2完242位だった これで総合4完327位なので、頑張ればTシャツいけそう? A. Role Distribution 解法 問題文の例では長い部分…
いつも通り、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 - エージェント高橋…
練習会で1完だった 問題 TopCoder Statistics - Problem Statement リンク先の図のように、ボールを並べてN段のtriangleにR,G,Bの3色で、ボールどうしで色が隣り合わないように色を塗る(図はN=3)とする。 R, G, Bで塗れる回数がそれぞれ決まっているときに、…
SnackDown Online Pre-elimination round Aにe-monさんと出た。 1000位以上が次のOnline Elimination roundに進めて、204位だったので進めた。 Art(MAKEART) e-monさんが読んで解いたので知らない N different palindromes(NDIFFPAL) 僕が読んで書いた 問題 …
問題 文字列S(0..9, A..Z, a..z, -, _)を64進数とみなす。このとき、論理和をとってSと等しくなる文字列の個数を求めよ(ただしmod 10^9+7を取れ) 制約 1 解法 64進数なので、ちょうど6桁ごとに論理和を取って一致すればよい。 よってまず、64×64の組み合わせ…
Dashboard - Codeforces Round #355 (Div. 2) - Codeforces4問解くか、3問早解きか、みたいな回だった A. Vanya and Fence 問題 数列Aの各値を、H以下なら1、Hより大きいなら2と変換する。変換後の和を求めよ。 こんな問題文だからreadforcesとか揶揄される…
Lagrange's Four-Square Theorem | Aizu Online Judge 問題 整数Kが与えられるので、4個以下の数の二乗和がちょうどKになるような数の組の個数を求めよ 制約 K テストケースの個数 T 解法 2乗して2^15以下となる最大の数は181なので、下のように4乗ループを…
Algorithm 2016 — Yandex.Algorithm 2016 Online Round 1 — Enter2完523位だった Tシャツ圏内が3回合わせて512位なので、3回きっちり出て、解ける問題を解けばなんとかいけそうかなあという感じ? ただ残り2回が、午前3時からと午後4時からという、日本人を…
練習会に出て1完。Medは解けそうでダメだった。 問題 数列が与えられる(長さ50以下)。隣どうしをswapして良い最大の回数が与えられるので、同じ数が連続する長さを最大にしたい。最大の長さを求めよ。 解法 一箇所を固定してシミュレーションすればよい。 具…
SnackDown Online Qualifier 2016にe-monさんと出ました。 1問解けば次に進めますが、僕とe-monさんで2問ずつ解きました。 Kitchen Timetable 僕が解いた。 問題 各人が料理を始めるタイムテーブルA_1, ..., A_N(A_1 最後まで完成できる人は何人か? 解法 A…
問題 Decimal Sequences | Aizu Online Judge 解法 nが10^3以下なので、作れる数はn*(n+1)/2 *1 コード *1:n*(n+1)/2個の数を全てstringで作るとMLEする
問題 Yamanote Line | Aizu Online Judge 解法 1周60分なので、60回起きて寝れば、必ず最初の状態に戻る。よってシミュレーションをして、起きてる間に到着することがあればそれを出力し、60回起きて寝てもダメなら、-1を出力すればよい。 コード