problem D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoder how to solve This problem can be reduced to the maximum matching problems. This means that Ford-Fulkerson is among the good way to solve this problem.We have to take care that th…

問題 arc029.contest.atcoder.jp 解き方 二分探索するまえに(A ≤ C かつ B ≤ D)もしくは(A ≤ D かつ B ≤ C)を満たせば"YES"。 満たさなければ、角度で二分探索する。 このとき、中の本を傾けて行って、傾けたときの片方の長さのみに注目して2分探索する。 指…

Problem Statement You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi. You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W. …

problem agc012.contest.atcoder.jp how to solve The limitation of d is very small and it is key point to solve this problem. Consider that dp[v][i] which means “paint dp[v][i] among the range d distance from vertex v”. The time complexity i…

問題 arc023.contest.atcoder.jp note dpを使用した。i歩進むときの最大のたこ焼きの値段をdp[i]とした。 code

問題 B: 最短路問題 - AtCoder Regular Contest 044 | AtCoder note 数学の問題 最短距離がnの場所の場合の数は、最短経路がn-1である場所の数と、最短距離がnの場所の数で決まることを利用して貪欲にとく。 code

問題 arc035.contest.atcoder.jp note ペナルティの小さい順にソートして小さい順にペナルティをうけていけばよい。 コード

Problem arc048.contest.atcoder.jp note あらかじめあるレーティングの人が何人いるのかの累積和と、あるレーティングである手をとるプレイヤーが何人いるかを記録しておく。 そうすると、それぞれの勝敗が次のようにO(1)でもとまる。 int win = dp[players…

Problem arc049.contest.atcoder.jp Note 想定解のやり方と違うみたい。 nこの頂点から最も遠い２組の点が最小になるようにすればよいわけで、ある2点に対して、その２点間の間にあってそれぞれの点と距離が等しくなる任意の点との距離は、 (a.c * b.c) / (a…

問題 arc045.contest.atcoder.jp note まず累積和を使って、担当が1人しかいない掃除場所を探し出す。 その後、担当が1人しかいない場所を1、それよりも多い掃除場所を0として累積和をとればO(1)で任意の掃除の区間をサボれるかわかる code

問題 arc053.contest.atcoder.jp note 回文になる文字列は出現回数が奇数の文字が1回以下の場合。 したがってアルファベット26文字が偶数か奇数かを管理すればよい。

問題 abc019.contest.atcoder.jp note 木の直径を求める際には、まず適当なノードを選んで、そこから最も遠いノードを求める。 次にそのノードから最も遠いノードを求めると、その２頂点の長さが木の直径になる。

問題 abc009.contest.atcoder.jp note 文字列操作を貪欲にするだけなのだが、とても手こずった。 一番左に条件を満たす限り、一番小さい文字を持ってくるようにすればよい。

問題 abc017.contest.atcoder.jp note 累積和を用いて、ある宝石を選ぶことになった際のスコアの合計を求める。すべての宝石をゲットする場合得られる総合点から、ある宝石を選ぶ場合のスコアの最小値が答え。

問題 abc020.contest.atcoder.jp note 値を固定して二分探索するよくあるやつ。2点間の最短距離を求める必要があるのでダイクストラかワーシャルフロイドを使う。

問題 abc025.contest.atcoder.jp note マップの情報をメモ化するのに手こずった。 vectorなどであればmapのキーにできるが、自作の構造体などであると、そのままではハッシュテーブルのキーに出来ない。 詳しくは下を参考 stackoverflow.com qiita.com あと…

問題 abc021.contest.atcoder.jp あなたと高橋君は、AtCoder 王国に住んでいます。AtCoder 王国には、N 個の町と、町どうしを結ぶ M 本の道路が存在し、それらは双方向に移動可能です。 N 個の町はそれぞれ 町 1,町 2,…,町 N と呼ばれています。 また、M 個…

問題 abc024.contest.atcoder.jp メモ 貪欲にやれば良いだけ

問題 abc007.contest.atcoder.jp note 普通にキューつかって幅優先するだけ

問題 abc016.contest.atcoder.jp メモ 苦手意識のある幾何の問題。外積の公式を使うと,あるベクトルに対して、任意の頂点が左側にあるか、右側にあるかをチェックすることができる。 そのため、線分の直行判定は、１つの線分からみたときに、もう一方の線分…

問題 以下略 abc001.contest.atcoder.jp note 文字列の扱いがめんどくさいだけ。雨がふっている時間を管理する配列をいもす法をつかって保持してやればいい。おしまい。 いもす法の解説は http://imoz.jp/algorithms/imos_method.html とかがわかりやすい。 …

問題文 以下のリンクを参考に http://abc021.contest.atcoder.jp/tasks/abc021_d Note 重複組み合わせを求めればよい。 重複組み合わせについては以下のリンクを 重複組み合わせ n個の数字から重複ありでkこの数字を選べば良いので nHr = n+r-1Cn-1 を解けば…

D - 大ジャンプ 時間制限 : 2sec / メモリ制限 : 256MB 問題文 XY 座標上に、スタート地点とゴール地点が 1 つずつあります。 スタート地点は (0,0) にあり、ゴール地点は (X,Y) です。 あなたは、ジャンプという移動法を用いて、移動を行います。 ジャンプ…

D - 高橋君ボール1号 時間制限 : 2sec / メモリ制限 : 256MB 問題文 高橋君は野球が得意です。高橋君は、高橋君ボール 1 号という変化球を投げることが出来ます。 このボールは、投げてから t 秒後のボールの位置を f(t) とすると、 f(t)=A×t+B×sin(C×t×π) …

C - 高橋君の給料 時間制限 : 2sec / メモリ制限 : 256MB 問題文 高橋君は、社員が N 人いる会社の社長です。高橋君の会社では、以下のように給料が決まっています。 高橋君を含む社員の全員が、 1 から N までの社員番号を持っている。高橋君の社員番号はも…

D - 阿弥陀 時間制限 : 4sec / メモリ制限 : 256MB 問題文 古くより伝わる日本の伝統的なくじ引き、あみだくじをご存知だろうか？ あみだくじを行うときは、まず N 本の平行な縦線を引く。次に、M 本の横線をその中に引いていく。それぞれの横線は隣り合う 2…

C - 節制 時間制限 : 2sec / メモリ制限 : 256MB 問題文 セキュリティ意識が高く、最新鋭の錠を購入した高橋君ですが、財布の管理は甘かったらしくお金がピンチな状況です。 高橋君の収入は安定せず、次の収入があるのは今から N 日後です。高橋君は N 日間…

問題文 ミカミくんは怪しい英単語帳を使っています。その単語帳には N 個の単語の意味が載っており、単語 i の説明には「単語 bi と同じ意味である」とだけ書いてあります。ここで、i 番目の単語を単語 i と呼ぶことにします。 ミカミくんはまだ一つの英単語…

C - 飛行機乗り 時間制限 : 2sec / メモリ制限 : 256MB 問題文 ウナギの高橋くんは飛行機に乗ることが趣味です。今回は空港Aと空港Bを往復することにしました。 空港Aから空港Bの飛行機には X 時間かかり、空港Bから空港Aへの飛行機には Y 時間かかります。 …