2019-07-11

four-t practice 2019 Vol.12

https://onlinejudge.u-aizu.ac.jp/beta/room.html#fourt_2019_12/info
チームでときました

ABCを自分とnoy先輩、D以降をHao君が読むことにする。
Aを読む。やるだけなので実装する。AC。
Bを書いてもらう。入力形式がアでつらそう。その間Cを読む。なんだかんだBが通る。開始20分くらい。
Cは実は解いたことがあったけど実装することになる。実装つらいんだよね〜とか言いながら書く。その間noy先輩はHao君と一緒にDを考えてもらう。
Cの実装が終わってサンプルを試しても合わないので、Dを書いてもらうことにする（といいつつ、全探索しかわかんないっぽい状況だった）。
デバッグをするとlower_boundとかupper_boundのあたりがまずそうなのでかわってもらう、サンプルがあったので投げる、RE。intじゃだめなことに気づいてもう一回投げる、WA。完全にわからなくなる。ここで1時間20分くらい。
Cがわからなくなったので、Cを捨ててDを一緒に考えることにする。Dは答えが8より大きくならない（1文字ずつ区切った場合、最大が9で最小が1になる）ので、A桁で分割したあとにありうる分割の桁数はA-1, A, A+1 くらいしかないんじゃないかって話になってたんだけど、「0」は使われないのでA>2のときはAでしか分割できないのでは？となって、A>2の場合はNの約数だけ考えることにする。A=2のときどうすればいいかよくわかってなかったんだけど、Hao君がいい感じの案を思いついたらしくて、全部実装してもらうことに。ばちゃ開始から2時間15分後、見事DをAC！！わーい！

反省

一度ACした問題は、バグらせずに解けるようになりましょう（終わった後昔のACコード見たけど同じことやってるんだよね、いまだに今日のコードのだめなところがわかりません、たすけて）

2019-06-30

ICPC2019模擬国内予選

競技プログラミング

問題文：
http://icpc2019.jag-icpc.org/icpc2019/contest/problems_guest_ja.php
順位表：
2019/Practice/模擬国内予選/順位 - ACM-ICPC Japanese Alumni Group

チームUnRatedで出てABC3完75位（有資格者46位）でした。
BCあたり時系列ちょっと怪しいですが、コンテスト中を書きます。

コンテスト

Aを自分が、Bをnoy先輩が、CをHao君が担当することになる。
Aは見たらわかるので提出、AC。Bは場所と沼地の個数をもってbfsらしいので書いてもらう、Cが読解がやばいらしいので一緒に読む。
Bは実装がつらそうで、Cはx軸とy軸独立に考えたら良くて、偶奇で良い感じにできるので、先にCを書く。WA。
Cのコーナーを考えつつBを書いてもらう。BつらそうなのでDを考える。
Dは回転だけ最初にしてそのあと編集距離を求めればできそうで、書きます。投げます。WAになります。ここで1時間経過。
BはそのあといろいろがんばってもらってAC。
Cは実験しようということになって、Cのコードをかいてもらう。20くらいまで実験すると規則性が見えます。Cが通ります。
Dのコーナーがわかって、削除してから回転したほうが得な場合があって、でもそれをどうしたらいいかわからなくなったので、先を読みます。ここでコンテスト半分くらい。

E：Mが小さいので半分全列挙とかするのかな、いや何もわからねえ
F：構文解析マジ？と思ったら文字列数え上げじゃーん、むり
G：一番長いやつから1つ内側にはいると2番目になりませんか？どうなんですか？みたいなことを考えていた
H：グラフだし（部屋、コイン）で拡張ダイクストラしたらできませんか？とか考えてた

なんだかんだ自分にはHが一番できそうだったのでHを考えると、まずコインボタンは途中で押す必要がなく、脱出直前にどの部屋のボタンを押すかを考えればよくて、これは昨日のABC-D。よって、（今いる部屋、通った部屋の数、ワープで得たコインの数）を持ってDPをして、 $d_i$ にきたら、「 $e_i$ - ワープで得たコインの数」を「通った部屋の数」に分割するcombinationを求めて答えに足せばいい、みたいになる。しかし、状態が2000*2000*6000になって配列で持てないので、 $a_i < b_i$ を使ってクエリ先読みして、各部屋でその都度求めることにする。あとdp[2][2000][6000]もつらいのでpriority_queueでがんばる。ここまで考えた時点で残り1時間で、とりあえずコードを書き始めたんだけど、途中でcombinationの引数が1e9までなことに気づいてつらくなる。combination以外を書いて、どうするかかんがえることにする。残り30分くらい。
FができそうらしいのでHao君にバトンタッチする。
combinationの第二引数は高々Nなので、階乗の逆元だけ前計算することにして、分子はO(N)かけて求めて計算機の力を信じることにする。ラスト10分になってFつらそうなので変わってHを書く。サンプルがいくつか合わなくて終了。お疲れ様でした。

反省など

Cですぐ実験できなかったところ
多少時間がかかってもいいから全探索するという選択肢が頭になかった
ABCあたりを高速に通したい

2019-06-20

HCPC 2019 Virtual Vol.20

競技プログラミング

チームで解きました。
onlinejudge.u-aizu.ac.jp

Aを自分が、Bをnoy先輩が、CをHao君が担当することになったので、まずAを読む。
やるだけなので書く。ACしたのでBを書いてもらう。その間Dを読む。
Bが通ったのでCを書いてもらう。Dは拡張ダイクストラをすればできそう（最近拡張ダイクストラいっぱい書いてるので嬉しい）。
Cバグらせてつらそうだったけど、なんとかなってACしたのでDを書く。ライブラリ写経つらい。
Dも難なくACしてこの時点で開始40分くらい。
Dを書いてるうちに、2人がEの考察をしてくれていて、Eはdfsで全探索すればいいらしくて、noy先輩に実装を任せる。
FGHを読んで、Fを考えてみるけど、3^40はつらいなあとか言ってた。HはHao君がフローでできそうと言ってたんだけど、3000*3000頂点がつらいってなって、もうちょっとかんがえると、DPでできそうって言われたので、次元を増やしたらできるんじゃない？とか適当なことを言って考察を任せることにした（最悪）。Gを考えることにする。
Eが実装つらそうだったけどAC。ここで1時間40分。
Hao君にHの実装を任せて、FとGの考察をnoy先輩と2人で考察してわかんないって言うやつをした。一応2時間ばちゃということだったから2時間すぎたあたりで若干感想戦みたいなことを周囲としていた（最悪）。
Hは開始から2時間20分くらいで通りました。遷移がつらそうだったけど、コード長さはそこまで長くない（でも実装できるのつよい）。

初見のセットでのチーム練ははじめてだった*1けど、いい感じかなーっておもいました（小並感）

*1:前回の第一回目は去年の国内予選をした

2019-06-01

AOJ2333 僕の友達は小さい

競技プログラミング AOJ

AOJ-ICPC 500 自力AC！！！！

My friends are small | Aizu Online Judge

問題概要

$N$ 人の友達がいて、 $i$ 番目の友達の重さは $w_i$ である。
この友達を好きな順で選択し、選択した友達の重さの総和が $W$ を超えないようにしたとき、選択した友達の組み合わせは何通りあるか。ただし、選択できる友達が残っている場合はその友達は選択しなければならない。

制約
$1 \le N \le 200$
$1 \le W \le 10^4$
$1 \le w_i \le 10^4$

解法

「選択できる友達が残っている場合はその友達は選択しなければならない」の制約がない場合は普通のナップサック問題となり、

dp[i][j] := iまで見て重さの総和がjのときの場合の数

とすればよい。

「選択できる友達が残っている場合はその友達は選択しなければならない」を言い換えると、「選択した友達の重さの総和 + 選択してない友達の最小の重さ $> W$ を満たさなければならない」となる。
よって、選択していない友達のうち、重さが最小の情報を保持してあげればよい。

dp[i][j][k] := iまで見て重さの総和がjで、選択していない重さ最小の友達のindexがkのときの場合の数

とすると、DP後で $j + w_k > W$ を満たす dp[n][j][k]のみを答えに加算してあげればよい。
計算量は $O(N^2W)$ となって間に合うが、dp[200][10000][200]では配列が足りなくなるので、1次元目を使いまわしてdp[2][10000][200]とすればよい。

AIZU ONLINE JUDGE: Code Review

2019-05-15

AOJ 2642 Dinner

競技プログラミング AOJ

Dinner | Aizu Online Judge
AOJ-ICPC 550点…？

問題概要

$N$ 日間の夕食を食堂か自炊のどちらかで済ませる。
$i$ 日目に食堂で夕食をとると幸福度が $C_i$ 得られる。
各日に自炊をすると得られる幸福度は、 (自炊をした時点での自炊パワー) $\times P$ である。
自炊パワーは、初期値が $Q$ であり、食堂に行くたびに 1 減り、自炊をするたびに 1 増える（食事の終了時に変動する）。
$N$ 日間の幸福度の総和の最大値を求めよ。

制約

$1 \le N \le 500,000$
$0 \le P \le 500,000$
$|Q| , |C_i| \le 500,000$

解法

気づくべき重要な点は、ある日に自炊によって得られる幸福度は、「その日以前に何日自炊し、何日食堂に行ったか」のみに依存するということである。
自炊を $x$ 日行い、食堂に $y$ 日行ったとき、 $x+y+1$ 日目に自炊をすると幸福度は $(Q+x-y)P$ 得られる。

ここで、 $N$ 日間で $K$ 日自炊したときの幸福度を式にしてみる。
$sum := C_0 + C_1 + … + C_{N-1}$ とし、
自炊した日を $a_0$ 日目, $a_1$ 日目, … , $a_{K-1}$ 日目（0-indexed）とする。

$a_i$ 日目以前に自炊した日数が $i$ 日で食堂に行った日数が $a_i - i$ 日なので、 $a_i$ 日目の自炊パワーは、 $Q+i-(a_i-i) = Q - a_i + 2i$ となる。
よって、 $a_i$ 日目に自炊したときの幸福度は $(Q - a_i + 2i)P$ であり、 $K$ 日の自炊で得られる幸福度は $\displaystyle \sum _{i=0}^{K-1} (Q-a_i+2i)P$ である。
一方、食堂で得られる幸福度の総和は $sum - \displaystyle \sum_{i = 0}^{K-1} C_{a_i}$ である。

以上から、自炊した日を $a_0$ 日目, $a_1$ 日目, … , $a_{K-1}$ 日目としたときの幸福度の総和は
$sum - \displaystyle \sum_{i = 0}^{K-1} C_{a_i} + \sum _{i=0}^{K-1} (Q-a_i+2i)P$
となる。
これを変形すると、
$sum - \displaystyle \sum_{i = 0}^{K-1} C_{a_i} + \sum _{i=0}^{K-1} (Q - a_i + 2i)P$
$= sum + \displaystyle \sum _{i=0}^{K-1} \{(Q - a_i + 2i)P-C_{a_i} \}$
$= sum + \displaystyle \sum _{i=0}^{K-1} (QP - a_iP + 2iP-C_{a_i} )$
$= sum + KQP + 2 \frac{K(K-1)}{2} P - \displaystyle \sum _{i=0}^{K-1} ( a_iP + C_{a_i} )$
$= sum + KQP + K(K-1) P - \displaystyle \sum _{i=0}^{K-1} ( a_iP + C_{a_i} )$
となり、これを最大化したいので、 $a_0, a_1, … , a_{K-1}$ は $iP + C_i$ が小さいものから $K$ 個選んでくるのが最適となる。

よって、 $K$ を全探索してあげると良い。

2019-04-28

GitHubで過去のcommit logのメールアドレスを変更する

GitHubのメールアドレス変更が終わった後の話
基本はこれ：https://help.github.com/en/articles/changing-author-info#

変更したい repository の名前を repo とする

ローカルのその repository の外で
git clone --bare https://github.com/user/repo.git
cd repo.git
をして repo.git に入り、その中で

#!/bin/sh

git filter-branch --env-filter '

OLD_EMAIL="your-old-email@example.com"
CORRECT_NAME="Your Correct Name"
CORRECT_EMAIL="your-correct-email@example.com"

if [ "$GIT_COMMITTER_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_COMMITTER_NAME="$CORRECT_NAME"
    export GIT_COMMITTER_EMAIL="$CORRECT_EMAIL"
fi
if [ "$GIT_AUTHOR_EMAIL" = "$OLD_EMAIL" ]
then
    export GIT_AUTHOR_NAME="$CORRECT_NAME"
    export GIT_AUTHOR_EMAIL="$CORRECT_EMAIL"
fi
' --tag-name-filter cat -- --branches --tags

を書いて、hoge.sh として保存する。
OLD_EMAIL（変更前のアドレス）、CORRECT_NAME（名前）、CORRECT_EMAIL（変更後のアドレス）は書き換える。

sh hoge.shでスクリプトを走らせる。
これでローカルでは変更ができたはず。
（git logで変更されているか確認する。）

git push --force --tags origin 'refs/heads/*'
これでpushできる。あとは
cd ..
rm -rf repo.git
で repo.git を消せば良い。

その後、ローカルの repo を書き換えたいので、 repoのフォルダに入り
git pull --rebaseし、
git logで書き換わっていれば完了。

2019-04-13

AOJ0310 枠

競技プログラミング AOJ

枠 | Aizu Online Judge

この高速化テクは典型らしいです。

問題

$N \times N$ のグリッドがあり、各マスに数が書かれている。
このグリッドに太さ1マス分の長方形の枠をのせ、枠が覆っているマスの数の総和を最大化する。
ただし、枠は $1 \times 1$ や $2 \times 2$ や $1 \times 10$ のように、中央に穴が空いていない場合もある。（詳しくは問題文の図を見て）

制約

$1 \le N \le 300$
$-1000 \le p_{i,j} \le 1000$

想定TLE

累積和をしてから、枠の左上と右下を全探索（ $O(N^4)$ ）して、それぞれの枠についての総和をO(1)で求め、最大値を答える。
2次元累積和＋長方形領域の総和を求めるパートくらいバグらせずに素早く書けるようにしましょう。

ちなみにこの問題を見た当初は 300^4くらいいける！w と思って書いてTLEしました（バカかな？）

解法

累積和して区間の総和を $O(1)$ で求めるのは変わりません。

しかし、枠の4辺を全探索すると $O(N^4)$ で間に合いません。 $O(N^3)$ に落としたいので、とりあえず2辺を $O(N^2)$ で全探索して、残り2辺を $O(N)$ で決めることにします。
ここで、2辺を $O(N)$ でしようとしたときに、しゃくとりを思い浮かべると、対辺をペアにするという発想ができます。
上下と左右、どっちを全探索しても本質的には同じなので、ここでは上下を全探索することにします。

$i$ 行目を上の辺、 $j$ 行目を下の辺として、総和が最大になるように右辺（ $r$ ）と左辺（ $l$ ）を決めます。
f:id:wk1080id:20190413181021p:plain
まず $i$ 行目と $j$ 行目を採用することは決まっているので、 $i$ 行目と $j$ 行目のマスの総和を計算しておきます。ここでは、枠を決めたときのその総和からの差分を最大化していきます。

右辺と左辺を一度に考えるのは難しいので、先に右辺から考えます。
右辺を $r$ 列目にすると決めたとき、

$i$ 行目の $r$ 列目以降の部分
$j$ 行目の $r$ 列目以降の部分

は、枠には関係ない部分なので、不要になります。
逆に、

$r$ 列目の $i+1$ 行目から $j-1$ 行目の部分

は枠の一部なので必要になります。
f:id:wk1080id:20190413182753p:plain
よって
（ $r$ 列目の $i+1$ 行目から $j-1$ 行目の部分） - （ $i$ 行目の $r$ 列目以降の部分） - （ $j$ 行目の $r$ 列目以降の部分）
を計算してあげればよいです。
これを $0 \le r \le n-1$ のすべての $r$ について求めてあげます。

そして、左辺の $l$ についても同様で、

$i$ 行目の $l$ 列目より前の部分
$j$ 行目の $r$ 列目より前の部分

は、枠には関係ない部分なので、不要になります。
逆に、

$l$ 列目の $i+1$ 行目から $j-1$ 行目の部分

は枠の一部なので必要になります。
f:id:wk1080id:20190413183500p:plain
よって
（ $l$ 列目の $i+1$ 行目から $j-1$ 行目の部分） - （ $i$ 行目の $l$ 列目より前の部分） - （ $j$ 行目の $l$ 列目より前の部分）
を計算してあげればよいです。
これを $0 \le l \le n-1$ のすべての $l$ について求めてあげます。

これで前計算が終わったので、あとはこれらをうまく組み合わせて右辺と左辺を最適に選びます。
たとえば、 $l$ を決めると、最大となる $r$ は、 $l < r$ をみたすもののうち、さっき計算した差分が最大となる $r$ です。これは「右端が $r$ 列目以降であるときの最大値」などを前計算してあげると $O(1)$ で求められるので、右辺と左辺を計算するのは全体で $O(N)$ でできます。（実際は $l = r$ の場合などは別で計算した方が簡単になります）

AIZU ONLINE JUDGE: Code Review

足跡-sokuseki-

りかの日進月歩の記録

four-t practice 2019 Vol.12

反省

ICPC2019模擬国内予選

コンテスト

反省など

HCPC 2019 Virtual Vol.20

AOJ2333 僕の友達は小さい

問題概要

解法

AOJ 2642 Dinner

問題概要

解法

GitHubで過去のcommit logのメールアドレスを変更する

AOJ0310 枠

問題

想定TLE

解法