秋分コンテスト感想 (2020/09/22)
#秋分コンテスト 感想
A:うんうん。は？
B:なるほどね～
C:絵絵～～～
D:国語の問題
E:国語の問題
F:
G:くそなぞなぞ常連勢が強すぎる
H:古代人が多すぎる
I:翻訳こんにゃく～
J:まともだと思ってたらジャッジ壊れてたみたいで草
K:強欲に88 どうだ？
L:これびっくりしたな～
M:I don't like this
N:草
O:シイークアシャーは最早シークヮーサーではない
P:インドア派なので...
Q:インドア派なので...
R:インドア派なので...
S:これ好き C++死亡
T:w
U:絵絵～
V:heno239を出力したら「出力形式ぐらい守れや」ってジャッジに怒られて爆笑した(ボーナス10点もらえた)
W:甲骨文字の知識が増えました、やったー
X:やばそ～
Y:言い忘れないで！！！
Z:なんかキング消滅してる盤面あるけど何事？
[:Yesって出したのに100点くれなかった...
\:？？？
]:OEISひっぱってちょっと数字いじったらなんか通った
^:めっちゃ大変そう
_:突然マラソンを始めるな
':OOOOOOOOOOOOOO@@@@@@OOOOO
a:7番の「いのうただたか」と8番の「うみ」の両方がACなのを見てこの世界の理、予想を裏切る無秩序さ、エスパーのさらに上を超えていくエスパーエスパーの波動を感じた
WUPC2020参加記
参加しました。
-
結果
優勝しました。
-
問題ごとの感想
- A:特になし(1m)
- B:特になし(5m)
- C:ちょっと悩んだ、A_{i+1}-A_iの正負がそれぞれ独立になるんだなあ(11m)
- E:数学,いつもの約数をいじるやつ(15m)
- F:2^iの倍数のうちx以下の最大のものがmaxの候補なんですね～(4m)
- G:GはDPのG(5m)
- M:伝家の宝刀 全方位木DP(5m)
- J:これきれいで好き(6m)
- L:コンテスト直前に https://yukicoder.me/problems/no/344 を解いたばっかりだったので一瞬だった... (12m)
- I:これ結構好きかも。bitごとに分けて、最終値が0になるための条件がかなりシンプルにかけて楽しかった (8m)
- D:数学,bsgsを使ったらTLEしちゃった(N<=10^7を見て察しましょう)(28m)
- K:これ結構すき、点対称に相手の真似するのって楽しいよね。(はじめ1<=x<=zをz<=xに勘違いして2WAしちゃった) (28m)
- H:伝家の宝刀 全方位木DP 2nd season 証明どうやるんだろ (57m)
-
おわりに
出題者の皆さんありがとうございました！
技術室奥プログラミングコンテスト#5 Day1 感想
-
コンテストリンク
https://yukicoder.me/contests/284
-
問題ごとの感想
- 【A問題】A問題のwriterであるkaageさんをそのまま提出しました。★1(というかエイプリルフール的問題？)
- 【B問題】連続するa_i!=b_iをまとめてひっくり返すのを繰り返します。★1.5
- 【C問題】L=1のとき2^N-1になるのは知識の問題。L>1でもNを(N+L-1)/LにすればL=1に帰着できる(?未証明)。結構困惑したので★2
- 【D問題】3桁以上の時、各桁は0か3か6か9でないといけない。2桁以下の場合は3の倍数かどうかを全探索、3桁以上の場合は{0,3,6,9}の4通りを10桁分全探索(計算量4^10)。★1.5で投票したけど沼に落ちるとつらそう(?)
- 【E問題】はじめなぜかM<=10^9に見えて時間をロスしてしまった。列を左からみるとN*1(たて)を1個おくか、1*N(よこ)をN個おくかになるので、後者の数を全探索すると、あとはコンビネーションで解ける。★2
- 【F問題】「Dの倍数」という条件がなければシンプルな二分探索、あったとしてもN未満の数字xについてはx か x-1のどちらかはDの倍数ではないので、判定をxとx+1両方で行うと二分探索できる。★2
- 【G問題】LIS祭りって感じ。一昔前なら★3とかになるかもしれないけど、かなり典型になってしまったので★2かなあ。
- 【H問題】かなり戸惑った。同じ数字を2度以上使うことはないので、長さNの数列を長さ1024に数列(i番目には数字iが何回与えられる数列に存在するかを持つ)に圧縮し、dp[i][j]:=(今までのxorがi,今までとった個数がj個)のdpを遷移させた。B=MAX{A}とおくと、計算量はO(B^2logB)。★2.5
- 【I問題】辺を行って戻ってを繰り返せば2の倍数は楽に稼げるので、各頂点では{スタート/ゴール}から{偶/奇}数回でくるときの最短路を求めればよく、頂点倍化してdfsで求めた。★2.5
- 【J問題】A=0が無いのが救い。昇順で条件を満たすものの個数を数え上げてN!倍すればよい。最小値をiに固定すると、(S_{i+1}-S_i)の合計をD=min(M,i+B)-N*(A-1)以下に抑える問題になり、この値は(D+N-1,N-1)。★3
- 【K問題】これかなり良い問題だと思う。-1となるケースは文字列Sが文字列Tの部分列となるケース。そうでないとき、貪欲に小さいものをとり、それを取った後にちゃんと条件を満たす文字列が作れるかを判定したくなる。判定の具体例として、S=ba??,T=a???のときに1文字目にaをとったとする。このときSの後ろの??がTの後ろの???の部分列になっているようでは、条件を満たすような文字列が作れなくなる。これを一般化すると、結局判定パートではSのあるsuffixがTのあるsuffixの部分列になるかどうかが必要になる。これはSを後から見ていって、「TのsuffixでSの現在のsuffixを部分列に持つ」ものの中の最小値を更新していくと、判定できるようになる。★3.5
- 【L問題】期待値の線形性を使って丁寧に数え上げる。★3
- 【M問題】辺に登場しないところはA_i=iのまま。そうでないところは、いくつかの辺を伝っていくことができる頂点のうち最大値にする。これは愚直にやるとO(M^2)だが、SCCを使うとO(M)でできる。★3
- 【N問題】通称挿入DP。DP[i][j]:=i番目のアルファベットまで見てj個アルファベットがある場合の数とすると、DP[i+1][j+k]+=DP[i][j]*(j+k)!/(j!*k!)という遷移になり、畳み込みの形になる。2894msでかなりTLが危なかった。★3.5
- 【O問題】構文解析やるだけ。演算の順序等がややこしくバグりやすいので★3.5
- 【P問題】オンラインで重心分解をしよう！★4
-
全体的な感想
ノーペナかつ爆速という最高のパフォーマンスでうれしい。
day2も楽しみ。
チーム(嘘)練 2020/08/11
-
セット
https://codeforces.com/gym/102253
-
結果
-
問題感想
- A log10(2^M)=Mlog10(2)
- B 各アルファベットについて係数をbase26で計算する。なぜか0-leadingがOKだと誤解して3WA。問題文はちゃんと読もう！
- C なんか見たことある、dfsでほい
- D みてない
- E みてない
- F サイクルごとに分解していい感じに数えよう！
- G みてない
- H いい感じにブロックごとに分割すると手元では通るのにTLEしまくる。よく見ると与えられた乱数生成関数はほとんど乱数ではあるが、なんとA=B=C=0の時だけ0しか返さない。は？？？
- I サイクルごとに分割すると、ベクトル列が複数個与えられ、各ベクトルから1つとった総和のうち、i番目(1<=i<=K)に小さいものを求める問題になる。値を小さい順に見ていくと、いい感じ(説明が文字で書くのが大変)に枝刈りできてO(NK)になる。ところでこの問題、sum_{K}<=10^6しか制約がないけど、K=1,N=1000が10^6個飛んで来たら入力10^9個になって破滅するんだけど...]
- J 終了20分前までa_1<...<a_nを見落とし続けた。まあ解けないんですけどね(敗北)
- K 算数
- L 分割統治チックにやります
なんか全体的に質高かった、沼ったところ全部自分の注意不足だし
-
反省点
- 一人だと全問題読む/考える暇がないので3人に分裂するべきだった
- BとJで2度誤読/読み落とししてる、ちゃんと注意深く読んでくれ
- コンテスト中にキレない(主にH)
動的 (online) Z_algorithm 覚え書き
-
Z_algorithmとは
長さnの文字列Sに対し、次のような数列{a_i}{0<=i<n}をO(n)で構築できる:
・S_iをSのi番目以降からなる文字列としたとき、SとS_iの最大共通接頭辞の長さがa_i
世界中で説明されてると思うので、ここでは詳しく触れません
-
動的
計算量にlogを1つ増やすことで動的にすることができます。(普通に線形で出来ます。)
具体的には、「後ろへの文字の追加」と「現在のa_iの値を出力する」などができます(文字の変更は厳しい)。
-
やり方
以下、「iが条件を満たす」とは「S_iがSのprefixとなる」ことを表すことにします。
step1. 現在の文字列の長さをnとしたとき、条件を満たすiの集合Aと、そうでない集合Bを分ける。
step2. 一度Bに入ったものは二度とBから出てこない。AからBに移動する、すなわち新しい文字の追加によって条件を満たさなくなるようなiの集合を高速に求めたい。
(以下、便宜上i=0はAに含まないことにします。)
step3. まず、Aに属するもののうち、新文字の追加後もiが条件を満たすような最小のiを求める。(後述の実装例のLine 25~31にあたる。)
step4. step3で求めた最小のiをxとする(存在しなければstep4は不要)。
いま、x<iを満たすi∈Aで、新文字追加後に条件を満たさなくなるiを求めたい。
ここで、S_xはSのprefixであることから、(Sの長さをlenとすると)求めたいiの集合というのは、Sのlen-x-1番目の文字を追加したときにAから削除したiの集合と一致する。(
例.
ababcababにcを追加するとき、追加前はAに{5(abab),7(ab)}が含まれている。ababcはababcababcのprefixになるので、step3でx=5になる。
ここで新7(abc)がababcababcのprefixになるかのcheckが必要だが、このcheckは新7(abc)が新x=5(ababc)のprefixになるかのcheckとまったく同じ。
そして新7が新5のprefixになるかどうかのcheckは、5文字さかのぼった時代(ababcの時代)の旧2(abc)が旧0(ababc)のprefixになるかどうかのcheckと同じ。
したがって、ababcの時代にcheckでダメになった旧2(abc)を呼び起こすことで、現代でも新7(abc)がダメになることがわかる。
)
こんな感じで、ダメになるものたちを(過去の記憶を呼び起こすことで)列挙できる。
step4は、実装例のLine 32~37と、del関数で行っている処理に該当する。
-
実装例
-
実装例(追記)
普通にlogつけずにできます。
-
verify
https://judge.yosupo.jp/submission/14910
-
例題
https://codeforces.com/gym/102341/problem/K
-
参考文献
https://gist.github.com/snuke/84ca11fc3f1ab109a3d30a006afcfa1b
-
虚無枠
いかがでたしか？
Topcoderで黄色になるまでにしたこと
https://tempura0224.hatenablog.com/entry/2019/01/16/045208 を読む。
たくさん質問する。
topcoder初めてなんですが注意点とかってありますか
— heno (@heno_code) 2020年3月7日
入出力わからない
— heno (@heno_code) 2020年3月7日
とりあえず前回のDiv2に提出して180pt得たと言われたんだけど、これはsystem testを通過したという認識でいいの？
— heno (@heno_code) 2020年3月7日
今の時間は間休憩という認識？
— heno (@heno_code) 2020年3月7日
チャレンジってシステムはコドフォと同じような感じ？
— heno (@heno_code) 2020年3月7日
皆さんのおかげで今の僕があります。ありがとうございます。
初参加のDiv2で優勝する。
Heno World! チーム練習 2020年2月12日
-
コンテストページ
https://codeforces.com/gym/102428
-
コンテスト中のムーブ
てんぷら不在でスタート。
[0:06]テンプレートを書き、MをAC.
やむなくがEを解けたらしいので任せる。
この間にLを考察終了し、Iを読み始める.
[0:16]やむなくに完全に任せたEがAC.
[0:21]LをAC.
解かれてる問題どころか読まれてる問題がほとんど無い。2人と3人の違いを痛感___
[0:40]英語力不足でIの読解に100年かかるが、AC.
ここでGをパスされる。Gの解法がSAを利用すること以外思いつかないのにめちゃくちゃ通されてて泣く。
[0:50ぐらい]てんぷら起床、参戦
このあたりで、GとKを交互に実装するような感じになる。
[1:07]KがACされる.
[1:08]結局SAを使ってGをAC.
Dの解法をやむなくから共有される。
偏角sortしてmaxとminがπ以内であればいいのはわかるが、円環上になっているので判定が少し厄介。そこで、[0,pi/2),[pi/2,pi),[pi,3pi/2),[3pi/2,2pi)のそれぞれの区間で一番小さいやつを取ってきて、そこから反時計回りにpi以内に全点が載っているかを調べた。
ということがあって、
[1:32]DをAC.
[1:46]数え上げキラーがFをAC.
[2:04]CをAC.
ここから椅子温めコンが開幕する。
Aが全然わからず、貪欲を投げては落ちるを繰り返す...
[3:48]Aに諦めが付く。
[4:00ぐらい]Hの考察が終わる。同時期にJの考察が終わっているらしい。Aの新しいエスパー解を生み出す。
今まですっからかんだった実装キューに突然3つの刺客が。どうしてこうなった...
遷移を詰め切れていなかったので、先にJを書いてもらう。
[4:28]Jが通る。
[5:00]コンテスト終了
[5:11]Hが通る。惜しい...
-
反省点
正当性も無いのにAに執着してはいけない
てんぷらの家に凸して起こすべきだった
-
おまけ(Hの解法)
dp[x][y][c]を、過去の自分の点がx点、相手の点がy点、このターンで自分がc点稼いでいる時の勝率、と定義します。こうすると、dpの遷移は、
dp[x][y][c]=max(val1,val2).
-----------------------------------------------------------
ただし、
//holdするとき
val1=1-dp[y][x+c][0]
//continueするとき
val2=0;
//1の目
val2+=(1-dp[y][x][0])/6.0
//それ以外の目(adと置く)
for(int ad=2;ad<=6;ad++){
if(x+ad+c>75)val2+=(1-dp[y][x][0])/6.0
else val2+=dp[x][y][c+ad]/6.0
}
----------------------------------------------------------
さて、この遷移をdfs等でやろうとすると、自分に帰ってきて循環してしまいます。
まず、dp[x][y][c]の遷移先にはdp[y][x][0]とdp[x][y][c+なんか]の形だけが登場し、dp[y][x][c]の遷移先にはdp[x][y][0]とdp[y][x][c+なんか]の形だけが登場することをふまえると、dp[x][y][~]とdp[y][x][~]を同時に考えたくなります。
ここで、次のような工夫をします。
1.x+yの大きい順に見る
これをすると、遷移部分のdp[x][y+c][0]やdp[y][x+c][0]は既に計算されていることになり、定数と考えてよくなります。
x==yとx!=yで場合分けします。
2.x==yのとき。dp[x][x][0]の値を二分探索する。
dp[x][x][0]の値を決めつけた時、先ほどの遷移を用いると、dp[x][x][0]の値が再計算できます。しかもこの再計算した値は、dp[x][x][0]の正しい値に近づくはずなので、例えば決めつけた値よりも再計算した値の方が大きい場合、正しい値は決めつけた値よりも大きくなります。
3.x!=yのとき。dp[y][x][0]の値を二分探索する。
上の場合とほとんど同じです。dp[y][x][0]の値を決め付けると、先ほどの遷移から、まずdp[x][y][0]の値が計算できます.このdp[x][y][0]の値を用いるとdp[y][x][0]の値が再計算できるので、あとは上と同じ理屈です。
以上により、全状態の確率が列挙できるので、クエリへの回答はholdの場合とcontinueの場合の確率をそれぞれ計算すればよいです。
(本番の実装では、c+x==74,c+x==75の場合だけ分けました。)
