gyouzasushi’s diary

競プロとか

今日の競プロ(2020/5/2) + AtCoder Beginner Contest 165

AtCoder : 1705 → 1755 (+50)

ABC165 A - We Love Golf

こういうのは変に算数せず、全探索

ABC165 B - 1%

最大ケースがサンプルにあって優しい。C++でやったらオーバーフローしてもうたからPythonでやった。

ABC165 C - Many Requirements

何言ってるかよくわからないけど、とりあえず $A$ が全探索できればよさそう。 $A$ として考えられる数列は、 $M$ 個のボールと $N-1$ 個の仕切りの並べ替えと考えて ${}_{N+M-1} C_{N-1}$ 通り。これは最大でも ${}_{19} C_{9}=92,378$ なので、いける。

実装も同じように、 $M$ 個のボールと $N-1$ 個の仕切り（に見立てた $M$ 個の $0$ と $N-1$ 個の $1$ ）をstd::next_permutationで回せばいける。

ABC165 D - Floor Function

$x$ を $B$ で割って $x=qB+r$ とすると、

$\begin{eqnarray} \lfloor \frac{Ax}{B} \rfloor - A \times \lfloor \frac{x}{B} \rfloor &=& \lfloor \frac{A(qB+r)}{B} \rfloor - A \times \lfloor \frac{qB+r}{B} \rfloor \\ &=& (Aq+\lfloor \frac{Ar}{B} \rfloor) - (Aq + \lfloor \frac{r}{B} \rfloor) \\ &=& \lfloor \frac{Ar}{B} \rfloor -\lfloor \frac{r}{B} \rfloor \end{eqnarray}$

$r \lt B$ だから $\lfloor \frac{r}{B} \rfloor=0$ で、結局

$\lfloor \frac{Ax}{B} \rfloor - A \times \lfloor \frac{x}{B} \rfloor=\lfloor \frac{Ar}{B} \rfloor$

これは単調非減少なので、できるだけ大きい $r\lt B$ をとればOK。

めっちゃ時間かけてもうた、割り算苦手すぎ。小学三年生の算数の授業でどれだけ苦労したことか…。

ABC165 E - Rotation Matching

パズル。

f:id:gyouzasushi:20200502235923p:plain

こうやると $M$ 個の対戦場に書かれた数字の差が全て異なるようになるので、同じ人と当たることもなくなる。

ABC165 F - LIS on Tree

DFSの順番で普通のLISと同じようにやればいける。DP配列を更新するときに更新前の値をメモしておいて、子から親に帰るときにDP配列の値を元に戻す。

今日の競プロ(2020/5/1) + Codeforces Round #638 (Div. 2)

Codeforces : 2014 → 2081 (+67)

Codeforces Round #570 (Div. 3) F - Topforces Strikes Back

三つのうち最大を決め打つと貪欲でいける。

$a_i$ の約数の個数は $a_i$ に比べてはるかに小さい
$a_i$ より小さい $a_i$ の約数は全部 $\frac{a_i}{2}$ 以下

がポイント。

JOI2014春合宿 M - ストラップ

端子の数でソートして、「 $dp[i][j]=i$ 個目までみて、端子の数が $j$ となるつけ方の嬉しさの最大値」。

yukicoder No.1040 垂直大学

yukicoder No.1041 直線大学

yukicoder No.1042 愚直大学

Desmosを睨んだら $N \geq 1$ で単調性がありそうに見えたので、信じて二分探索した。

yukicoder No.1043 直列大学

乾電池と豆電球それぞれについてナップザックDPしたあと、条件を満たす組み合わせを数え上げる。割り算が苦手すぎて一時間半くらいかけてもうた…。

Codeforces Round #638 (Div. 2) A - Phoenix and Balance

実験した。 $2^{\frac{n}{2}+1}-2$ 。

Codeforces Round #638 (Div. 2) B - Phoenix and Beauty

数列 $a$ を $k$ の周期をもつ数列にすることができれば十分。

Codeforces Round #638 (Div. 2) C - Phoenix and Distribution

$s$ はソートしておく。

$s_1 \neq s_k$ のとき

$s_1+s_{k+1}+s_{k+2}+\ldots+s_n, s_2, s_3,\ldots,s_k$ みたいにするのが最適で、答えは $s_k$ 。

$s_1 = s_k$ かつ $s_{k+1} \neq s_n$ のとき

このときも $s_1+s_{k+1}+s_{k+2}+\ldots+s_n, s_2, s_3,\ldots,s_k$ みたいにするのが最適。ただし答えは $s_1+s_{k+1}+s_{k+2}+\ldots+s_n$ 。

$s_1 = s_k$ かつ $s_{k+1}=s_n$ のとき

$s_{k+1}$ から $s_n$ までをできるだけ均等に使うのが最適。答えは $s_1+s_{k+1}*\lceil \frac{n-k}{k} \rceil$ 。

Codeforces Round #638 (Div. 2) D - Phoenix and Science

$1$ 個、 $2$ 個、 $4$ 個、 $8$ 個… みたいに殖えるのが最速。あまりは適当に調整できて、例えば $n=18$ なら $1,2,3,4,8$ 、 $n=25$ なら $1,2,4,8,10$ みたいな。

今日の競プロ(2020/4/30)

JOI2014春合宿 D - ラーメンの食べ比べ

std::minmax_element を知っていますか？僕は今日知りました！

Codeforces Round #570 (Div. 3) A - Nearest Interesting Number

Codeforces Round #570 (Div. 3) B - Equalize Prices

Codeforces Round #570 (Div. 3) C - Computer Game

🐓🐢

Codeforces Round #570 (Div. 3) D - Candy Box (easy version)

貪欲に〜〜

Codeforces Round #570 (Div. 3) E - Subsequences (easy version)

「 $S$ の部分文字列のうち、長さ $0$ から $n$ までのものがそれぞれいくつあるか」がわかればOK。部分文字列　数え上げ　で検索。

Codeforces Round #570 (Div. 3) G - Candy Box (hard version)

D と同じ要領でやればいけるはずが、Wrong answer on test 15 が一向になおらず…。

出力を空白区切りから改行区切りに変えたら通りました。なんで？

Codeforces Round #570 (Div. 3) H - Subsequences (hard version)

E に同じ。

今日の競プロ(2020/4/29)

JOI2013本選 2 - IOI 列車で行こう (Take the 'IOI' train)

「 $dp[i][j][k]=i$ 両目、 $j$ 両目を必ず使って、末尾の車両が $k$ であるような IOI 列車の長さの最大値」をする。

Codeforces Round #575 (Div. 3) A - Three Piles of Candies

Codeforces Round #575 (Div. 3) B - Odd Sum Segments

Codeforces Round #575 (Div. 3) C - Robot Breakout

Codeforces Round #575 (Div. 3) D2 - RGB Substring (hard version)

RGBRGB..., GBRGBR..., BRGBRG..., 全部試す

Codeforces Round #575 (Div. 3) E - Connected Component on a Chessboard

f:id:gyouzasushi:20200429230644p:plain

（ $b \geq w$ のとき）これより偏ってたらアウト、そうじゃなかったら周りの黒を適宜削れば構築できる。

$b \lt w$ のときも白黒入れ替えたら同じ。

Codeforces Round #575 (Div. 3) F - K-th Path

$k$ 番目に短いパスに含まれうるのは短い方から $k$ 本の辺だけなので、短い方から $k$ 本の辺だけのグラフで Warshall–Floyd すればいける。

コメント

f:id:gyouzasushi:20200429231607p:plain

Div.3 バチャ全完はじめてでめっちゃ嬉しい。

今日の競プロ(2020/4/28)

Codeforces Round #582 (Div. 3) F - Unstable String Sort

昨日の残り。なんか微妙に問題を勘違いしてて、

3 2

3 1 2

3 2 1

が YES なんが理解できんくてちょっと苦しんだ。

JOI2013予選 E - 魚の生息範囲 (Fish)

座標圧縮〜〜〜

Codeforces Round #579 (Div. 3) A - Circle of Students

Codeforces Round #579 (Div. 3) B - Equal Rectangles

Codeforces Round #579 (Div. 3) C - Common Divisors

Codeforces Round #579 (Div. 3) D2 - Remove the Substring (hard version)

Yutori とちょっと似た発想？これすぐ解けたん嬉しい。

Codeforces Round #579 (Div. 3) E - Boxers

これの上位互換みたいなやつこの前 Div.3 で見たな。典型なんかな？

Codeforces Round #579 (Div. 3) F2 - Complete the Projects (hard version)

解説AC。めちゃくちゃ勉強になった…。

とりあえず二つを入れ替えたらどうなるかを考えるところから始める！

今日の競プロ(2020/4/27)

JOI2011本選 C - JOI 国の買い物事情 (Shopping in JOI Kingdom)

昨日の今日でまたちょっと変わった Dijkstra やった。今日はちゃんと解けた！昨日の反省を活かしすぎ。

四捨五入難しいね。

Codeforces Round #582 (Div. 3) A - Chips Moving

Codeforces Round #582 (Div. 3) B - Bad Prices

やや難読

Codeforces Round #582 (Div. 3) C - Book Reading

Codeforces Round #582 (Div. 3) D2 - Equalizing by Division (hard version)

小さい方から使う。めっちゃ時間かけてもうた…。

Codeforces Round #582 (Div. 3) G - Path Queries

E, F より解かれてたから先にやった。

これです。好き

Codeforces Round #582 (Div. 3) E - Two Small Strings

場合分け。

今日の競プロ(2020/4/26) + AtCoder Beginner Contest 164 + Educational Codeforces Round 86

AtCoder : 1705 → 1705 (±0)
Codeforces : 1985 → 2014 (+29)

Codeforces Round #587 (Div. 3) A - Prefixes

Codeforces Round #587 (Div. 3) B - Shooting

Codeforces Round #587 (Div. 3) C - White Sheet

Codeforces Round #587 (Div. 3) D - Swords

Codeforces Round #587 (Div. 3) E2 - Numerical Sequence (hard version)

丁寧に数えていったら通る。苦行すぎる…。

Codeforces Round #587 (Div. 3) F - Wi-Fi

「 $dp1[i]=$ 部屋 $i$ までみたときのコストの最小値」、「 $dp2[i]=$ 部屋 $i$ までみて、部屋 $i$ に必ずルーターを設置するときのコストの最小値」をする。

ABC164 A - Sheep and Wolves

ABC164 B - Battle

cout << "NO" << endl;

で1WA。もったいな〜〜

ABC164 C - gacha

ABC164 D - Multiple of 2019

右端が一の位！右端が一の位！

ABC164 E - Two Currencies

（頂点, 銀貨の枚数）でDijkstra。これ解いときたかったなあ。

Educational Codeforces Round 86 A - Road To Zero

Educational Codeforces Round 86 B - Binary Period

Educational Codeforces Round 86 C - Yet Another Counting Problem

嫌いやけどがんばった。 $lcm(a,b)$ 周期で考える。

Educational Codeforces Round 86 D - Multiple Testcases

大きい方から貪欲に使っていく。実装はこれっぽい雰囲気？

Educational Codeforces Round 86 E - Placing Rooks

好き系。 $0 \lt k \lt n$ でそれぞれの行に一つずつルークを置くような場合だけを考えたらよくて、これは結局 $n$ 列のうちちょうど $n-k$ 列にルークを置く場合の数。
包除できてなくてコンテスト中には通せませんでした　え？