裏紙

ほぼ競プロ、たまに日記

2018/4 solved(2)

4/16 AOJ 1312 - Where's Wally 2次元ロリハのverify(submission)。 CF 938 A - Word Correction 4/17 CF 938 B - Run For Your Prize CF 938 C - Constructing Tests 4/18 CF 938 D - Buy a Ticket 初めに初期値を全部突っ込んでおいてdijkstraする。dijkst…

CF 938 F - Erasing Substrings

問題 Problem - F - Codeforces 問題概要 英小文字のみで構成された長さの文字列がある。これに対して、回目の操作では長さのの連続する部分列を切り取り、残った部分を連結してとする、ということをがなくなってしまう直前まで行う(つまり回数をとすると、)…

2018/4 solved(1)

4/1 AOJ 2326 - Number Sorting dp[i] := iがsubsetの中で最大になるような適切な選び方は何通りあるかを計算する。このとき、文字列でソートされた順でiを処理していくと、i未満の部分のdpの和を取ることでdp[i]の値を得ることが出来るので、部分和を高速に…

CF 958 E3 - Guard Duty (hard)

問題 Problem - E3 - Codeforces 問題概要 個の白い点と個の黒い点の座標が与えられるので、完全二部マッチングをつくりたい。マッチングさせた者同士を線分で結ぶ時に、その線分が交差しないような割り当て方を答えよ。 2点が同じ位置にある・3点が同じ直線…

AOJ 2720 - Identity Function

問題 Identity Function | Aizu Online Judge 問題概要 1より大きい整数が与えられる。次のような関数を考える: この時、のについてが成り立つような最小のを求めよ。このようなが存在しない時は、-1を出力せよ。 アイデア まず、考察したこととしては、が…

2018/3 solved(2)

3/16 yukicoder No.235 - めぐるはめぐる (5) HL分解を使って解く。そこよりもどういうSegmentTreeを作るかに時間がかかった。区間Addをするが、そのAddに頂点ごとに異なる係数がかかるので、一様にAddできない、どうしようってなった。ただ、区間sumを求め…

CF 822 E - Liar

問題 Problem - E - Codeforces 問題概要 長さの文字列と長さの文字列が与えられる。をいくつかの部分文字列に分解して、その中から任意の個数を選んで順序を崩さないように結合させる。その結合させた文字列をと一致させるために、できるだけ結合の数減らし…

CF 940 F - Machine Learning

問題 Problem - F - Codeforces 問題概要 長さの数列がある。次のようなクエリを考える: クエリ 1 : 区間について、数字が現れる回数をとして、集合のmexを答える。 クエリ 2 : の値をに変更する。 以上のクエリが合計で個与えられるので、順に処理せよ。 …

2018/3 solved(1)

3/1 CF #411(Div.1) Virtual ABCの3完。Cの解釈に時間掛けすぎたけど、木という条件を利用することでクリークがそれ以上大きくならないというふうに考えることができ、色は貪欲に決まる。Dも途中までは考察できてたので、Dは解説見ずに通したい。 3/2 3/3 3/…

2018/2 solved(2)

2/15 imulan.hatenablog.jp CF #416(Div.2) Virtual ABCDの4完。Bはちゃんと愚直ソートを殺すケースが入っていた(ひっかかった)。 2/16 imulan.hatenablog.jp CF 895 D - String Mark それぞれの文字列a,bに対して、strictlyに辞書順で小さいaのpermutation…

CF 809 C - Find a car

問題 Problem - C - Codeforces 問題概要 のグリッドがある。上から行目、左から列目のセルをと表す()。各グリッドには、条件に従って数字が書き込まれている。その条件とは、 に書き込むのは、このマスより左側一直線()と上側一直線()の中に現れていない正…

CF 813 E - Army Creation

問題 Problem - E - Codeforces 問題概要 長さの数列と整数が与えられる。次のようなクエリが個与えられるので、それに答えよ: クエリ : 区間 について、同じ値は個までしか選べない時に、最大で何個まで選べるか (問題を読んでもらうと分かるが、オンライ…

CF 712 E - Memory and Casinos

問題 Problem - E - Codeforces 問題概要 個のカジノが一列に並んでいる(左から番目のカジノをカジノと呼ぶ)。カジノで遊んだ時に、勝つと1つ右に移動する。このときに勝つ確率はである。負けると1つ左に移動する(勝率は)。番目の左側と番目の右側は出口であ…

CF 811 E - Vladik and Entertaining Flags

問題 Problem - E - Codeforces 問題概要 のグリッドがあり、各セルに数字がかかれている。グリッドの美しさを、連結成分の個数と定義する(同じ数字かつ上下左右のいずれかで触れていれば連結とする)。 クエリ: グリッドの左端を、右端をで切った時に残る部…

CF 835 F - Roads in the Kingdom

問題 Problem - F - Codeforces 問題概要 頂点辺の無向グラフが与えられる。辺は頂点とを結ぶ長さの辺である。 このグラフのinconvenienceを、「全ての頂点対の最短路のmax」と定義することにする。 このグラフから連結性を保ちつつ1つだけ辺を取り除く時の…

2018/2 solved(1)

2/1 imulan.hatenablog.jp 2/2 CF 894 A - QAQ CF 894 B - Ralph And His Magic Field よくわからなかったけど、実験してみると規則性があったのでそれを実装した。 考え方としては、まず全てのセルには1か-1しか置くことが出来ない。その上で、k=-1のとき、…

CF 877 F - Ann and Books

問題 Problem - F - Codeforces 問題概要 長さの数列と整数が与えられる。クエリ:「閉区間内の連続部分列で、その和がになるものの個数を答える」が個与えられるのでそれぞれに答えよ。 アイデア prefix sumを使えば、ある区間の和はで取ることが出来る。以…

CF 900 D - Unusual Sequences

問題 Problem - D - Codeforces 問題概要 数列について、かつを満たすような数列が何種類存在するか、で割った余りを求めよ。 アイデア まず、数列の全てのgcdがであるということは、数列の全ての要素はの倍数であるということになる。よってその和もの倍数…

2018/1 solved(2)

1/17 ARC 083 C - Sugar Water 水の量と砂糖の量を全探索する。砂糖の量は、bool配列などにその量が作れるかを持っておけば計算量的にOK(submission)。 ARC 083 D - Restoring Road Network Warshall-Floyd法によって、最短距離を計算して、入力と一致するか…

CF 909 F - AND-permutations

問題 Problem - F - Codeforces 問題概要 長さの順列がそれぞれあるかどうかを判定し、ある場合はその具体例を1つ示せ。 全てのについて、かつであるような順列 全てのについて、かつであるような順列 (ANDはbitwise and(C++でいう&演算子)) アイデア pにつ…

Codechef January Challenge 2018 - Killing Monsters

問題 Contest Page | CodeChef 問題概要 モンスターが体いて、それぞれにからまでのIDが振られている。のIDを振られているモンスターは、はじめ体力がある。次のようなクエリが個来る: クエリ : k & x = kを満たすについて、のIDを振られているモンスターの…

CF 847 L - Berland SU Computer Network

問題 Problem - L - Codeforces 問題概要 台のルータがあり、何台かはコードで繋がれており、ネットワークを構成している。ルータの構造は木である。次のような情報が与えられるので、元のネットワークの構造を復元せよ: それぞれのコードとと直接繋がって…

2018/1 solved(1)

一昨年やってたのを復活させます。去年は「これあんまり意味ないかもなあ、もっとちゃんと解説書く問題を増やしたほうがいいでしょ」と思ったが、辞めた結果そもそも解説書く問題が減った(ダメ)。他人に読んでもらうことは特に意識せず書きます。 1/1 AOJ 20…

yukicoder No.584 - 赤、緑、青の色塗り

問題 No.584 赤、緑、青の色塗り - yukicoder 問題概要 一直線にNマスが並んでいる。各マスを赤、緑、青いずれかの色で塗ることが出来る。塗らないマスがあっても良い。マスを塗る条件として、 同じ色は隣接してはいけない 異なる色であれば連続する2マスを…

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回反転される…