読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

AOJ-ICPC 400 インビジブル

問題 インビジブル | Aizu Online Judge D: インビジブル - JAG Contest 2016 Domestic | AtCoder 解法 先手はスコアの最大化、後手は最小化を目指すのでミニマックス法で解ける。 先手, 後手のデッキでスタックにつまれている区間をそれぞれ[l0, r0), [l1, …

AOJ-ICPC 400 Eleven Lover

問題 Eleven Lover | Aizu Online Judge 10進数表記の数sが与えられる sの部分文字列のうち、11の倍数であるものの個数を答えよ ただし、部分文字列のうち先頭が0でないもののみをカウントする 制約 |s| <= 80000 解法 「11の倍数 ⇔ D = (奇数桁目の和) - (…

ARC057 B - 高橋君ゲーム

難しかった。 問題 B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder 高橋君はN日間ゲームを行う。i日目にはa_i回のゲームをする。ゲームの結果は勝つか負けるかのどちらかである。 高橋君のi日目の機嫌は勝率によって決まる。i-1日目までの勝率よ…

yukicoder No.393 2本の竹

学び。 問題 竹が2本ある。長さはそれぞれ である。 人の客がいる。 番目の客は長さがちょうど の竹が欲しいと言っている。 あなたは2本の竹のいずれかから一部を切り出すことで客の注文に応えることができる。ただし異なる竹から切り出した部分どうしをつな…

yukicoder No.390 最長の数列

問題 N個の正の整数からなる集合 S = {x_1, x_2, ..., x_N} がある。 SからM個の要素を選んで適切に並び替えた数列を (a_1, a_2, ..., a_M) とするとき、aが単調増加かつ隣り合うすべての要素に対してa_iがa_i+1の約数となるような数列を「良い」数列と呼ぶ…

yukicoder No.385 カップ麺生活

問題 M円の所持金がある。 N種類のカップ麺がある。i番目のカップ麺はCi円である。カップ麺は好きなものを好きなだけ購入できる。 カップ麺を購入したとき、もし残り所持金が素数となれば所持金をM円に戻すことができる(これを"金欠チャンス"と呼ぶ)。ただし…

ABC038 D - プレゼント

問題 i 個の数の組 (w_i, h_i) が与えられる。これらから自由に選んで並べてw, hともに狭義単調増加な列を作るとき、その最大の長さは? 制約 1 <= N <= 105 1 <= w_i <= 105 1 <= h_i <= 105 解法1: LIS まず、入力をwの昇順にソートします。すると、以下の…

SRM538 Div.1 Med(450) TurtleSpy

Div.1 Medium 初AC! 問題 TopCoder Statistics - Problem Statement ロボットに以下の命令を送ることができる。 その場で左(右)に向きをx度変える(xは1以上359以下の整数) 前(後ろ)に距離xだけ進む 使える命令文(「左に50度曲がる」など)が与えられるので…

ABC027 D - ロボット

想定解賢いなあ…という感じ。 問題 D: ロボット - AtCoder Beginner Contest 027 | AtCoder 数直線の原点にロボットが置かれている。 はじめ、ロボットの幸福度は 0 である。 このロボットに命令列が与えられる。 命令列は次の 3 文字のみからなり、先頭から…

RUPC2016 Day1 D : Scanner

昨日解けなかったDP。 問題 AIZU ONLINE JUDGE 解法 DP。本番は貪欲法(Tを昇順にソートして、今までにかかっている時間が最小のスキャナーに順番に入れていく)で挑んだが、これは「1,2,3,4,5,6,7,8,9」というケースでWAする。(正解は15, 15, 15だが、この貪…

RUPC2016 Day2 G : Max Pig Noodle

本番でctylさんが解法を編み出し、自分が実装した問題。 問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=G 解法 DP。int dp[xの残量][yの残量] = このx, yで実現できる最大のブタメソの最大個数とすればよい。交換人…

SRM 680 Div.1 Easy BearFair

Div.1 Easy 4題目。 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14129 以下の条件を満たす集合が存在するか判定せよ。 要素は互いに異なる正の整数 要素数 は偶数 集合は 個の偶数と 個の奇数からなる 要素はすべて 以上 以下 以上 ]…

Codeforces Round #338 (Div. 2) B - Longtail Hedgehog

過去問再挑戦キャンペーン実施中。 問題 1からnまでの番号がつけられた点とm個の辺からなるグラフがある。重複辺・自己辺はない。 このグラフのいくつかの辺に色を塗ることでハリネズミを作る。ハリネズミは「尾」と「背骨」からなる。これらは以下のように…

ARC043 B - 難易度 (作成中)

記事書こうと思ったんですけど,やっぱりわかってないということがわかったので記録だけ残しておきます. 問題 個の正の整数 から, を満たすような4つの要素を選ぶ方法は何通りか. で割った余りを求めよ. 制約 解法 ここでは公式の解説とは異なる方法を採…

square869120Contest #1 D - square1001の通学経路 (square1001's School Road)

問題 D: square1001の通学経路 (square1001's School Road) - square869120Contest #1 | AtCoder 左下が(1, 1), 右上が(W, H)の格子状の地図がある。 条件「K個のマス(左下が(Xi, Yi))のそれぞれについて、その周囲の4点のうち少なくとも1つを通る」を満たす…