2019-01-01から1年間の記事一覧
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人いるという。この状況で全体的にありうる並びの場合の数はいくつか?
atcoder.jp 概要 数直線があり、最初に高橋くんは0にいる。青木くんは、N(区間を持っていて、次のようなことをN回行える。 区間を一つ選び、高橋君はその区間内に入るように移動する。これに一回使われた区間はもう二度と使えない。 N回の操作後、高橋君は数…
atcoder.jp 概要 H * W (H, W ハンコも白紙も1*1のサイズに分割されていて、ハンコはそれぞれのマスごとに黒or白がある。 白紙は一度ハンコが押されて、その時点のマスが黒となったのならば、そのマスはずっと黒となる。 左上から右下まで、押せる場所を全部…
atcoder.jp 概要 偶数長'(', ')'からのみなる列(size 今カーソルは一番左を指している。コスト1を使って、次の操作のうちのいずれかを行える。 カーソルを左右に動かす(動かせるなら)。 カーソルの指してる文字を変更する。'(' -> ')' とか ')' -> '(' であ…
atcoder.jp 概要 Nの長さを持つ数列がある。(N
atcoder.jp 概要 数字を与えられる。数字の隣接する二つの桁の数をそれぞれ、a, bとして、次の操作を行う。 aとbの2ケタをa+bで置き換える。 この操作を1回行うと、2751では例えば、951, 2121, 276のようになる。順番を工夫して操作をするとき、与えられた数…
atcoder.jp 概要 0からN(1 )まで、xずつ加算したい。はじめ、xは1である。最小の加算回数は?ただし、次の★の操作は任意回行ってよい。★ xをニコ数倍する。ニコ数とは、2 or 5からのみで構成されるかつ、同じ数字が隣り合わない数のことである。例えば、5, 2…
atcoder.jp 概要 ナップサック問題を解く。一つだけカバンに入れず持ち歩ける。個数は3000個まで、価値、重さはそれぞれ[1, 3000]、入れられる最大の重さは[1, 3000]。最大の価値は?
atcoder.jp 概要 最大10万長の数列が与えられる。この数列は和が10^5以下を満たす。 この数列の部分列のうち、XORしたらKになるのはなん通り存在するのか?
atcoder.jp 概要 太郎君は、H時M分S秒に寝ました。起きた時には、C1回秒針と分針が重なり、C2回分針と時針が重なった。この時、寝てる時間としてあり得るのは最低何分、最長何分でしょう?ありえない入力ならば-1と出力すること。 ただし、寝始めや寝起きの…
このブログでは、訪問者の皆様の情報を次のツールで使用しています。(はてなブログのデフォルトを除く) Google Analytics Google Analyticsを使って、訪問者の分析をしています。情報は本人を特定できないように匿名化されてますが、それでもいやだという方…
この記事は、競技プログラミングでよくあるグラフの問題で、愚直に問題文の指示通りやると辺の数があまりにも多くなりすぎるようなものに対して、コスト0の辺をうまく利用することで辺の数のオーダーを落とす者である。 性質上、すべてのものに適応できるわ…
atcoder.jp 概要 最大10^5個の頂点(それぞれ1~Nまで番号を振る)を持つ辺に次の最大10万個のqueryで無向辺を追加する。クエリ LとRとCを与えられる。を満たすすべての(a, b)の間にコストCの辺を張る。クエリを全部処理したのち、頂点1から頂点Nまでの最短経路…