裏紙

ほぼ競プロ、たまに日記

2016/7 Solved(2)

7/17

木の中心を使って全探索する問題.中心という概念を初めて知った.

解説を見ながら.まずX=x-y,Y=x+yの座標変換を行うことによって,マンハッタン距離上等しい点が軸に平行な正方形のようになるように出来る.すると,解の候補が4通り出てくるので,それを元の座標系に戻して正しい解を選ぶ.確か当時は回転で座標が実数になっちゃうから嫌だなあと思いつつ,色々試して結局数ケース落ちる提出をしていたみたいだけど,候補を選んでしまうだけならこの座標変換でできて,賢いなあと思った.

7/18

Kが0の時に注意.この時以外は所持金は指数的に増加するので愚直にシミュレーションで良い.K=0だと.毎日1円ずつしか増えないので2兆と現在の所持金の差がそのまま日数になる.

気分の良い日をDPの係数に加える発想が難しかった.勝利数の最小化に帰着させる良いDPの問題だった.

7/19

2次元imos法を使う.左上と右下に+,右上と左下に-をおいておくことで矩形に一様に足せるという仕組み,忘れがちだった...

動的計画法により解く.dp[i][j]=現在i番目のアトラクションまで乗る回数が確定して,残り時間がjのときの満足度の最大値を更新していく.この状態からの遷移はi+1番目のアトラクションに乗る回数分あるので,一見するとT/c[i+1] + 1個の遷移があるように思えるが,満足度はどんどん半減して最終的には0になる(つまりそれ以上乗っても意味が無い).今回,1つのアトラクションの初期の満足度の最大値が500なので,最大でも1つのアトラクションに乗るのは9回までで,10回以上は意味がないので最大値を求めるにあたって考える必要がない.よって遷移の数を抑えられ,時間以内に解ける(submission).

bitDPにより解く.現在の配送状況と最後に訪れた配達先を保存して計算する.現在の荷物の重さは配送状況をみることによって確認できるのでそれを利用して,各配送先までの移動時間と荷物を下ろす時間を足しあわせながら最小値を求める(submission).

現在位置と移動回数を持ちながらBFSし,コストを更新していく.BFSなので,ゴールにコストV未満でたどり着けることが分かった時点で答えが確定するのでそれを答えると良い(submission).

7/20

現在位置と,2つ前の値と1つ前の値を保存しながらBFSする.現在位置から4近傍へ移動する時に2つの値を使って門松列判定をして,okなら辺を張ることが出来る(submission).

7/21

ものさしの長さを2分探索していく.長さを決め打ちにした時,点が結べるかどうかを判定しながらUnionFindで結んでいき,0とn-1がつながっていればOKになる(submission).

7/22

imulan.hatenablog.jp

現在位置とナイト/ビショップの状態をもったBFSにより解く.vectorで移動方向の配列を管理しておくと包括的に書けて良い感じになった(submission).

7/23

ARC 058に参加

CDの2完.Cは余計なことを考えて時間食ってたし,Dも思いつくのはそんなに大変じゃないけど色々実装で手間取って閉まっていた.Eは完全に方針違いだったので,要復習.

7/24

imulan.hatenablog.jp

7/25

(なにもしてない)

7/26

区間の和を保存するSegtreeを作る.クエリ1に対してはその数値を1だけaddするだけでよく,クエリ2は1からmedまでの区間の和を二分探索してx番目に小さい数を求める(submission).

反転した文字列に対して,各indexごとに今の文字と別の方を向いた文字を出力すればよい.

前にAOJで部分問題として似たようなのをやった.始めに4方向用意しといて,この方向は循環的に回ってくるので壁にあたったら方向転換をするという方針がわりとすっきり書ける(submission).

始めに海からの距離が1からのところを求めておき,それらを始点としてキューに入れてから何のひねりないBFSをした(submission).解説見たら,最大正方形を探すDPに落とせるって書いてあって,それは気づかなかった...

7/27

前者は繰り返し二乗法を2回すれば実現できるというのはすぐに思いついたが,後者についてはとても悩んだ.どうしてもまずB^Cを先に計算する必要があるが,これに直接modの繰り返し二乗法を適用させるのは論理が破綻してしまう.そこでフェルマーの小定理を使う.今回,modが素数なので a^{p-1}は1とみなせるので,B^Cのmod p-1をとったものをAの肩に乗せればよいということになる(submission).

7/28

行か列かを選ぶときに,どのマスもすでに埋まってしまっていることはその行または列がすでに選ばれていない限り無いので,そこは選ぶことが出来る.行も列も残り1つになるまでは選ぶことができるので,H+W-1番目に順番が回ってくる人が負けることになる.

permutation使って全探索.

金欠チャンスをどの順番で使っていくかと,そのタイミングによって,最終的に購入できるカップ麺の個数に差は出ないので,金欠チャンスは素数の大きい方から順番に使えるものは全部使っていくようにすればいい.すると,そこまでに消費すべき金額が決まってくるので,ちょうどx円を消費した時に購入できるカップ麺の個数の最大値を前もって計算しておけば,10000までの素数はそんなに多くないので,十分間に合う(submission).

DPによって解く.編集距離と言う名前で以前知る機会があったので,すんなり思いつけた.

7/29

(なにもしてない)

7/30

始めにDPで前計算しておいて,クエリにO(1)で答える.DPの前計算をどのような形にしようか悩んだが,累積和を保存しておくことで高速に計算することが出来る.まず,111111の倍数の端数は1円で払うしか無いので払っておいて,後は111111で割った値についての組み合わせを考えていけば良い.DPの計算をするときにも剰余で累積和を取ってDPを更新し,更にクエリに答えるためにはそのDP自体の累積和が必要になすのでそれを用意してクエリに答えた(submission).

7/31

問題に描かれた条件を1つ1つ考慮して細かく場合分け(submission).

外積を利用して平面の方程式を求める.これが出来てしまえば点と平面の距離の公式をつかって計算出来る(submission).

imulan.hatenablog.jp

AGC 002に参加

ABCの3完.Dは二分探索やクエリ先読みやUnionFindなど考えてみたけど解法には辿りつけず...