裏紙

ほぼ競プロ、たまに日記

2016/1 Solved (1)

1/1

x以下ではどれでもうまくいく、xより大きいとこではムリという境界を探す。→二分探索

2人とも最善手をとる→後手は先手の評価値を最小化するような動きをする

1/2

行列演算とダブリングによる高速化(AND演算においては-1が単位元...1になっててかなりハマる)

1/3

発送の転換(http://www.slideshare.net/chokudai/abc027)が必要だった、本番はdpで解こうとしてたっぽいけど再帰で書いたけどうまく動かなかった(今ならfor分ループに書き下せそう)

1~25の数字を順番に置いていくことを考えた時に、上下と左右のそれぞれに対して数字が置かれるケースは「端、両方空き、片方空き、両方埋まり」の4通り、小さい順に数字を置くので、この時条件に反してしまうのは「片方空き」の位置に配置してしまうことである。数字の配置順を固定→大小関係が決まっている→数字そのものに対して注目する必要が無い→盤面の状態をビットで表す→DPという流れ。すでに埋まっている部分の扱いがうまくできなくてちょっと遅い(http://abc025.contest.atcoder.jp/submissions/603651)

1/4

高さはh+stで決まるので、逆に撃ち落とす高さを決め打ちでvにしてv>=h+stを変形してt<=(v-h)/sを得る。このtの値がt以下のものがt個以下ならt秒以内にそれらを撃ち落とせるのでokという判定方法でO(N)で判定でき、あとはvについて2分探索。

1/5

dp[i]=サプリiまでを食べる組合せの個数として、サプリがかぶらないギリギリの位置をstとして記録し、dp[i]=dp[st]+dp[st+1]+...+dp[i-1]で埋めていく。iをすすめるごとに、しゃくとり法的に詰めていく。(http://abc017.contest.atcoder.jp/submissions/604419)

蟻本を読みながら、LCAを作った。うまく動いた(http://abc014.contest.atcoder.jp/submissions/604512)

1/6

部分点は、切る関係をbitloop+BFSで到達判定で出せる。満点解はフローを使う。初めてフロー書いた。

1/7

1/8

ウサギの向きは端を除いてR...RL...Lというようないくつかの区間から構成される。この区間内のウサギを動かそうと思う時に、RとLの境目に集まってくることになる。その際、最大で動かしたいときはその区間内で向いている方向が多いウサギを目一杯動かせるように寄せるのが良い。境界の位置をxとした時に、それが少ない方に1つ寄ると(多い向きのウサギの数)-(少ない向きのウサギの数)ぶんだけ移動回数を増やせるからである。それを貪欲にやっていく。(http://arc041.contest.atcoder.jp/submissions/605380)

1/9

ABC 032に参加

ABCDの4完

1/10

簡単なのでもいいから1日1問やろう。

1/11

1/12

明るさを決め打ちして、二分探索しながら到達範囲をBFS。

a%p==0か否かでまず場合分けが必要。a%p==0ならx[1]以降は全て同じ値になることに注意。逆にそうでなければxの値はすべて異なる。そうすると、その人が行くべき列は決まる。全体をソートして、自分のindex/mで求まる。左から順に見ていって、行くべき列の列の左から順番に貪欲に詰めていくのが一番効率が良い。 自分のindexを探すところで二分探索を使用するが、自前ので無限にバグってた(http://arc018.contest.atcoder.jp/submissions/610218)。 机が1列に並ぶ縦長の時に、なんかインデックスがバグってたっぽい。うまくSTL使おう。lower_bound使ってようやく解決(http://arc018.contest.atcoder.jp/submissions/610232)。 ほんとに使えるところはSTLを積極的に使うべきだなあと思った...

1/13

SRM678 Div1に参加

Easy - ANewHopeの1完(https://community.topcoder.com/stat?c=problem_solution&rm=327810&rd=16648&pm=13585&cr=23325175)。

レートめっちゃあがった(1290→1402)。

1/14

出現する単位の換算表を作り、埋まってないところをワーシャルフロイドで埋めていって、最後にその表全体を見て大きいところが答えになる。ワーシャルフロイドを久々に書いたらループの順序間違えてめっちゃハマった。ちゃんと意味がわかってれば間違えるべきじゃないんだよなあ...(http://arc015.contest.atcoder.jp/submissions/610771)

文字列の操作。

しゃくとり法。

要するに木の直径を求める。

村1からBFS→最も離れた位置pからもう1度BFS→最も離れた位置q発見→pとqが答え(pやqが複数個あり得る場合でも、特に問題はない。)

1/15

CF339 Div2に参加

コンテスト中0完で爆死。かなしいばぐをうめこんでしまった。以下2問は修正解き直し。

kの累乗で、l<=k^x<=rをすべて求める問題。上限10^18はやはりC++erには不安になる数字であるということを身をもって感じさせられた...オーバーフローの瀬戸際はやっぱ怖い。どうせ掛け算60回ぐらいしかしない処理なんだからPythonで書けばよかったと切に思う。オーバーフロー回避テクとして、r/kよりもk^xが大きければ、k^(x+1)が必ずrより大きくなる((r/k)*k<k^x*k -> r<k^(x+1))から、それを打ち切り基準にすればC++でもできた。

n個の数の掛け算。ただ「少なくともn-1個の数はbeautiful numberである」。これもめっちゃ数が大きいので、これはPythonでポンポン掛け算して終わりにしよう!→普通に10万この掛け算TLE→制約0.5sC++で多倍長実装しないとダメなのか...→→→→しばらくして→beautiful numberって10^xの形しかありえなくね→じゃあnot beautiful numberの後に0がめっちゃ並ぶってことじゃん、全部文字列で処理できるじゃん...→本当にしょうもないミスでSystemTestを落とす→(死)

できるだけ均等に分けるのが幸福度を最大化出来る。n>kn<=kの場合の違いに注意。