phyllo’s algorithm note

レッドコーダーへの道のりは遠い。休んでる場合じゃない!

ARC099 D. Snuke Numbers

問題 整数nについて、nを十進数で表したときの各桁の和をS(n)とする。 正の整数nで、nより大きいすべての正の整数mに対してn/S(n) 整数Kが与えられたとき、すぬけ数を小さい方からK個列挙せよ。 制約 1 K番目のすぬけ数は10^15以下 解法 「ある整数xについて…

TCO18 MM R2 CrystalLighting

概要 レートのわりに順位がよくて、目標の1つの「1pt以上ゲット(できればTシャツ)」を達成できた:D最終順位は41位(127人参加)でした。 問題 HxWのセル上にクリスタルまたは障害物が置かれており、各クリスタルには、光らせたい色(原色:青/黄/赤、二次色:緑/…

yukicoder No.5002 stick xor

概要 yukicoderでもマラソン問題が用意されてうれしい:) 風邪で熱出して休んでたのもあって頭回っていなかった。。。最終順位は24位(71人参加)でした。最終スコアは42,203点。 問題 NxNの2次元グリッドが与えられ、各セルは白または黒で塗られている。 こ…

codeFlyer C. 徒歩圏内

問題 N個の都市が直線上に並んでおり、それぞれの座標Xが与えられる。 都市iと都市jについて、2都市間の距離がD以下なら徒歩、そうでなければ電車で移動する。 このとき、都市の3つ組(i,j,k)で、以下を満たす個数を求めよ。 i 都市iと都市jの間と、都市jと都…

GCJ18 Round1B B. Mysterious Road Signs

問題 西から東に向かって無限に長い直線道路のある場所にSignfieldという町がある。 この町から東に向かってS個の道路標識がある。 i個目の道路標識はD_iキロメートル地点にあり、西側から見て表側がA_i、裏側がB_iという整数が書かれている。 この整数は、…

GCJ18 Round1B A. Rounding Error

問題 無数にあるプログラミング言語について、N人に、どの言語が好きか?を聞いた。 今、途中までの集計結果(C_1,...,C_L)が与えられている。 例として、「1 2」という集計結果は、3人に回答してもらっていて、言語1が好きといった人が1人、言語2が好きとい…

TCO18 MM R1 RoadsAndJunctions

概要 マラソンはできるだけ参加していきたいお気持ちだったので参加。問題やスコアリングが微妙らしく、苦情もでてた。 (Unratedにもなりえそうだけど、まあしょうがない)最終順位は107位(239人参加)でした。 問題 10~100の町があり、これらすべてを道でつ…

ARC097 E. Sorted and Sorted

問題 1からNまでの番号が書かれた白いボールと黒いボールが合わせて2*N個ランダムに一列に並んでいる。 隣り合う2つのボールを交換する操作を行い、以下を達成したい。 i i これを達成するために必要な最小操作回数を求めよ。 制約 1 解法 最終状態がどんな…

AGC023 B. Find Symmetries

問題 各マスに文字が書かれたNxNの盤面が与えられる。 この盤面を右にAマス、下にBマスずらした盤面を考える。はみ出る場合は、(N+i,N+j)を(i,j)とする(1-origin)。 ずらした盤面の中で「すべてのi,jに対して、マス(i,j)とマス(j,i)に書かれている文字が等し…

AGC023 A. Zero-Sum Ranges

問題 長さNの整数列Aの連続部分列について総和が0になるものの個数(位置が異なる場合は別カウント)を求めよ。 制約 1 -10^9 解法 小さいケースで考えてみる。A={a,b,c}。 よくある手として、要素cで終わる連続部分列{a,b,c}, {b,c}, {c}の総和が0になるもの…

ARC094 D. Worst Case

問題 10^10^10人の参加者が2回のプログラミングコンテストに参加し、高橋くんも2回参加し、1回目にA位、2回目にB位だった。 参加者のスコアが2回の順位それぞれを掛け合わせた値であるとき、高橋くんよりスコアの小さい参加者は最大何人いるか、答えよ。 制…

ARC093 E. Bichrome Spanning Tree

問題 N頂点M辺の重み付き無向グラフGと整数Xが与えられる。 このグラフGの各辺を白か黒で塗りたいが、以下の条件を満たす塗りかたが何通りあるかmod 10^9+7で求めたい。 条件「白辺と黒辺どちらも含む全域木が存在し、そのような全域木のうち、辺の重みの和…

yukicoder No.660 家を通り過ぎないランダムウォーク問題

問題 東西にのびる1次元の道の原点に立っており、東にN歩のところに家がある。 2*N歩以下で家にたどり着くような歩き方を、10^9+7で割った余りで答えよ。 ただし、家に一度たどり着いたら必ず歩くのをやめて家にはいり、それ以降は歩かない。 制約 1 解法 縦…

yukicoder No.5001 排他的論理和でランニング

問題 N個の重複のない1以上10^6以下の整数が与えられる。 ここから重複なしでM個選んですべてのXORを取ったときの値がなるべく大きくなるようにせよ。 制約 5 1 ただし、ジャッジには乱数で生成した値の50ケースで構成される 最終的に提出したアプローチ 最…

ARC092 D. Two Sequences

問題 長さがNの非負整数列が2つ与えられ、それぞれA,Bとする。 1 このN^2個の数字のxorを計算せよ。 制約 1 0 解法 単純に計算しようとするとN^2 = (4 * 10^10)個のxorを計算するので間に合わない。(頑張れば間に合う?) 整数のxorはビットごとに計算される…

HACK TO THE FUTURE 2018本戦参加記

概要 まぐれで予選突破してしまい、こんな機会滅多にないと思うので、参加してきました。future-contest-2018-final.contest.atcoder.jp普段、会場の情報とかつぶやいてくれる人とかありがたいと思っていたので、今回はできるだけつぶやくようにしてみました…

AGC021 B. Holes

問題 平面上にN個穴があいている。 今、原点を中心とした半径Rの円に無作為にすぬけさんを置く。すぬけさんはユークリッド距離で最も近い穴に落ちる。 すべての穴について、すぬけさんが落ちる確率を求めよ。 制約 2 穴の座標はすべて整数、すべて異なる、|x…

天下一プログラマーコンテスト2016予選B C. 天下一プログラマーコンテスト1999

問題 参加者はN人の総当たり戦の記録をアンドウくんとハシモトくんの2人が行う。 記録はN*Nの表に記録する。(1選あたり2つの記録をする) アンドウくんは間違えずに記録するが、ハシモトくんは確率Pで正しい記録、確率(1-P)で間違った記録をしてしまう。 各記…

問題が解けない原因を考えたい

背景 競技プログラミングの能力を鍛えたい。 ただ、何ができなくて解けなかったのか?や、問題の難しい部分はどこなのか?など簡単な抽象的・体系的でとらえたいお気持ち。 なんとなく思ったことがあるので、それを書き出して整理してみる。 「問題を解く」…

Weathernews Programming Competition

概要 圧縮やRangeCoderの勉強のつもりで参加。最終順位は26927.87点で20位。 といっても、一つ前との差分値をRangeCoderで圧縮しただけのコード。 問題 5分おき4観測分の衛星データが波長(16チャネル)ごとに64枚ある。このデータすべてを可能なかぎり圧縮・…

Hokkaido Univ.& Hitachi 2nd New-concept Computing Contest 2017参加記

概要 AtCoderで開催されたマラソンマッチに参加してみた。 phyllo-algo.hatenablog.com 1stの方は比較的時間取れて取り組めたけど、2ndの方は時間がほとんど確保できず、だいたい2.5日分ぐらいしかできなかったと思われる。。最終順位は6,961,040点で73位。W…

Hokkaido Univ.& Hitachi 1st New-concept Computing Contest 2017参加記

概要 AtCoderで開催されたマラソンマッチに参加してみた。終了30分前なので、時系列で振り返ってみる。 システムテスト前のスコア・順位は156,999点で66位/298人。おそらくシステムテスト後は順位下がる・・・最終順位は720,841点で62位でした。今回は知り合…

ARC085 D. ABS

問題 N枚の山札が与えられる。上からi番目のカードの数字はa_i。 XさんとYさんが、この山札を使ってゲームをする。最初にXさんはZが書かれたカード、YさんはWが書かれたカードを持っている。 2人は交互に「山札の上から1枚以上のカードを取り除く。最後にひ…

yukicoder No.595 登山

問題 N個の地点が1~Nまで順番に直線上に並んでおり、地点iの標高がH_iで与えられる。 地点1からスタートし、すべての地点に1回以上訪れたい。終了地点はどこでもよい。 移動は2種類あり、「隣接地点に移動する場合、登る方向に移動する場合のみ標高の差」か…

AGC017 C. Snuke and Spells

問題 N個のボールが一列に並んでおり、各ボールには数字が書かれている。 魔法を使うと、今あるボール個数と同じ数字が書かれたボールを消すことができる。また、魔法は連続的に行うことができる。 例えば、{1,3,3}だった場合、魔法を2回連続で行うと、{1,3,…

AGC017 B. Moderate Differences

問題 N個のマスの一番左にA、一番右にBが書かれており、それ以外は空白になっている。 いま、空白のマスに、以下の条件を満たすように数字を入れることができる。 隣接するどの2マスについてもその差はC以上D以下 このとき、条件を満たすように数字を入れる…

ARC076 E. Connected?

問題 x,y座標の(0,0)から(R,C)までの長方形を考える。 N個の長方形内の点のペアが与えられる。(各点はすべて異なる) ペアの点同士を曲線で結びたい。ただし、長方形の外に出たり、交わってはいけない。 可能かどうか判定せよ。 制約 1 1 解説 Editorial - At…

ARC075 E. Meaningful Mean

問題 長さNの整数列aに対して、空でない連続する部分列の算術平均がK以上であるものの個数を答えよ。 制限 2 1 1 解説 https://atcoder.jp/img/arc075/editorial.pdf AtCoder Regular Contest 075 / Beginner Contest 063 解説放送 - YouTube 愚直に計算する…

yukicoder No.519 アイドルユニット

問題 N人(2の倍数)のアイドルがいる。 全員ペアを組ませて売り出したい。 しかし、ペアには相性度が決まっており、すべてのペアの相性度の合計値が最大になるようにしたい。 相性度の合計の最大値を返せ。 制約 1 0 解説 一般的には、グラフの重み付きマッチ…

ARC047 B. 同一円周上

問題 座標平面上にN個の点がある。 各点の座標は整数で、ある点Pとのマンハッタン距離が同じであることがわかっている。(点Pの座標も整数) 点Pとしてあり得る点を一つ出力せよ。 制約 1 -10^9 解説 arc047 平面座標で、点Pからのマンハッタン距離が同じ点と…