日々drdrする人のメモ

今日も明日もdrdr

AtCoder

AtCoder: Tenka1 Programmer Contest 2019 - D問題: Three Colors

コンテスト中に解けなかった。だめだめだった。atcoder.jp 問題概要 個の整数が与えられ、番目の数はである。各数について赤、青、緑の3色で塗り分けることを考える。 そして塗り分けた個の数の中で、その色で塗られた整数の総和をそれぞれとする。全ての塗…

AtCoder: Mujin Programming Challenge 2018 - F問題: チーム分け

実際には少なく見積もれる計算量がなかなか慣れない。atcoder.jp 問題概要 人をいくつかのチームに分ける。 この時、番目の人は人以下のチームのみに所属できる。この条件の元、人のチーム分けとして何通り考えられるかをMOD で求めよ。 (ここでは、人は区別…

AtCoder: エクサウィザーズ2019 - E問題: Black or White

コンテスト中に解けなかった問題。思考力が足りなかった (終) 想定解法メモ。atcoder.jp 問題概要 個の黒いチョコレートと個の白いチョコレートがある。黒と白を等確率で選び、選んだ色のチョコレートが存在すれば食べる、をチョコレートがなくなるまで繰り…

AtCoder: エクサウィザーズ2019 - D問題: Modulo Operations

これ解くのに1時間はかかりすぎた。反省回。 atcoder.jp 問題概要 個の整数からなる集合と整数が与えられる。この集合に含まれる1つの整数を取り除き、整数を mod に書き換える。この操作を集合が空になるまでの回行う。集合の整数を取り除く順序は通り存在…

AtCoder Grand Contest 032 - D問題: Rotation Sort

コンテスト中に悩んで解けなかった。想定解法のメモ。 atcoder.jp 問題概要 の順列が与えられる。この順列に対し、以下の操作を行える。 あるを選び、を一つ左にシフトする コストはかかる あるを選び、を一つ右にシフトする コストはかかる を昇順に並べる…

AtCoder: 早稲田大学プログラミングコンテスト2019 - D問題: Choose Your Characters

コンテスト時間中に解いた。解法メモ。atcoder.jp 問題概要 とあるアクションゲームにおいて、の番号が振られた種類のキャラがいる。 これらのキャラには、対戦する際の有利不利、もしくは五分の関係がある。 (キャラがキャラに対し有利である場合は、必ずキ…

AtCoder: AtCoder Grand Contest 028 - B問題: Removing Blocks

組み合わせを計算する問題は、計算の視点がうまく合わせられないとなかなか計算できなくて、頭を抱える...。 結局、公式の解法を見て通した。atcoder.jp 問題概要 個のブロックが一列に並んでいて、番目のブロックの重さはである。このブロックを1つずつ取り…

AtCoder: 全国統一プログラミング王決定戦本戦 - G問題: Greatest Journey

コンテスト中は(E問題でハマってて)見なかった問題。後日公式の解説見ながら通した。atcoder.jp 問題概要 1からNまでの番号が付いた個の頂点を持つ木がある。この木の上を1からMまでの番号がついた人の人が移動し、番目の人は頂点からちょうど回辺を伝って頂…

AtCoder: 全国統一プログラミング王決定戦本戦 - E問題: Erasure

本戦中にはなんとか解けたけど、通り数計算まわりで無限にハマってつらくなった問題。 こんなハマり方はしないようにしたい...。atcoder.jp 問題概要 1からまでの番号付きの個のブロックがある。 を満たすを選び、以上以下のブロックを消すことを考える。こ…

DPまとめコンテスト - O問題: Matching

問題: O - Matching気づき含めた解法メモ 問題概要 人の男性と人の女性がいる。男性と女性の相性の良し悪しがによって与えられ、1なら相性が良く、0なら相性が悪い。ここで、相性の良い男女同士のペア組を作るとき、これは何通り存在するか。で割った余りで…

AGC024 - D問題: Isomorphism Freak

問題: D: Isomorphism Freak - AtCoder Grand Contest 024 | AtCoder1100点だけど、実質700, 800点問題な感じ。 コンテスト中に解けないといけなかった問題。猛省。 問題 木を何色かで彩色したものの内、ある色で彩色された頂点を根とした根付き木は全て同型…

ARC085 - E問題: MUL

昔いろいろ考えたけど、書き忘れた問題 問題: E - MUL

ARC087 - E問題: Prefix-free Game

解いたので解法メモ URL: E - Prefix-free Game

AGC023 - C問題: Painting Machines

問題: C - Painting Machines横一列に並んだN個のマスを、N-1台のマシンで塗っていく。i番目のマシンはi番目とi+1番目のマスを黒く塗る。 ある順列Pを与え、その番号の順番でマシンを動かしていき、N個のマスが初めて黒く濡れた時点のPのindex(1-indexed)が…

ARC096 - E問題: Everything on It

問題: E - Everything on ItN種類のトッピングが乗せれるラーメンで、トッピングの組み合わせを異なる通りの組み合わせのラーメンのうち何杯か注文し、N種類のトッピングが、注文したラーメンらのうち2杯以上に乗っている組み合わせ数を計算する問題。公式や…

ARC052 - C問題: 高橋くんと不思議な道

問題: C - 高橋くんと不思議な道N個の頂点と2つのタイプを含むM個の辺が存在する。タイプAは1のコスト、タイプBは(今まで通過したタイプBの辺数)+1のコストがかかる時、頂点0から各頂点に到達するための最小コストはいくらかを答える問題。コンテスト中にも…

ARC065 - E問題: へんなコンパス / Manhattan Compass

問題: E - へんなコンパス / Manhattan Compass平面上のN個の穴について(a, b)の穴のペアから始めて、マンハッタン距離が同じ穴のペアを辿ること(ペア(p, q)とペア(p, r)の距離が等しければ、一方からもう一方を辿ることができる)で辿れるペア数を求める問題…

ARC062 - E問題: AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer

問題: E - AtCoDeerくんと立方体づくり / Building Cubes with AtCoDeer4頂点に色を持つN個のタイルを組み合わせ、全ての接するタイルの頂点の色を同じにしながら構成できる立方体は何通り存在するか、を計算する問題。とりあえず自分の解法。ほぼ想定解法。

ARC057 - C問題: 2乗根

想定解法メモ。問題は、入力としてが与えられ、 の上桁がとなるようなを求める問題。問題: C - 2乗根

ARC047 - C問題: N!÷K番目の単語

自分のための解法メモ (公式の解法スライド読んでピンとこなかったので)問題: C - N!÷K番目の単語

ATC001 - C問題: 高速フーリエ変換 (FMT解法)

頑張ってPythonで解いた。C: 高速フーリエ変換 - AtCoder Typical Contest 001 | AtCoder

ABC009 - D問題: 漸化式 (ビット行列解法)

ちょっと昔の話だけど書いとく。今回はABC009のD問題: "漸化式" をビット行列として解いた話 (Python)D: 漸化式 - AtCoder Beginner Contest 009 | AtCoder

Xmas Contest 2016 昼の部 に参加した

12/24に行われていたXmas Contest 2016の昼の部に参加した。 参加しようとしてたら、ちゃっく(@chakku_000)にチーム組みを誘われたので、ロ技研部室に集まって参加した。xmascon16noon.contest.atcoder.jp

ARC066, ABC050 - D問題: Xor Sum

コンテスト中に解けなかったけど、解説に載ってた解法以外で解けたのでメモ D: Xor Sum - AtCoder Regular Contest 066 | AtCoder