裏紙

ほぼ競プロ、たまに日記

2017-01-01から1年間の記事一覧

CF 847 J - Students Initiation

問題 Problem - J - Codeforces 問題概要 頂点辺の無向グラフが与えられる。この各辺について、どちらかに向きを付けなければならない。その時に各頂点からの出次数の最大値が最小になるような割り当て方を答えよ。 多重辺や自己ループはない アイデア 各辺…

Codechef October Challenge 2017 - Shooting on the array

問題 Contest Page | CodeChef 問題概要 長さの数列が与えられる。xy平面を考えて、数列に対して番目の要素について、とを端点とする線分を引く。以下の2種類のクエリが合計で個与えられるのでそれを処理せよ: + i X : ? i L R : x軸に平行な光が、個発射さ…

Codechef Nomvember Cook-Off 2017 - Adjacent leaves

問題 Contest Page | CodeChef 問題概要 根付き木の美しさを、good subsets of leavesの個数で定義する。 どういうものがgood subsets of leavesになるかというと、根からdfsをしていき、訪れた順番に、そのノードが葉であればその頂点番号をリストに追加す…

ACM-ICPC 2017 Asia Tsukuba Regional に参加しました

ACM-ICPC 2017 Asia Tsukuba Regional | 国際大学対抗プログラミングコンテスト2017アジア地区つくば大会 ACM-ICPCというプログラミングコンテストの国内予選を通過したので、アジア予選に参加してきました。 私はSyntaxSatoというチームのメンバーとして参…

AOJ 1595 - Traffic Tree

問題 Traffic Tree | Aizu Online Judge 問題概要 頂点数の木が与えられる(番目の辺は頂点とを結ぶ)。 隣接する頂点に移動するコストを1であるとすると、各頂点について、その頂点をスタート地点とした時に全ての頂点を訪れるための最小コストを求めよ。 ア…

CS Academy #57 - Binary Flips

問題 CS Academy 問題概要 のバイナリ行列がある。はじめ、行列の全要素は0である。この行列に対して、以下の操作を回行う: 行列のセル()を1つ指定し、行目の全要素をバイナリ反転し、列目の全要素を全要素をバイナリ反転する(よって、セルは2回反転される…

CS Academy #53 - Parallel Rectangles

問題 CS Academy 問題概要 xy平面に点が個与えられる。4点を選んで、それによって長方形を構成したいが、長方形のそれぞれの辺がx軸とy軸にそれぞれ平行になるようにしなければならない。 そのような4点の選び方は何通りあるか。 アイデア 1つ目の方針として…

CF 782 D - Innokenty and a Football League

問題 Problem - D - Codeforces 問題概要 サッカーチームが個ある。それぞれのサッカーチームにはチーム名があり、2単語から構成されている。 各チームの省略形を3文字で決定したい。各チームに対して、省略形の候補は2種類ある: 1単語目のprefix3文字を取…

CF 871 C - Points, Lines and Ready-made Titles

問題 Problem - C - Codeforces 問題概要 2次元平面上に点が個ある。番目の点の座標はである。各点に対して、x軸に平行な線を描く、y軸に平行な線を描く、何も描かないのどれかの操作を選ぶことが出来る。 この個の点から描かれた線を平面上に描かれた画像と…

会津合宿2017 参加記

9/18~9/20の2泊3日で、これに行ってきました atnd.org 競プロオンサイトイベントはCODE FESTIVALしか行ったことなかったので、とてもワクワクしながらオンサイト行きました。 会津大学に初めて行ったんですが、自分が通っている大学と比べてかなり景観が良く…

GCJ 2017 R1A B - Ratatouille

問題 Dashboard - Round 1A 2017 - Google Code Jam 問題概要 究極のラタテュイユのレシピが完成した。レシピにはどの原料をどれほど使うべきか、が記されている。ラタテュイユには種類の原料が必要であり、1人前を作るのに番目の原料がグラム必要である。 …

CS Academy #42 - Xor Submatrix

問題 CS Academy 問題概要 長さの配列と長さの配列が与えられる。これらから、の行列を作る。で行列の各項を与える。 この中で部分行列を取り出し、その部分行列の要素の全てのXORを取る時に、得られる値の最大値を求めよ。 アイデア 部分行列の左上隅のinde…

CS Academy #44 - Array Elimination

問題 CS Academy 問題概要 要素数の配列が与えられる。いま、配列のindexを1つ指しているポインタがあり(はじめは)、そのポインタに対して以下の3つの操作ができる: を1増やす を1減らす が指している位置の要素を削除し、は1つ前の要素か1つ後の要素を指す…

CS Academy #41 - Candles

問題 CS Academy 問題概要 本のろうそくがある。番目のろうそくの長さはである。一晩ろうそくを使用すると長さは1だけ減る。 これから、回の夜を過ごそうとしている。日目の夜には、本のろうそくを灯そうと考えている。最大で過ごせる夜の回数を求めよ。 ア…

CS Academy #40 - Direct the Graph

問題 CS Academy 問題概要 頂点数の完全グラフの各辺に対して向きを付ける(トーナメント)。この時、経路長が3である閉路の個数が最大になるように向きを付け、その向きの付け方と、その結果経路長が3である閉路はいくつになるか答えよ。 アイデア まず、問題…

CS Academy #38 - Tree Antichain (Hard)

問題 CS Academy 問題概要 頂点数の木が与えられる。長さの順列を考え、それを頂点に対応させる時、との間にいずれも辺がないような順列の中で辞書順最小のものを求めよ。 テストケース数 : テストケース全体でのの和はを超えない アイデア 同じラウンドに(E…

CF 765 F - Souvenirs

問題 Problem - F - Codeforces 問題概要 長さの数列が与えられる。 とが与えられ、 の最小値 を答えよというクエリが個与えられるので、それらに答えよ。 アイデア まず、絶対値を考えるのはややこしい。数列をreverseしてindexもreverseして同じクエリに対…

ACM-ICPC 2017 国内予選 に参加しました

ACM-ICPCとは(公式サイト) 3分でわかるICPC 感想(ほぼ箇条書き) 去年と同じメンバーで出ました、この3人で出られるのは今年で最後。 模擬国内前までは、特にPCを制限したりせず、3人で集まったら何かの問題セット選んで一緒に考えるみたいなことをやってきて…

CS Academy #14 - Subarrays Xor Sum

問題 CS Academy 問題概要 長さの数列が与えられる。長さが以上以下の部分列に対して、xorを取った値の和をで割った余りを答えよ。 アイデア ビットごとに独立に考えていく。今、ビットを固定する(とする)と、もとの数列は01の数列として見なすことができる…

CS Academy #20 - Palindromic Concatenation

問題 Archive 問題概要 文字列が個与えられる。番目の文字列をと表す時、との連結(この順番に並べて結合した文字列)が回文になるような組の個数を求めよ。 は英小文字のみで構成される とは区別される アイデア が回文になる時、どのような状況になれば条件…

CF 798 D - Mike and distribution

問題 Problem - D - Codeforces 問題概要 長さの数列とが与えられる。 いま、数列のindexを個選ぶことが出来る。選んだ個のindexをとするとき、次の条件を満たすように個のindexを選べ: このような条件を満たすを答えよ。 アイデア まず、は多いほうが得だ…

CF 785 D - Anton and School - 2

問題 Problem - D - Codeforces 問題概要 (と)のみで構成される文字列について、次のような長さの文字列をregular simple bracket sequences(RSBS)と呼ぶことにする: 空文字列ではない() は偶数で、前半の文字は全て(、後半の文字は全て) 例えば((()))はRSB…

CF 740 D - Alyona and a tree

問題 Problem - D - Codeforces 問題概要 頂点数の木があり、各頂点にはからまでの番号が振られている。根の頂点番号はである。各頂点はそれぞれ整数を持っている。 また、辺には重みがあり、本の辺の情報について、個目の情報は頂点とを結んでおり、その重…

CF 738 F - Financiers Game

問題 Problem - F - Codeforces 問題概要 長さの数列が与えられる。この数列を使って、LさんとRさんの2人でゲームを行う。 ゲームはLさんのターンで始まる。まず、Lさんは数列の左端からスタートし、そこから1つか2つの値を数列から取り除きその合計を自分の…

SRM 643 Div1 Easy - TheKingsFactorization

問題 TopCoder Statistics - Problem Statement 問題概要 自然数の素因数分解を求めよ。ただし、の素因数の小さい方から順に奇数番目だけ素因数が何であるかのヒントが与えられる。 例えば、であるとき、素因数分解はであるから、小さい方から数えて奇数番目…

CF 701 F - Break Up

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフがある。グラフが連結である保証はない。 いま、ある辺を削除して頂点から頂点への移動をできなくなるようにすることを考える。しかし、辺の削除の上限は2本である。辺にはそれぞれ削除のコストが…

CF 701 E - Connecting Universities

問題 Problem - E - Codeforces 問題概要 頂点数の木があり、頂点にはからの番号が振られている(グラフの情報は、各辺がどの頂点を繋いでいるかが与えられる)。このうち、個の頂点番号が指定される。それらをとする。これら個の頂点から、個のペアを作る。そ…

ARC 068 E - Snuke Line

問題 E: Snuke Line - AtCoder Regular Contest 068 | AtCoder 問題概要 個の駅があり、駅に対してからまでの番号が振られている。列車は駅から駅ごとに停車する。また、種類の名産品があり、番目の名産品は駅から駅の区間で売られており、その駅に停まると…

FHC 2017 R2 C - Fighting all the Zombies

問題 Fighting all the Zombies | Facebook Hacker Cup 2017 Round 2 問題概要 RPGをやっている。主人公は魔法使いである。 体のゾンビがいる洞窟がある。番目のゾンビの強さはである。いま、レベリングのために、この洞窟を回周回しようと考えている。この…

CF 749 E - Inversions After Shuffle

問題 Problem - E - Codeforces 問題概要 からまでの数を並べた長さの順列がある。1回だけ以下の操作を行う: 全ての区間個のうち、区間(から)をランダムに選ぶ。そして、その区間の長さをとし、その区間に対して、シャッフルを行う(つまり、通りの並び替え方…