Hatena::ブログ(Diary)

simezi_tanの日記

2018-05-14

ARC 097 F Monochrome Cat

| 06:39 | ARC 097 F Monochrome Catを含むブックマーク

問題

N頂点からなり、各頂点が黒または白である木が与えられる。

好きな頂点から出発して、

  • 今いる頂点の色を反転させる
  • 隣接する頂点に移動して、移動先の色を反転させる

の二つの操作を好きなだけ行える。全部の頂点の色を黒にするのにかかる操作の回数の最小値を求めよ。終了時にはどこにいてもいい。

https://beta.atcoder.jp/contests/arc097/tasks/arc097_d

制約条件

N≦10^5

続きを読む

ARC 097

| 06:28 | ARC 097を含むブックマーク

ボケ防止にまったり勢でプロコン復帰します。

C

sの異なる連続する部分文字列のうち辞書順でK番目に小さいものを出力せよ。


  • 最初から結構難しそう。制約がないと結構面倒な問題じゃなかったっけか。
  • substringを全部列挙してsetに入れる → O(N^3logN)とかになり間に合わない。
  • Kが小さいらしい。長さ1〜Kの文字列は全部異なるから、各iについてs[i..i+K]まで列挙すれば十分
  • AC. 最初の問題に7分以上かかる。相当考察力が落ちている。

D

順列pとn個のタプル(xi, yi)が与えられる。順列に大してxi番目とyi番目を入れ替える操作が何度でもできるとき、pi = iとなるiの個数を最大化せよ。


  • (1, 3), (3, 4)が与えられていたら1, 3, 4番目は自由に入れ替えられる
  • 各連結成分ごとに要素をまとめて、成分内でマッチングすればよさそう
  • 二つの単調増加列のマッチングだから尺取りで書けばいい
  • AC.

E

1〜Nまでの数字が書かれた白いボールと黒いボール合わせて2N個が一列に並んでいる。

隣り合うボールを入れ替えて、白いボールだけを見たときにソートされていて、かつ、黒いボールだけを見たときにソートされている状態にしたい。必要な操作の回数の最小値を求めよ。


  • バブルソートの交換回数の拡張みたいな奴。バブルソートのときってどうするんだっけ。
  • Binary Indexed Treeで転置のペアの個数を数えるだっけ → 今回は転置を数えても最終状態が一意に定まらないし上手くいかなそう
  • バブルソートの交換回数って分割統治みたいなアルゴリズムもあったような。忘れた。

  • 普通のバブルソートの交換回数は、愚直に求めるには当然O(N^2)でバブルソートを実際にシミュレーションすればいい。
  • 今回、最終状態が一通りじゃないからシミュレーションすら無理だ。
  • 白いボールの位置を決めたらコストは求まりそう → DPなんかなこれ。
  • dp[白いボールを使った個数][黒いボールを使った個数] := その時点の操作の回数 とすると?
  • いけそう、書いてみる。

  • 遷移が上手く書けない。bitか何かでコストを高速に求めないといけない。
  • 思考がごちゃごちゃする。遷移を整理してみる。
  • 白をi個、黒をj個使った状態で白のi+1を使うとき
  • 列の白i+1の前にあるボールのうち、白の番号がiより大、黒の番号がjより大のものの個数が高速に求まればいい。
  • 最初に前計算すればいいか。

  • 送信。RE. 配列を2NじゃなくてNで取ってた。
  • 送信してAC.
  • 手間取りすぎー。順位表見ると、この時点で48位。どの程度なのか全然わからない。
  • 昔のTopCoderだったら微妙。ARCはそれより参加人数少なそうだし(要出典)アレかも。

F

木が与えられる。頂点は白または黒。好きな頂点から出発して、今いる頂点の色を反転させる、または隣接する頂点に移動して、移動先の色を反転させる、の二つの操作を好きなだけ行える。全部の頂点の色を黒にするのにかかる操作の回数の最小値は?終了時にはどこにいてもいい。


  • 残り1時間。
  • 全部の頂点を回る必要はなさそう → 白と白のパス上の頂点だけ考えればいい
  • 木の黒のリーフは落とせるだけ落として考える。
  • 白の頂点が木のリーフにしかないとき、オイラーツアーが最適解?
  • そうじゃないとき、なんか移動を節約できる。。。どう節約できるんだろう。
  • 各辺て何回通る? → 高々2回でよさそう
  • 内点の白のたびに2節約できる? → いや全然嘘
  • 次数によってオイラーツアーした後の色がかわるやんけ。リーフしかないときはオイラーツアーするだけが最適解も嘘だ。
  • 時間切れ。

2018-01-02

ICPC2017 Asia Regional Tsukuba K Counting Cycles

| 19:02 | ICPC2017 Asia Regional Tsukuba K Counting Cyclesを含むブックマーク

問題

n頂点m辺からなる連結な無向グラフが与えられる。そのグラフに含まれる単純閉路(同じ頂点を二度通らないような閉路)の個数を求めよ。

制約条件

n≦10万

m≦n+15

続きを読む

ICPC2017 Asia Regional Tsukuba J String Puzzle

| 18:47 | ICPC2017 Asia Regional Tsukuba J String Puzzleを含むブックマーク

問題

長さnの文字列がありその一部の情報が以下のどれかの形式で与えられる。

  • x文字目がcである
  • l文字目からr文字目がh文字目からと等しい

このときq個のクエリ、x文字目が何の文字であるか、あるいは与えられた情報からではわからないかを答えよ。

制約条件

n≦10^9

アルファベットは英小文字

情報とクエリは1000以下ずつ

それぞれの文字iについて、i文字目とj文字目が等しい(j < j)であるような関係は高々一つしか与えられない。

続きを読む

ICPC2017 Asia Regional Tsukuba I Starting a Scenic Railroad Service

| 18:30 | ICPC2017 Asia Regional Tsukuba I Starting a Scenic Railroad Serviceを含むブックマーク

Hは解説みて通しはしたけど解法の意味がわからない。

問題

n人の乗客がいてそれぞれ駅s[i]からt[i]まで電車に乗る。

全員が座るためには各人が席を指定できないとき、最小でいくつの座席が必要であるか、

また各人が自由に席を指定できるとき最小でいくつの座席が必要であるか求めよ。


また、乗客Aが駅1から2乗客Bが駅2から3まで乗るとき座席は1つで足りる。

制約条件

n≦10万

続きを読む

ICPC2017 Asia Regional Tsukuba G Rendezvous on a Tetrahedron

| 18:14 | ICPC2017 Asia Regional Tsukuba G Rendezvous on a Tetrahedronを含むブックマーク

問題

全ての辺の長さが1の正四面体ABCDの頂点Aから二つの点p, qが与えられた向きに与えられた長さだけ進む。

点は正四面体の辺を通過するとき、辺と進む向きの角度が変化しないように進む。


移動後に二つの点が同じ面の中にいるかを判定せよ。

制約条件

移動後に点がギリギリ辺や頂点のそばにいるケースがない

続きを読む

ICPC2017 Asia Regional Tsukuba F Pizza Delivery

| 18:06 | ICPC2017 Asia Regional Tsukuba F Pizza Deliveryを含むブックマーク

問題

重み付きの有向グラフが与えられる。i番目の辺の向きを反転させたとき、1番から2番の頂点への最短路が

  • 短くなる
  • 変化しない
  • 長くなる

のいずれであるかをそれぞれ出力せよ。

制約条件

グラフの辺と頂点≦10万

辺の重みは正整数で10万以下

続きを読む

ICPC2017 Asia Regional Tsukuba E Black or White

| 17:58 | ICPC2017 Asia Regional Tsukuba E Black or Whiteを含むブックマーク

Dむずくて通せてないですごめんなさい。

問題

n個のセルが黒または白で塗られている。

セルの初期状態およびゴールの状態が与えられる。

セルは一度の操作で連続する1〜k個を好きな色に塗ることができる。

最小で何回の操作で全てのセルをゴールの状態にできるか求めよ。

制約条件

n, k≦50万

続きを読む

ICPC2017 Asia Regional Tsukuba C Medical Checkup

| 17:31 | ICPC2017 Asia Regional Tsukuba C Medical Checkupを含むブックマーク

問題

とても読みにくい問題文。


n人の人がt秒以内に機械(m1, m2, m3, ...)を使う。

  • 同時に一人一個の機械しか使えず、一つの機械は同時に一人でしか使えない
  • 各人はm1から順にとばさずに機械を使う必要がある
  • 各機械は、1番目の人から順に使用する。i番目の人の使用が終わったら即座にi+1番目の人に渡す
  • i番目の人が機械を使うとき、どの機械もh[i]の時間がかかり、中断はできない
  • 機械を渡された人が別の機械を使用中のとき、渡された機械はその人がその前の機械を全て使い終わってから(即座に)使い始める

このとき、各人が何個目の機械を使用中、あるいは何個目の機械を待っている状態であるかを求めよ。t秒の時点でちょうど機械を使い終わった場合、次の機械を待っている状態であるとする。

制約条件

n≦10万

h[i], t≦10^9

続きを読む

ICPC2017 Asia Regional Tsukuba B Parallel Lines

| 17:16 | ICPC2017 Asia Regional Tsukuba B Parallel Linesを含むブックマーク

問題

平面上にm個の点が与えられる。その中から相違なる2n点を選び、n本の線分を作る。(nは自由

n本の線分のうち、平行であるペアの個数を最大化したい。

そのようなペアの個数の最大値はいくつか。

制約条件

m≦16

座標は絶対値1000以下の整数

続きを読む

ICPC2017 Asia Regional Tsukuba A Secret of Chocolate Poles

| 17:05 | ICPC2017 Asia Regional Tsukuba A Secret of Chocolate Poles を含むブックマーク

問題

黒と白の円盤を積み上げてタワーを作る。タワーは以下の条件を満たす必要がある

  • 一枚以上の円盤がある
  • 円盤の厚さの合計はl以下
  • 最も外側の円盤は黒
  • 同じ色同士の円盤が隣り合ってはいけない

黒の円盤は厚さ1またはkのどちらかを選ぶことができて、白の円盤は厚さ1だけ。

条件を満たすタワーは何通りあるか。

制約条件

l≦100, k≦10

続きを読む

2017-12-28

ICPC2017 国内予選 H 等積変形

| 14:08 | ICPC2017 国内予選 H 等積変形を含むブックマーク

問題

面積の等しい三角形A, Bが与えられる。

三角形Aに対し等積変形(二頂点を固定し、残り一頂点を三角形の面積が変わらないように動かす操作)を繰り返し三角形Aを三角形Bに重ねたい。

必要な操作の最低回数(あるいは4回以内にはできない)を求めよ。

続きを読む

ICPC2017 国内予選 E 論理式圧縮機

| 13:37 | ICPC2017 国内予選 E 論理式圧縮機を含むブックマーク

問題

与えられた論理式と常に同じ出力を返すような論理式のうち長さが最小のものを求めよ。

論理式の変数は4つまで、長さは16まで。

続きを読む

ICPC2017 国内予選 D 弁当作り

| 13:31 | ICPC2017 国内予選 D 弁当作りを含むブックマーク

問題

各成分が0, 1であらわされる行列Aが与えられる。

Aの行の部分集合A[i]で、任意の列jに対してΣi_s[i][j]が偶数になるものを考える。

このようなA[i]のうち最大のサイズはいくつか。


例)Aが

010

011

110

101

だったら、2, 3, 4行目を選ぶと全ての列の和が偶数になり、このときの3つが最大。


制約条件

Aをn行m列としたときn, m≦500, nm≦500

続きを読む

2014-11-29

TopCoder SRM 622 Div1 Hard

| 01:05 | TopCoder SRM 622 Div1 Hardを含むブックマーク

問題

aまたはbからなる文字列が与えられる。

このとき、文字列に2回以上、重ならないで出現する空でない部分文字列の個数を求めよ。

文字列が同じときは一つと数える。

制約条件

文字列は乱数により生成される。

n≦10^5

続きを読む

2014-11-27

Codeforces 480(#274 Div1) D. Parcels

| 20:50 | Codeforces 480(#274 Div1) D. Parcelsを含むブックマーク

問題

n個の箱があり、i番目の箱は

時刻in[i]に倉庫に入り、out[i]に倉庫から出る。

この荷物は重さがw[i]であり、上にs[i]までの荷物を載せることができる。

この荷物を倉庫に出し入れするとv[i]円もらえる。


倉庫には、同時に全体でSの重さの荷物しか入れられない。

また、荷物は直前に入れた荷物の真上にのみ置くことができ、最も上にある荷物のみを取り出すことができる。


利益を最大にするように、倉庫に出し入れする荷物を選択したときの利益を求めよ。

制約条件

n≦500

0≦in[i]<out[i]<2*n

w[i], s[i], S≦1000

v[i]≦10^6

続きを読む