Senです。(Twitter: @Sen, Atcoder: Sen, AOJ: Sen, Codeforces: Sen_cdfo)大学に入って1年たちました。2019年での自分のやったことを簡単に振り返ります。 1,2,3月 センター試験爆死からの二次試験爆死は新春福袋です。早稲田大学基幹理工学部学系3への進学…

atcoder.jp 概要 サイズNの木が与えられる。それぞれの頂点を1/2の確率で白、1/2の確率で黒と塗る。 黒で塗られた頂点をすべて含む最小部分木を考える。その最小部分木のサイズの期待値を求めよ。制約： 1

atcoder.jp 概要 N * Nのフィールド上に、1*2のサイズのドミノを1枚以上、任意の枚数置く。回転させてもいいが、ドミノ同士は重なってはいけない。 この時、ある行or列について、その上に乗ってるドミノの数をxとする。すべての行と列について、その上に乗っ…

突然ですが次のタイプの問題、見おぼえありますか？ N*Nの行列がある。すべての行と列において、○○という条件を満たす(もしくは行が○○という条件、列が××という条件を満たす)ように、そのN*Nの行列を構築せよ。構築不能なら-1を出力せよ。 トラウマ要素重め…

codeforces.com 概要 n行m列の行列がある。それからa行b列の部分行列を切り出す。(n-a+1) * (m-b+1)個できる。部分行列の項の最小値の和を(n-a+1)*(m-b+1)個分足した値を答えよ。 ただし、n行m列の行列はとして、である。制約: 1 ACするまで 1. 与式で構築さ…

codeforces.com 概要 32bitのIPアドレスがN個与えられる。それぞれのアドレスには、悪いと良いがある。悪いアドレスは必ずブロックし、よいアドレスは必ず通す。何もないアドレスは、通すことにする。 ところで、サブネットというのを定める。192.168.0.1/8…

codeforces.comこのセットの日本語での解説です。足りない問題は時間ができたら埋めます。 A dpでやるかと思ったらこれ順序わからない。順序がわからないDPっぽい遷移はグラフと相場が決まってる。結局グラフの最短路でやる。でもやる際はよくよく考えると辺…

codeforces.com 概要 n個の仕事がある。整数m, x, tがありこれらの仕事を前から順に次のルールで行う。 かかる時間がx以下ならば行う。そうでないなら飛ばす。 mこの仕事を終えたら、そのmこの仕事にかかった時間のぶんだけ休む。 時間がtをぎりぎり超えない…

codeforces.com 概要 nとその約数のmが与えられる。n個のa_iから成る数列も与えられる。 1回の操作で数列の要素を1増やすことができる。 あなたは、mで割ったあまりが0, 1, 2, ..., m-1となるものの個数がすべてn/mになるようにしたい。最低の操作回数とその…

codeforces.com 概要 N日の間、K個の飴を毎日食べたい。近所の菓子屋にはM種類の飴があり、それぞれ[l_i, r_i]日の間に、毎日最大で1つあたりの値段p_i円でc_i個まで売っている。 あなたは、いい感じに購入して毎日K個の飴を食べたい。もしその日に売られて…

codeforces.com 概要 城がNつある。あなたははじめ、K人の戦士を従えて、これを攻略していく。 城には戦力a_i, 補充兵士b_i, 戦略的価値c_iがそれぞれある。城を攻略するには、現在の従えてる戦士がa_i以上である必要がある。城の攻略に成功すると、戦士の数…

codeforces.com 概要 '('と')'のみが含まれる文字列S, Tが与えられる。次の条件を満たす文字列Xを構成してください。 SとTはどちらもXの部分文字列である。 Xはかっこ列としてすべての'(' と ')' は対応されていて、かつその2文字からのみ成る。 Xの長さはあ…

codeforces.com 概要 長さnの数列が与えられる。それぞれの要素a_i(1 さて、すべての1 不能なら"-1"と出力せよ。制約：1

前編の読了お疲れさまでした。形式的べき級数でいくつかの数え上げを解決して、残るは数え上げの難関の3つの数(僕呼び)の、スターリング数、ベル数、分割数のみです。この三つの数はいずれも一般的な場合では漸化式を使わない式で表せません。今回の記事では…

codeforces.com 概要 t個の文字列が与えられる。それぞれの文字列は'a', 'b', 'c', '?'で構成されてる。各文字列に対して、'?'は'a' or 'b' or 'c'にすることができる。それぞれの文字列の’?’をうまく差し替えた時、同じ文字が隣り合わないような文字列の差…

先日、競プロやってたらhotmanから「形式的べき級数と数え上げの相性が抜群すぎてつながってて気持ちいい、世の中の眠る真理が目覚めた気がする」といわれて、気になったのでまとめた。 この記事は、数学的厳密性に欠けています。多くの変形が厳密な確認をな…

codeforces.com 概要 無限に長い配列がある。カーソルが存在していて、最初は1文字目を指す。 あなたはつぎのような操作を行える カーソルを一つ右に動かす。 カーソルを一つ左に動かす。ただし、一番左ならば何も起きない。 カーソルの指してる配列の文字を…

atcoder.jp 概要 N人の人が並んでいて、それぞれが赤、緑、青の帽子をかぶってる。i番目の人が自分より前で、自分と同じ色の人がそれぞれA_i人いるという。この状況で全体的にありうる並びの場合の数はいくつか？