CPSCO2019参加記(1日目) - Tallfallの日記

こんにちは、まつかわです。

はにーまさんが参加記を読みたいと仰っていたのでブログを始めることにしました。

5/4 ~ 5/6 の3日間、はにーまさんの主催する競プロ合宿のCPSCO2019があったので

時系列に沿ってつらつらと書いていきます

参加前

大阪で競技プログラミングの勉強会があるとTLで見かけたので参加登録をしましたがレート帯的に色々考えました。強い人がその後めっちゃきたので考えるのをやめました。

1日目

割と早めに会場に着いて雑談をしていました、その後会場に入りましたが居心地がとても良さそうな空間だったのでテンションが上がりました()。

Session1

作問人(さくもんちゅ)はてんぷらさんでした、まだ黄色表記ですね。

全体的に難度勾配がなだらかでかつ教育的だったなぁと思います（これは全部の回でそうだけど特に）

問題名の頭文字には気づきませんでした。

問題文:

CPSCO2019 Session1

感想は使用言語に準拠してpythonで書きます。

A - Ajihon

N人を3人ずつのチームに分けるとき、A冊の鯵本を所有するチームを最大、最小化する問題

切り上げは-(-A//B)とかの形で書けます。mathからceil()とって来た方がバグらせないかもしれないですね

いかなごさんが解いてくれました。

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291010

B - Beautiful Harmony

令和問

文字列の出現回数の種類が１かの判定問題

出現回数ならCounter使っておくのが便利で、これはdictなのでvalues()をsetに入れて長さが1かどうかを見ます、pythonが輝きそうな類の問題。

いかなごさんが解いてくれました(2回目)

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291066

C - Coins

N(<=30)個のものからK個(<=6)選んでなんだかんだする ${}_nC_k$ 問題

てんぷらさんの解説の通り実装すると楽

（この記事を書いている時next_permutaionに引っ張っれてpermutaions()で書いてTLEしたのは内緒）

本番の担当は僕で、実装めんどいなぁとおもったら煎茶さんが再帰で書いてくれてpythonでTLEしたので唯一のc++ユーザのいかなごさんに書いてもらうことに

いかなごさんが解いてくれました(3回目)

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291556

D - Dessert Planning

mod = 10**9+7
print(8*pow(5, int(input())-1, mod)%mod)

おわり。

真面目に書くと

煎茶さん担当でした、dpはすぐに思いつきたい問題で、ケーキを食べて終わる通り数とそれ以外のを持つと遷移が

$\begin{pmatrix} dp_{cake}[i+1] \\ dp_{other}[i+1] \end{pmatrix} = \begin{pmatrix} 2 &3 \\ 6 &5\end{pmatrix}\begin{pmatrix} dp_{cake}[i] \\ dp_{other}[i] \end{pmatrix}$

となって結局求めたいのは $\{dp_{cake}[n] + dp_{other}[n]\}$ なのでこれのi項目を $dp_{tot}[i]$ とおくと $dp_{tot}[i+1] = 8dp_{tot}[i]$ となります。

提出(いる？):

https://atcoder.jp/contests/cpsco2019-s1/submissions/5291698

Ｅ

pythonの標準ライブラリにc++のsetをくれ(言語選択で敗北)

19/05/31追記
BIT上の二分探索すると通るようです
オフラインクエリのset実装 - Tallfallの日記

F - Fruits in Season

特徴量に対して単調に範囲が増加する部分列に対する問題。

最小値の最大化なので二分探索は筆頭候補に出て、それでなんか行けそうなので見ていくと判定パートは1~Nがそれぞれ別の部分列に含まれるようにできるかどうか？みたいな感じになります。この判定が多分本質パートで類題の解法から終点か始点ソートかなーとは考えてたんですけどheapqに終点を順次入れることに思い至るまで少し時間をかけすぎた気がします。で、思いついたら結局日経コンのＤ

https://atcoder.jp/contests/nikkei2019-final/tasks/nikkei2019_final_d

のpython解と同じじゃーんってなったので復習不足を感じました。（自分はセグ木の伝播を最後だけするようにして通してた）

なお範囲を決めるところ（算数）をバグらせて通ったのは終了3分後でした（は？？？？）

二分探索は判定を関数化した方がよさそう。

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/me

G - Game with Division

部分点300その2

部分点解法が満点解法の愚直版になっている。

iゲーム目でXが始め書かれている時、それ以前はこれ以降影響しない(マルコフ過程的なイメージ）のでdpは解法候補として上の方になる。茶色とかの人がやると凄いいい感じの練習になりそう

満点は例えば貰うdpを考えたときもらうノードは $O(\sqrt{a})$ で抑えられるので何とか貰うノードに対して定数か $O(\log{n})$ くらいで処理を抑えたい、よく考えると同じiに配るノードは区間になっているのでSegtreeで高速化すると通ります(8TLEくらいした、前問でバグを防ぐためにceil, floorを使おうという意識が仇(?)になった、てんぷらさんはこれを予想していた....？)

本番ではFの実装詰まった時に気分転換で部分点を通しました、他の人にやってもらった方が合宿の目的には合っていたかもしれないですね、ただそれをするとレートチーム内で一番高かったのにもかかわらず何も通さない人になるのでやっちゃった(かわいい)

提出:

https://atcoder.jp/contests/cpsco2019-s1/submissions/5297662

H - Highest and Ends

コンテスト中は見てないです

部分点300その3

数列Aに対して $l \leq m \leq r$ 　かつ　 $A\lbrack l\rbrack + A\lbrack m\rbrack + A\lbrack r\rbrack = X$ 　かつ　 $max_{i \in\lbrack L, R\rbrack} = A\lbrack m\rbrack$ を満たすl, m, rを求める問題です