読者です 読者をやめる 読者になる 読者になる

phyllo’s algorithm note

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

AGC013 C. Ants on a Circle

問題 周の長さがLの円上にN匹の蟻がいる。 それぞれの蟻は番号がついていて、座標X_iと向きW_iが与えられ、毎秒1単位距離の速度で動く。 各蟻は衝突するとそれぞれ進む向きを変える。 T秒後にそれぞれの蟻がいる位置を求めよ。 制約 1 1 0 L-1 W_i = {1,2} …

AGC013 B. Hamiltonish Path

問題 N頂点M辺の連結で単純な無向グラフが与えられる。 このグラフにおける以下の条件を満たすパスを1つ出力せよ。 2頂点以上 同じ頂点を通らない パスの少なくとも一方の端点と直接辺で結ばれている頂点は必ずパスに含まれる 制約 2 1 解説 直感的に、でき…

GCJ2017 Round1A A. Alphabet Cake

問題 R*Cのグリッドに大文字アルファベットまたは「?」が書かれている。 各アルファベットは高々1回しか出現しない。 「?」は出現したアルファベットのどれかを割り当てることができる。 各アルファベットを長方形を維持した状態で拡張し、すべての「?」をど…

二項演算が非可換な場合のセグメント木のクエリ処理

気になったのでメモ。 モノイド セグメント木は、完全二分木の各ノードがその子孫の範囲の情報を管理しているようなデータ構造。 図は、配列(緑)に対して対応するセグメント木(青)を表す。 青の2番は、緑の0番から3番までの範囲に演算した結果を保持する。 …

AGC012 B. Splatter Painting

問題 連結とは限らない、N頂点、M本の辺を持つ無向グラフが与えられる。 頂点には1~Nの番号が振られている。 Q回「頂点v_jから距離d_jの頂点を色c_jで塗る」という操作をした後の各頂点の色が何色か答えよ。 制約 1 0 1 自己ループや多重辺は存在しない 解…

yukicoder No.492 IOI数列

問題 IOI数列は、1,101,10101,1010101,...とa_1=1, a_i=100*a_{i-1}+1であるような数列である。 第N項について、1000000007で割ったあまりと101010101010101010101で割ったあまりを求めよ。 制約 1 解説 第N項を計算したい。 後者の10101...で割ったあまりは…

KUPC2016 E. 柵 / Fences

問題 H*Wのグリッドのいくつかのマスにヤギがいる。 ヤギは上下左右の隣接マスに移動できるが、移動先となるマスに柵がある場合は、その方向へは移動できない。 ヤギがグリッドの外に出ないようにするために必要な柵の最小個数を求めよ。 制約 1 1 解説 http…

AGC010 C. Cleaning

問題 Nノードからなる木が与えらえる。 各ノードにはA[i]個の石が置かれている。 「2つの(異なる)葉ノードを選び、そのパス上のノードすべてから1つずつ取り除く」という操作を繰り返して、すべての石を取り除けるか答えよ。 ただし、パス上に石のないノード…

ARC068 E. Snuke Line

問題 直線上の鉄道で、0~Mまでの番号が付いたM+1個の駅がある。 N種類の名産品が与えられ、名産品iは駅lから駅rまでの区間で売られている。 最初0番の駅にいるとして、d駅ごとに停車する電車の場合、購入可能な名産品の種類数を知りたい。 dが1~Mの場合そ…

CodeFestival2016 Final D.Pair Cards

問題 N枚のカードがあり、カードiには整数X_iが書かれている。 今、「書かれた数字が同じ」または「和がMの倍数」になるような2枚のカードをペアにする。 最大で何ペア作れるか? 制約 2 1 1 解説 https://cf16-final.contest.atcoder.jp/data/other/cf16-fi…

yukicoder No.374 コイン

問題 2人で以下のゲームを行う。 ・半径Aの円の中に、半径Bの円を交互に置いていく ・置いていく円は、半径Aの円からはみ出したり、すでに置いた円とかさなったりしてはいけない ・先に置けなくなった方が負け ・置かれた円は動かせない それぞれ最適に行動…

AtCoder Regular Contest 055 C. ABCAC

問題 文字列Sが与えられる。 この文字列は、それぞれ長さ1以上の文字列A,B,Cを「ABCAC」のように連結してできている。 このような分割は何通りあるか? 制約 5 (部分点:Sの長さ 解法 説明のために、「A B C A' C'」と置く。N=(Sの長さ)とする。 もし、A'が…

テンプレ

コードも残したいと思います。 使っているテンプレは以下です。 #include <algorithm> #include <cstdio> #include <cstdlib> #include <cctype> #include <cmath> #include <iostream> #include <queue> #include <list> #include <stack> #include <map> #include <numeric> #include <set> #include <sstream> #include <string> #include <vector> us…</vector></string></sstream></set></numeric></map></stack></list></queue></iostream></cmath></cctype></cstdlib></cstdio></algorithm>

引っ越し

旧:れどこだ目指すよ! (;`・ω・)