Takefumi Yamamura's blog

This blog is for my memorandum.

Takefumi Yamamura's b!og

This blog is for my memorandum

atcoder

AtCoder Beginner Contest 060 D - Simple Knapsack

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. …

Atcoder Grand Contest : B Splatter Painting

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…

AtCoder Regular Contest 023 B - 謎の人物X

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

AtCoder Regular Contest 044 B - 最短路問題

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

累積和とってソートしてBluteForce AtCoder Regular Contest 035 B - アットコーダー王国のコンテスト事情

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

いもす法 累積和 AtCoder Regular Contest 048 B - AtCoderでじゃんけんを

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

2通りの全列挙 AtCoder Regular Contest 049 B - 高橋ノルム君

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

いもす法を二回する AtCoder Regular Contest 045 B - ドキドキデート大作戦高橋君

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

ハッシュテーブルをbitで管理 AtCoder Regular Contest 053 B - 回文分割

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

Double Sweep AtCoder Beginner Contest 019 D - 高橋くんと木の直径

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

貪欲法による文字列操作 AtCoder Beginner Contest 009 C - 辞書式順序ふたたび

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

いもす法 AtCoder Beginner Contest 017 C - ハイスコア

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

値を固定して2点間の最短距離を求めるのを二分探索 AtCoder Beginner Contest 020 C - 壁抜け

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

mini-maxとメモ化探索によるゲーム木探索 AtCoder Beginner Contest 025 C - 双子と○×ゲーム

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

動的計画法しながら幅優先探索 AtCoder Beginner Contest 021 C - 正直者の高橋くん

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

Blute Force AtCoder Beginner Contest 024 C - 民族大移動

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

幅優先 AtCoder Beginner Contest 007 C - 幅優先探索

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

2つの線分が直行しているかどうかの判定 AtCoder Beginner Contest 016 D - 一刀両断

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

いもす法 AtCoder Beginner Contest 001 D - 感雨時刻の整理

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

重複組み合わせ AtCoder Beginner Contest 021 D - 多重ループ

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

AtCoder Beginner Contest 011 D - 大ジャンプ

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

AtCoder Beginner Contest 026 D - 高橋君ボール1号

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

AtCoder Beginner Contest 026 C - 高橋君の給料

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

AtCoder Beginner Contest 013 D 阿弥陀

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

AtCoder Beginner Contest 013 C - 節制

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

AtCoder Beginner Contest 030 D へんてこ辞書

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

AtCoder Beginner Contest 030 C 飛行機乗り

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