足跡-sokuseki-

りかの日進月歩の記録

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あたりを高速に通したい

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:前回の第一回目は去年の国内予選をした

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

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 を全探索してあげると良い。

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で書き換わっていれば完了。

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

競プロ合宿の開き方

競技プログラミング 参加記

はじめに

競プロ合宿といえば RUPC （立命館大学競技プログラミング合宿）や ACPC （会津大学競技プログラミング合宿）が有名だと思います。*1


最近、競プロ合宿の需要が増えている気がしていて、たとえば RUPC の参加登録はページ公開後1時間もしないうちに埋まってしまったり、



のように新たに競プロ合宿が開催されたりしています。


競プロ合宿は楽しいので、もっとたくさんの合宿が開催されてほしいなーと思い、合宿の運営のノウハウなどをみんなに共有したい気持ちになったので書きます。


ちなみに、そすうさは RUPC2017 / RUPC2018 / RUPC2019 の運営を経験しているのですが、この記事は自分から見た部分しか書いてないので、もし何か不備等があれば言ってください。
また、もっと詳しいことが知りたい場合は直接聞いてください。

RUPC / ACPCとは

RUPC は立命館大学が主催する競プロ合宿、 ACPC は会津大学が主催する競プロ合宿で、それぞれ例年3月と9月に開催されています。

これらの競プロ合宿の主な特徴は

  • 3日間にわたり、オンサイトでチーム戦のコンテストを行う
  • コンテストで使う問題は、どこかのコンテストの過去問ではなく、運営が用意する

となっています。

問題セットは立命館大学、会津大学、北海道大学が提供し*2、（主観的には） ICPC っぽい問題が出題されているみたい*3です。
コンテストは Aizu Online Judge （AOJ）で行っています。

競プロ合宿（RUPC）の運営の大まかな仕事

RUPC でやっていることを書きます。時系列じゃなさそう。

はやめにすること
  • 日程を決める

RUPC ではジャッジ（作問）をする3大学の予定をうまくすりあわせて日程を決めています。（だいたい1月上旬くらいに、いつにするか話し合い始めている気がする。）
日中に行われる他のコンテスト（企業コンや有志コン）と日程が被ってしまうと悲惨になってしまうので、コンテストを開催しそうな大学の人やちょくだいさんとDMで相談して避けるのがよいです。
3月は卒業式や学会が行われやすいので、そういうのも外そうと考え始めると、だいたい候補の日程は固まってきます。

  • 問題セットを提供してくれる人を探す

RUPC では例年会津大学と北海道大学に頼んでいますが、新しく合宿を開催するなどであてがない場合は、作問できそうな知り合いに声をかけてみるか Twitter などで募集するとよいと思います。
作問を頼む場合は、早めにコンテストの時間（3時間など）を決めましょう。何時間セットにするかを決めないとどういう難易度の問題をどれくらい作る必要があるかわからないので。慣れていないと作問は時間がかかりがちなので、作問者はできるだけ早く募集するといいと思います。
ちなみに RUPC では3時間セットで7問程度、5時間セットで13問程度出題されているようです。

  • 会場を抑えて参加人数を決める

日程が決まったら、会場を押さえましょう。遠方から来る人は大きい荷物を持って来ることが予想されるので、広めの部屋だと嬉しいです（コンテスト前・コンテスト後の交流とかも広いとやりやすい）。コンテスト中はみんなPCを使うので、会場に電源がたくさんあると良いです。もし電源が少なければ、その分たくさんタップを用意しましょう。
参加人数は、会場の広さや風船運びなどの運営の都合を考えて決めると良いです。

  • 懇親会の場所を決める

参加人数が多いと懇親会の会場を探すのが難しいがち。
たくさんの人と交流できるように、席を移動できるタイプのお店だと嬉しいなあという気持ちになります。

  • ジャッジシステムとして AOJ が使えるように会津大学の先生と連絡をとる

コンテスト開催の日程と時間が決まったら、先生と連絡をとりましょう。*4

  • ATND とフォームを書く

ATND には、どういう合宿か、場所や日時、スケジュールはどうなっているか、参加人数の枠や参加費はどのくらいか、懇親会はどうするか、みたいなのを書きます。（RUPCのATNDを参考にしてください）
RUPC の募集には ATND を使っていますが、昔はこくちーずを使っていたみたいです。こういうイベント告知サイトは他にもありますが、どこがいいかはよくわかりません。
ATND では懇親会の参加の出欠確認ができないので、Google フォーム を併用していて、そこでコンテスト・懇親会の出欠や名札の情報を集めています。
ATND とフォームの募集を締め切ると合宿の参加人数や懇親会の人数が確定できるので、締め切りの日時は懇親会の人数の確定日時とかに設定すると良いです。*5

  • 無線 LAN が使えるか確認する

無線 LAN が使える環境がないとコンテストがつらいです。

  • 風船や名札ケースやゴミ袋などを買っておく

RUPC の場合はだいたい Amazon で買い揃えます。
風船や問題文を入れる封筒は使いまわすので一度用意すればそれでいいんですが、紙コップやウェットティッシュやゴミ袋等は消耗品なのでちゃんと買いましょう。
名札は回収が面倒なので毎回使い捨てのやつを買ったりしています。別のオンサイトで RUPC の名札持ってる人を見かけると嬉しくなりがち。

  • 企業に協賛してもらえるなら連絡をとっておく

昔は RCO さんとかに協賛してもらっていて、そのときは懇親会費が無料になってましたね。その節は大変お世話になりました。

  • 大学の宿泊施設の予約など

立命館には学生のみが宿泊できる施設があって、ジャッジの3大学の人は大学に宿泊したりしています。

  • 作問

作問の仕方は Rimeの使い方 - beet's soil を参考にすると良いです。余裕をもって作問しないと炎上しがち。

直前にすること
  • お菓子と飲み物を買いに行く

買ったものは部室等に置いておき、当日の朝に会場に並べるのがいいと思います。もしそのような場所がなければ、当日の朝に買いに行くのが良さそう。
ちなみになんですが、70人分の3日間のお菓子と飲み物を一度に買おうとすると結構大変で、7人くらいいないと運ぶのが不可能。

  • 名札や受付の準備をする

参加者リストを作ってそれぞれ懇親会の金額を書いておくと、当日の受付のときに計算しなくてよくて便利だったりします。
名札にはアイコンと名前を書いていますが、もしかして所属の情報とか入れた方がよかったりしますか？（まあ必要なら勝手に余白に書いてもらうといいんですが）

  • 問題文の印刷

事前に問題が完成していれば先に印刷しましょう。 RUPC の立命セットは例年間に合ってないので Day 1 の朝に印刷していますが、非常にバタバタします。

  • 会場の設営の準備

チーム戦のために机や椅子をいい感じに配置します。これは当日の朝にやってもいいと思います。大掛かりな移動は前日までにやっておくと当日楽になる程度。

  • ネット接続のチェックとか

まあいらないと思うけど一応。*6

当日すること
  • 会場の設営

受付の場所をつくったり、お菓子や飲み物を並べたりします。飲み物は紙コップで飲むことになるので、紙コップを置くスペースや紙コップに名前を書くペンなどを用意しましょう。コンテスト終了後とかに感想戦などで人がお菓子の周りに群がりがちなので、スペースに余裕があるといいと思います。
あとはコンテストで使用するプリンターやコピー用紙も準備しておきましょう。

  • 受付で参加費等を回収する

同人即売会みたいに百円玉とかたくさんあるといいと思います。行ったことないから知らないけど。
RUPC2019 ではチーム決めにアプリケーションを使っていたので、それに使う AtCoder ID を聞いたりもしていました。
参加人数が多いと受付が混みがちなので複数人いたほうがいいです。名札は受付のところに並べておくと、来た人に勝手に取っていってもらえるので楽です。

  • 合宿中の司会・進行とか

社会性とコミュ力が試されます。スケジュールとか臨機応変にするのむずかしいね。*7

  • コンテスト中のあれこれ

風船を運んだり、clar （質問）対応をしたり、First Accept の記録をしたり、印刷クエリに対応したり、いろいろ

  • 解説後の片付けと懇親会への案内

風船や問題文を入れた封筒は使い回しているので、ちゃんと回収しましょう。あとはよしなに。




漏れがありそうだけど、だいたいこんな感じな気がします。
どこまで詳しく書けばいいかわかんないね。

最後に

運営は大変なこともありますが、参加した人に楽しかったって言ってもらえるのが一番嬉しいです。あと参加記を読むのも好き。
競プロ合宿は他のオンサイトに比べて参加のハードルが低い（予選があったりするわけではない）ので、普段会えないようないろんな人と知り合いになれるのも良い点だと思っています。

運営でわからない点があったら気軽に聞いてもらっていいので、ぜひ競プロ合宿やりましょう！！応援します！！

*1:会津大学競技プログラミング部によると、2012年から毎年開催していて歴史がありますね

*2:昔は他の大学だったらしいです

*3:もともと RUPC / ACPC は ICPC 対策の色が強いので

*4:新しい合宿を開催する場合は、いきなり日時のメールを送るんじゃなくて、この時期に開催を考えているんですけど…みたいな連絡を事前にするべきだと思う（しらんけど

*5:RUPCでは懇親会が大人数の予約になるので、1週間前までに人数を確定して連絡してくれみたいなのをお店から言われます。

*6:一番怖いのが同時接続に耐えられるかなんですが、事前の接続チェックで70台を一気につなぐことは無理なので

*7: RUPC や ACPC の Day3 は朝が早いので遅刻する人がいる