競プロ界隈の独特な雰囲気を醸し出す用語たちを独断と偏見で解説する。 #競プロの闇 何かあったら@nonpro3 までご一報ください。 あ行 う 笑[名] 「う し た ぷ に き あ 王 国 笑」の省略版。どうみても「笑う」のアナグラムだけど王国民には国名の略称に見…
atcoder.jp 概要 おかずがN種類ある。それぞれのおかずには糖分A[i]、塩分B[i]というパラメータがある。 あなたはおかずを何種類か選んで晩御飯と一緒に食べたい。この時、次の条件を満たすようにする必要がある。 選ばれたおかずが2つ以上存在するのなら、…
atcoder.jp 概要 Nが与えられる。最初がx=1で、高橋君と青木君が交互に次の操作のうちのどれかをする。先手は高橋。 xを2xにする。 xを2x+1にする。 自分の番で操作してNを超えたらその人の負け。Nが与えられるので、その時が誰が必勝なのかを答えてください…
はじめに KotlinのNull許容型について。(競プロメイン)C++erから見たKotlin勉強記録-1 型、基本制御文 - Senの競技プログラミング備忘録(競プロメイン)C++erから見たKotlin勉強記録-2 Array, List, 関数 - Senの競技プログラミング備忘録(競プロメイン)C++er…
はじめに Kotlinのクラス関係について。(競プロメイン)C++erから見たKotlin勉強記録-1 型、基本制御文 - Senの競技プログラミング備忘録(競プロメイン)C++erから見たKotlin勉強記録-2 Array, List, 関数 - Senの競技プログラミング備忘録(競プロメイン)C++er…
codeforces.com 概要 n_a, n_b, n_cと長さがn_aのa, n_bのb, n_cのcが与えられる。 aの中の1つの要素をx, bの中の1つの要素をy, cの中の1つの要素をzとする。を最小化せよ。制約： 1 ACするまで 1. 何か裏がありそうな式ではあるが、なんやかんやうまく全探…
www.hackerrank.com 概要 解法 パズル 海辺の20以上の4区(渋谷、新宿、千代田、中央)は1つしか使わない 端から攻めるがほとんど通用しない 頭を抱えたくなる局所最適解 強烈に自己主張されてる港区は使わない 全探索 BitDP 実装 統計＆講評 最後に 概要 東京…
はじめに KotlinのArray、List、関数、try-catch文について。(競プロメイン)C++erから見たKotlin勉強記録-1 型、基本制御文 - Senの競技プログラミング備忘録(競プロメイン)C++erから見たKotlin勉強記録-3 class - Senの競技プログラミング備忘録(競プロメイ…
はじめに これは三分の二、自分用の記事。競技ピログラミングでC++をメインで使ってる自分が、大学の文化祭のAndroidアプリ開発のためのKotlinの勉強記録を残す。sen-comp.hatenablog.com(競プロメイン)C++erから見たKotlin勉強記録-3 class - Senの競技プロ…
Problem - D - Codeforces atcoder.jp# ABC194 - F https://atcoder.jp/contests/abc194/tasks/abc194_f 実装重い桁DP 煩雑な実装をバグらせずに書けるのかな？ 必要だと思ったものは全動員しよう。自信を持とう。# Edfo103 - C https://codeforces.com/cont…
atcoder.jp 概要 長さNの文字列Sが与えられる。Q回の質問ごとに与えられるkについて、次の条件を満たすような(a, b, c)のセットの数を答えよ。 S[a]=='D', S[b]=='M', S[c]=='C' a c - a 制約： 1
atcoder.jp 概要 N個の要素からなる数列A[]で、floor(N/2)個の要素を選ぶ。ただし、選ばれたものは隣り合ってはならない。その和を最大化せよ。制約： 1 ACするまで 考察ノートを考察パートで載せる。 考察 僕の解法 これが本番中書いた考察ノート。(DPの実…
atcoder.jp 概要 N個のふりかけが売られていて、それぞれのふりかけの番号はA[i]でおいしさがB[i]である。あなたはKという整数を持っている。次の条件を満たすようにふりかけを選んだ時のおいしさの和の最大値を求めよ。K>=XのようなXがあり、えらばれたふり…
atcoder.jp 概要 Senくんのスケジュールが記された、長さNの文字列によってあらわされるスケジュール表が与えられる。i文字目が'o'なら働ける日、'x'なら働けない日である。 "ooxox"ならば、1, 2, 4日目にだけ働ける。 Senくんは怠惰なので、1日働いたら次に…
codeforces.com 概要 サイズNの木が与えられて、それぞれの頂点には重みがweight[i]だけ設定されている。 あなたは、この中から次の条件を満たすように、好きなだけ頂点を選べる。選んだ頂点たちの重みの総和の最大値を求めよ。 選んだ頂点たちはお互い距離…
codeforces.com 概要 サイズNの木が与えられる。根を頂点1とする。 次のようなM個のqueryに答えよ。 k個の頂点を与える。頂点1からある頂点vへ行くパスからの距離が、k個の頂点すべてに対して、1以下となるvが存在するのならばYES、ないのならNOと答えよ。 …
atcoder.jp 概要 サイズNの木が与えられる。頂点に1~Nの番号が振られている。k=[1, N]として次の条件下で問題を解け。 頂点kに最初に赤色を塗る。次に塗ることができるのは、すでに塗った頂点に隣接する頂点、というルールのもとで色を塗るとき、何通りの塗…
codeforces.com 概要 円状にN個の数が並んでいて、時計回り順にt[i]である。次の条件を満たすように、これらの数に色を塗る。 隣り合った異なる値の数字どうしは、必ず異なる色が塗られている。 これを満たすように、最小限に色を使って塗ったときの一例を示…
codeforces.com 概要 長さが100万以下の文字列Sが1つあたえられる。構成されてる文字は、アルファベットの最初の20文字、すなわち'a' ~ 't'である。これの連続部分文字列を1つ選んで、1回だけ反転してよい。(しなくてもよい) 操作を終えた時、文字列Sの連続…
codeforces.com 概要 2つの長さNの文字列S, Tが与えられる。次の操作を任意回行えるとして、SとTを一致させることはできるか？ x 同時に反転させる。 例えば、S="sen", T="shojin"でx=3の連続部分列を次のように選べる。 S'="sen", T'="hoj" これを同時に入…
codeforces.com 概要 N人いて、それぞれのprogramming skill(以降PSと略す)はa_iである。N人でいくつかチームを組む。3人以上の人間で１つのチームを組むことができる。 チームの不満度を、チーム内の最大のPSを持つ人と、最小のPSを持つ人との差と定める。 …
atcoder.jp 概要 N個の区間が与えられる。これらの区間をグループ１、グループ２に分ける。それぞれのグループ内の区間の積集合の区間を計算し、その長さの和を最大化せよ。制約： 2
atcoder.jp 概要 長さNの数列A[]が与えられる。次のようにf(l, r)を定める。 l さて、1 制約： 1
codeforces.com 概要 n行m列の行列で、毎行のxorの結果はa[1~n]、毎列のxorの結果はb[1~m]として与えられる。これを満たす行列を存在するのならば、YESと答えて、1つ構築せよ。存在しないのならば、NOとだけ答えよ。制約： 1
codeforces.com 概要 0 数列の要素のXORがuと等しく、和がvに等しい
codeforces.com 概要 サイズNの木が与えられる。そのN-1本の辺に、それぞれ1つずつ、0~N-2の数字を重複なく割り当てていく。 頂点uと頂点vの間を通る単一のパス(木なので必ず存在する)上の辺に含まれる数の集合をSとする。Sに含まれない、最小の非負整数をME…
atcoder.jp 概要 サイズNの木が与えられ、頂点には１～Nまでの番号が振られてる。AliceとBobはAliceからゲームを始め、自分の手番が終わったら、相手に交代する。自分の手番では、次の操作を行う。 木の辺を1本取り除く。これによって、木は2つの部分木に分…
atcoder.jp 概要 ある文字列sが存在し、次の操作を考える。 sの空でない連続部分文字列を1つ選び、これをpとする。pのそれぞれの番目を'?'に置き換えるorそのままにする。 この操作で得られた3つの文字列、a, b, cが存在するとき、元のsの最短の長さを答えよ…
シリーズの構成 １．計算幾何の基本 ２．計算幾何のインフラ整備 ３．直線、線分の計算幾何 ←いまここ ４．円の計算幾何 ５．多角形の計算幾何 ６．AOJにある問題の解説
ei1333.hateblo.jpこれの例題1について、実装の備忘録。 dfs2の操作 今着目してるidx=子とその親をつなぐ辺は必ず使うとする。 すると、子からさらに孫方向での最長はdfs1で求まっている。欲しいのは親の子方向ではない向きの最大。これは下図のようになる。
