足跡-sokuseki-

りかの日進月歩の記録

競技プログラミング

ABC011 D 大ジャンプ

D - 大ジャンプ 問題概要 スタート地点の座標は で、ゴール地点の座標は とする。 1回のジャンプで、それぞれ の確率で以下の4つのうちどれかを行う。 軸方向に だけ移動する 軸方向に だけ移動する 軸方向に だけ移動する 軸方向に だけ移動する ちょうど …

ABC037 D 経路

D - 経路 問題概要 縦 横 のマス目があり、それぞれのマスには整数 が書かれている。 このグリッドの中の好きなマスから開始し、今いるマスの上下左右に隣接しているマスのうち、今いるマスより大きな整数が書かれたマスに移動することができる(移動しなく…

CODE FESTIVAL 2016 Grand Final B Inscribed Bicycle

B - Inscribed Bicycle幾何。 問題概要 三角形の頂点が与えられる。 三角形の内部に半径の等しい円を重ならないように2つかくとき、円の半径の最大値を求めよ。制約 解法 まず、三角形の内部に半径 の円がかけるとはどういうことかを考えてみる。 円の中心と…

ABC036 D 塗り絵

D - 塗り絵はじめての木DPです。 問題概要 頂点の木が与えられる。 両端の頂点が黒で塗られるような辺がないように、頂点を白または黒でぬるとき、塗り方の通り数を で割ったあまりを答えよ。制約 解法 漸化式を立てて木の上でDPをしましょう。 := 頂点 を親…

TPC追いコン A 不完全迷路

A - 不完全迷路 問題概要 高さ 幅 の迷路が与えられる。 壁のマスを1マスのみ道のマスに変えたとき、スタートのマスからゴールのマスへの最短経路長が最長となるようにしたい。 そのときのスタートからゴールまでの最短経路長を求めよ。制約 TLE解法 それぞ…

CODE FESTIVAL 2017 Final C Time Gap

C - Time Gap 問題概要 人の都市について、高橋君の都市との時差が与えられる。 高橋君を含めた 人の都市のうち、すべての2つ都市の時差の最小値を としたときの、 の最大値を求めよ。制約 解法 num[ ] := 高橋君との時差が 時間の人数 とする。num[ ] とな…

COLOCON -Colopl programming contest 2018- D すぬけそだて――トレーニング――

D - すぬけそだて――トレーニング―― 問題概要 スタミナの上限が で、 スタミナを全て消費する時間の候補が 個ある。 時刻 のときにスタミナが で、 単位時間にスタミナが 回復するとき、 回スタミナを消費する場合の消費したスタミナの合計の最大値を各 につ…

ABC034 D 食塩水

D - 食塩水 問題概要 個の食塩水があり、 番目の食塩水は グラムで濃度が である。 この中から 個選んで混ぜるときの濃度の最大値を求めよ。 制約 解法 濃度が の食塩水を作れるかで二分探索していく。 それぞれの食塩水について、濃度を にするために必要な…

CODE FESTIVAL 2016 Grand Final A 1D Matching

A - 1D Matching 問題概要 一次元の世界に 個のパソコンと 個の電源がある。 番目のパソコンの座標は であり、 番目の電源の座標は である。 それぞれの電源は一つのパソコンにのみつなぐことができるとき、ケーブルの長さの合計を最小化する場合の数を で割…

ARC027 B 大事な数なのでZ回書きまLた。

B - 大事な数なのでZ回書きまLた。 問題概要 2つの文字列が与えられる。同じアルファベットは同じ数字を表し、異なるアルファベットは異なる数字を表す場合と同じ数字を表す場合がある。2つの文字列が同じ 桁の数を表すとき、その数は何通りあるか。制約 解…

ARC085 / ABC078 C HSI

C - HSI 問題概要 プログラミングコンテストの 'YES' か 'NO' で答える問題でTLEした。 テストケースは ケースあり、そのうち ケースでTLEしていた。 そこで、 ケースではそれぞれ実行に ms かかって の確率で正解し, 残りの ケースではそれぞれ実行に ms …

ARC087 / ABC082 D FT Robot

D - FT Robot 問題概要 2次元平面の原点にロボットが置かれていて、はじめは 軸の正の方向を向いている。 'F', 'T' のみからなる文字列 が命令として与えられ、先頭から順に実行される。 'F' : 今向いている向きに1すすむ 'T' : 時計回りまたは反時計回りの…

COLOCON -Colopl programming contest 2018- C すぬけそだて――ごはん――

https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c 問題概要 以上 以下の整数を0個以上選ぶ。 選んだ整数のうちすべての整数が互いに素であるように選ぶとき、何通りの選び方があるか。制約 解法 より、それぞれの整数が35以下のど…

ABC065/ARC076 D Built?

D - Built? 問題概要 個の街があり、 番目の街は座標 にある。 座標 にある街と座標 にある街の間に道をつくるのに、コストが 円かかる。 任意の2つの街の間を道を通って行き来できるようにするための最低コストを求めよ。制約 解法 3つの街が にあるとする…

CODE FESTIVAL 2017 Final B Palindrome-phobia

B - Palindrome-phobia 問題概要 'a', 'b', 'c' の3種類の文字からなる文字列 が与えられる。 文字列 を自由に並び替えて、部分文字列に2文字以上の回文を含まないようにできるかどうか判定せよ。制約 解法 2文字以上の回文が含まれないとき、並べ替えた文字…

DDCC2016 予選 C ロト2

C - ロト2 問題概要 個の整数があり、 番目の整数は である。 が の倍数となるような と の組み合わせ が何通りあるか求めよ。制約 解法 積が の倍数になればいいのだから、 それぞれの において必要な情報は、 の約数のうちどれが含まれているか。 よって、…

AGC013 Hamiltonish Path

B - Hamiltonish Path 問題概要 頂点 辺の、連結な単純無向グラフが与えられる。 頂点には から までの番号がついており、辺には から までの番号がついている。 辺 は、頂点 と頂点 を結んでいる。 次の条件を満たすパスを つ見つけて出力する(あり得る答…

ABC080 D Recording

D - Recording 問題概要 個のテレビ番組を録画したい。 テレビが受信できるチャンネルが 個あり、1から までの番号がついている。 録画したいテレビ番組のうち、 個目のテレビ番組は、時刻 から時刻 までチャンネル で放送される(時刻 を含み時刻 を含まな…

AGC018 A Getting Difference

数学的な問題ほど解けないの、どうすればいいんでしょう…? (解説を読んだ後、フォロワーさんたちにもいろいろ教えていただいた)A - Getting Difference 問題概要 箱に 個のボールが入っていて、 番目のボールには整数 が書かれている。 「箱から2つのボー…

ABC079 D Wall

D - Wall 問題概要 1つの数字を から に変えるコストを とする。 行列 が与えられ、 のとき上から 番目、左から 番目のマスに数字 が書かれていて、 のとき上から 番目、左から 番目のマスに数字が書かれていないことを意味する。 マスに書かれたすべての数…

ARC083(ABC074) D Restoring Road Network

D - Restoring Road Network 問題概要 次正方行列 が与えられる。すべての について、 の 行 列成分が頂点 と頂点 の最短距離となるようなグラフが存在するかを判定する。また、存在する場合、そのようなグラフのうち辺のコストの総和が最小となるものについ…

ABC084 D 2017-like Number

400点以上の問題は積極的にブログに書こうと思います。D - 2017-like Number 問題概要 「 も も素数」を満たす奇数 を2017に似た数と定義する。 個のクエリが与えられるので、それぞれのクエリに対して、 かつ2017に似た数となる奇数 の個数を答えよ。制約 …

ICPC2017国内予選 参加記

ICPC国内予選に出ました。 参加記を書くまでが国内予選みたいな風習があるっぽいので書きます。 ACM-ICPC 2017 国内予選 予選前 去年のチームは同学年3人で組んでいたので今年も同学年で組むか〜となって、yebi君(@sigsigma19)としゅもん君(@shumon_84)と組…

ABC008 C コイン

数学ができないので。 期待値問題は苦手です。C: コイン - AtCoder Beginner Contest 008 | AtCoder 問題概要 枚のコインを無作為に一列に並べる。左端から順に、そのコインよりも右側にある、そのコインに書かれた数 の倍数が書かれたコインをすべてひっく…

RUPC2017参加記

3/22から3/24に立命館大学で行われたRUPC2017に参加した。 立命館大学競技プログラミング合宿2017 : ATND Day1 : 立命館大学&大阪大学セット コンテスト前 会場の設営のために10時半くらいにBKCに着いたけど、Twitterではすでに到着している参加者がいてびっ…

gitあれこれ

作問につかった。忘れそうなのでメモ。githubのレポジトリの「Clone or download」からurlを取得 作りたい場所に移動してから「git clone 取得したurl」を入力 $ git clone https://github.com/~既存の(誰かの)フォルダをコピーして、自分の名前に変える。フ…

ABC 006 C スフィンクスのなぞなぞ

数式が出てきたのでメモ。C: スフィンクスのなぞなぞ - AtCoder Beginner Contest 006 | AtCoder 問題概要 大人、老人、赤ちゃんの足の数をそれぞれ2本、3本、4本とする。 街の人数Nと足の数Mが与えられるので大人、老人、赤ちゃんの人数の組み合わせを1つ答…

ABC017 C ハイスコア

自力で満点解法思いついたの嬉しかったのでその記念。C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder 問題概要 個の遺跡があり、遺跡を探索すると宝石と得点が得られる。 番目の遺跡を探索したときに、得点 点を獲得し、 種類ある宝石のうち 番目…

ABC054 D Mixing Experiment

頑張って実装したので記事にするぞ。最近更新頻度高いし競プロ頑張ってる感がある*1。D: Mixing Experiment - AtCoder Beginner Contest 054 | AtCoder 問題概要 N種類の薬品のうちいくつかの薬品を購入する。薬品iにはタイプAの物質を グラム、タイプBの物…

ABC054 C One-stroke Path

頑張って実装したやつは記事にしようという試み。C: One-stroke Path - AtCoder Beginner Contest 054 | AtCoder 問題概要 自己ループと二重辺を含まないN頂点M辺の重み無し無向グラフが与えられるので、頂点1を始点として、全ての頂点を1度だけ訪れるパスは…