hogloidのブログ

へなちょこ

ICPC WF '18

に参加していました。今年は北京大会で、日程は大体4月15日-20日でした。

4/15

朝5時半ぐらいに起きて、羽田に向かう。東工大チームにも会う。
飛行機はよくあるBoeing777、椅子をリクライニングさせるとき後ろに倒れるんじゃなくて座ってる部分が前に伸びるタイプだから後ろを気にせずに済むし前の人に邪魔されることもない。(これはBoeing777のおかげかANAのおかげか知らないけど)
昼ごろついて、ICPC Hostの人にホテルまで送ってもらう。結構渋滞してて時間がかかった。チェックインすると3時ぐらい。
ホテルの部屋はかなり広くて綺麗。なぜかシャワーとトイレがガラス張り。
あまりに腹が減っているので、勝手に外に出て近くの店で肉まんと牛肉を頼む。英語が全く通じず困ったけど指差して注文して数だけは中国語で伝えられた。(まあ二人分で2個のつもりが1人あたり2個になっていたんですが…)
ホテルに戻って、registration をやる。ライブラリとかももう預けないといけない。いろんなギフトが多くて、持つのが大変。
夕食を食べる。ホテルのバイキングだけど結構おいしい。あまり中華料理要素はないけど。ちなみにバイキングはこの後ずっと同じ形式で、出てくるものもあまり変わらないので後半は飽きてきた。

4/16

この日は午前はスポンサーの講義があり、午後は知恵の輪とかイライラ棒とかVRゲームとか伝統文化の遊びとかを体験できるブースで遊んだ。VRスキーがかなりすごくて、すごい勢いで(ゲーム内で)ジャンプしたときは思わず(現実で)尻もち付きそうになった。

終わると3時前には暇になってしまい、しょうがないので1人で勝手に地下鉄に乗って北海公園とか天安門広場とかを歩く。この後もずっとそうだけど、1,2時間程度の暇な時間があらゆるところに挟まってて、とても時間を持て余すことになる。ワルシャワ大会とかは予定が詰まりすぎてたらしいからその反省かもしれないが…
そのまま1人で北京大学に行って、歓迎オーケストラみたいなのを聴く。ただナレーションが英語と中国語を交互に使うので何話してるのかよく分からなかった。

あと、昼ごはんの後では MIT のksunさんを含むチームと話した。うち1人は全くコーディングをしないらしく、多くのコードはksunさんが書くと言ってた。チームも校内予選の2日前に決めたらしい。後で分かったことだがこのチームはIMO金メダル8枚チームで、ここまで偏ることもなかなか珍しい。

4/17

この日は万里の長城に朝早くから向かった。北京から一番近いところで50kmぐらいしか離れてない。
予想以上の急勾配ですぐに喉が乾く。ただ一番きついのは最初で、その後は割とどうにかなる勾配だった。
1時間ぐらい登って、また降りて、あとは色んな建物を物色した。
午後は開会式があったが、本当に普通で特に何も覚えてない。

4/18

この日は朝早くから Dress Rehearsal(要はプラクティス) に向かった。問題はWFの過去問で、ただ不勉強なので普通に知らない問題が出てきた。6問だけど初見で全部通すのは難しい。
午後は北京大学のツアーに行くはずが、これまた連れてって貰うまでの時間が長すぎたので勝手に歩きだしていると、先生(と先生の研究室の学生)に偶然会ったので、案内してもらう。北京大の北の方はだいたい庭園がそのまま残されていてメチャクチャ広いし綺麗。
さらに北には円明園があり、ここでも池を眺めながら屋台料理を食べたり、壊された庭園を見て回った。

4/19

この日はついにコンテストがあり、やっぱり朝早くから起こされる。6:30に起きたが、色んなところで待たされコンテストが始まるのは10時少し前。

始まると、とりあえずABCD担当になる。ABは長いのでCを読む、ある辺について、片側が足りなくなるならその分は流さなきゃいけないのは当たり前なんだけど、それだけでイケるやんと勘違いしそうになる。幸いパソコンが回ってくるまで時間があったので間違いだと気づいた。
Bが解かれてるのでBを読む、まあ面倒なやるだけ。断続的にパソコンを使いつつ、KFの後に通す。
(でも、単語にid振って有向グラフ作ってdfsっぽくやると思ってるけど、それにしてはみんな速すぎると思う、楽な方針あるのかな)
次に解かれてるAを読み、かなりやるだけなので続けてやる。しかし突然謎のコンパイルエラーに悩まされ、全く原因が分からず数分お手上げになってしまう。冷静にとりあえずパソコンを明渡し、単にmaxの型が違うという問題だった(でも、エラーで表示された行数は確かに別の場所だったはずなのだが…)。Hと並行してやって、1WAののち通す。
Iの解法をdegwerから聞く。別に難しくはないのだが、入力の加工だったり反転だったり細かいところが面倒くさい。
Eと並行でかき揚げていく。ペナルティは大体諦めて、割とすぐ出すことにする。配列外参照で2回REした後TLEして、1行読む入力のcinをやめてgetchar()でparseは自分でやることにしたら通った…(そもそも最初はgets()を使っていたのだが、なぜかコンパイルできなかった)
後はCを考え分からず、Jはいくらなんでも大変すぎるので無理で、Gは幾何なので捨てた。Dはdegwerが、Eは藤原が取り組んでたので残りはあんまりやることがなく、コードを渡されてデバッグを少し助けたりした(ただDに関しては変わるスピードが速くてサンプル読み上げぐらいしかしなかった)
Dがなんとか20分前に通り、これでメダルは取れるかなと思った。
残りはEに注力した。EPSを変えて出すとかはダメで、コードを見てみると0除算とかnan系で怪しいのがあったのでそこは指摘した。
成り立つはずのassertを入れるとREになることが分かったのでおかしい箇所の検討はついていた。方程式が正しく解けていれば成り立つはずなのでかなり混乱していて、ラスト2分になりもう今から方程式を解き直す時間は明らかにないので、とりあえずREになりそうなら単にそのケースについて考えるのをやめることにすると、実はそれがちょうど正しいアルゴリズムになっていた(なんか考えになかった方程式の解が実はあって、そういうケースはそもそも答えにならないっぽい?)。めでたしめでたし。

Eが通った歓喜のシーン
2018 ICPC World Finals, Split screen - YouTube

終わった直後は、9割方銀メダルは取れてるだろう、金はさすがにないかなと思っていた。SJTUとNTUの人から何完か訊かれたが、とりあえず秘密にしておいた。弁当の残りを食べて、写真を取ったりした後セレモニー会場に向かう。
今年の Closing Ceremony はYesNoの具合が悪く、同じ表彰をやったり、突然運営の人が独唱を始めたりでユニークだった。いろんな情報から、SJTUとPKUのGが片方でも通ってないなら金っぽく、ほんまか?と内心思ってたが確かにそのとおりで、YesNo上だと一瞬1位になったりした後、無事金メダルが確定した。PKUのGも299って書いてあったから通らないだろうと思ってたが、実はキッチリ通していた、さすが(そもそも296分の提出で通ってたけど)。Asia 1位を逃したが、今年からなんか地域表彰が変わってAsia Pacific 1位の表彰になった(オセアニア1位がもらえなくなったUNSWくん…)。

ディナーはオリンピックスタジアムの近くのでかいホールでやった。あまり他チームとは話さなかったが、Um_nik が NRU HSE のコーチで来てたので、話しかけたりサインをもらったりした。その後はRecruitのHRの人に案内されて后海のバーに行って、浙江大の人たちと話した。うち1人はSnackDownでも会った人で、東方も知ってるみたい(!!!)なので、北京大で今度ZUNが講演することを伝えておいた。

4/20

起きて、食べて、空港でまた食べて、帰った。久しぶりにICPCの今までのイベントのツイートとか記事を漁り、懐かしい気分になった。

GCJ multithread

これは何?
  • C++11以降で、GCJ形式(手元で複数ケースの計算をして提出するタイプの問題)の実行が数倍速くなる雛形
なんで速くなるの?
  • 最近のコンピュータは大抵コアが複数個ついてるので、複数テストケース(=完全に独立に並列で動かせる)なら同時に動かした方が速いため
  • 4コア8スレッドでは3~5倍程度の高速化が見込めます(i9やRyzen 7 以降ならもっと…)。一方ノートパソコン用CPUは2コア4スレッドやそれ以下が多いのであまり期待できません。

コンパイルオプション: g++ A.cpp -std=c++11 -pthread

#include <thread>
#include <vector>
#include <iostream>
using namespace std;
int Tnum;
class Main{
//変数・関数はここで定義
public:
  void input(){
//標準入力を受け取る
  }
  void operator()(){
//問題を解く
  }
  void output(){
//出力を行う
  }
};

const int MAX_T=105;
Main solver[MAX_T];
int main(){
  cin>>Tnum;
  for(int i=0;i<Tnum;++i){
    solver[i].input();
  }
  vector<thread> threads;
  for(int i=0;i<Tnum;++i){
    threads.push_back(thread(ref(solver[i])));
  }
  for(auto& t:threads){
    t.join();
  }
  for(int i=0;i<Tnum;++i){
    printf("Case #%d: ",i+1);
    solver[i].output();
  }
  return 0;
}

使用例(GCJ 2017 Round3 A問題)
(ちなみにこの問題、時間のかかるケースが2個ぐらいしか入っていないので、あまり速くなりません)

int Tnum;
class Main{
public:
  set<string> done;
  int len;
  int solve(string s){
    int tot=0;
    REP(i,len) tot+=s[i]-'0';
    if(tot>len) return 1;
    if(done.count(s)) return 0;
    done.insert(s);
    int res=1;

    string perm;
    REP(i,len){
      REP(t,s[i]-'0') perm+='1'+i;
    }
    REP(t,len-tot) perm+='0';
    sort(ALL(perm));
    do{
      res+=solve(perm);
    }while(next_permutation(ALL(perm)));
    return res;
  }
  string s_in;
  void input(){
    cin>>s_in;
  }
  int ans;
  void operator()(){
    len=s_in.size();
    ans=solve(s_in);
  }
  void output(){
    cout<<ans<<endl;
  }
};
const int MAX_T=105;
Main solver[MAX_T];
int main(){
  cin>>Tnum;
  for(int i=0;i<Tnum;++i){
    solver[i].input();
  }
  vector<thread> threads;
  for(int i=0;i<Tnum;++i){
    threads.pb(thread(ref(solver[i])));
  }
  for(auto& t:threads){
    t.join();
  }
  for(int i=0;i<Tnum;++i){
    printf("Case #%d: ",i+1);
    solver[i].output();
  }
  return 0;
}

参考:
std::thread::thread - C++入門
免責: GCJやその他コンテストでこれを使用した場合のいかなるトラブルについても責任を持ちません。

GCJ 2017 R3

ちょっとうれしいので大雑把なコンテスト経過をメモ:

始まる前

  • 昼に起きた。あまり頭は使いたくないので、家の掃除をして、東方のなろうを少し読む
  • なんか頭が明らかに動いてないので10分横になって紅茶を飲む
  • 直前にsigmaがク☆バンバードを視聴完了していたので釣られて視聴する

始まった後

  • とりあえず点の取り方をソートするプログラムを動かす。でも問題を見ないと何もわからないので、Aを読む

A

  • なんか難しい?サイズ10^9のグラフを陽に構築すればできるのはすぐ分かったから、とりあえず書こうとする
  • あまり手が進まない
  • 逆から見たほうが書きやすいことに気づいたので、逆からにして書く
  • smallは通る。
  • largeは少し怖かったが、うっかりボタンを押してしまい走らせる。
  • 明らかに途中のケースで30秒ぐらいかかってる…がそういうケースは4個ぐらいだったのでヤキモキしながら実行の終了を見守る
  • さすがに見守ってられないのでBを読む、があまり頭に入らない
  • 結局4分ぐらいで終わった。すぐに出す

B

  • 読む、さっぱり分からない。フローに見えるけどとても制約を表せそうにない

C

  • 読む
  • Cやりゃ通るだろと思ってたので、やる気が出る。
  • 最初頂点ごとの2通りの結び方のうちコストの小さい方をやれば必ずいけるのかと思い書き始めるが、さすがにそれだと非連結になることに気づく
  • 少し焦り、B/Cどちらを解くにせよD-smallが必要だと思いDに行く

D

  • 読む、10^9+7 だからどうせlargeは解けないな~ラッキーと思ったが、数え上げではない。でもどちらにしろ大変すぎる見た目だし、元々smallしか解く気はないのですぐにdijkstra調に小さいところから埋めていく
  • 通る

C

  • コストが小さい方でとりあえずつなげて、コストが大きい方にswitchすれば2つの連結成分をつなぐ感じになるから、それでKruskal調にやればいい気がする
  • 書いた実装はそこまで消さずに済んだ。始点周りが面倒になって、2通り試せばいいかと思って書く。後で2*2通り試さなきゃいけないことに気づいて直すことになる
  • 書き上げる。smallを通す。残り1hちょい。
  • この時点でAbCdなら通ると思ってたので、bを書いてからCをちゃんとチェックしようと思う

B

  • 考えても分からない。接続行列に掛けるとゼロになる非ゼロベクトルを求めるのかな?と思ったけど、吐き出すと変なことになるしとても簡単には扱えそうにない。smallの愚直は本当に愚直だと間に合いそうもない。
  • 分かんねえ…ACdで終わってしまう可能性を考え、Cを出しておく。
  • よく考えると同じ頂点組を結ぶ辺が両側にあったときまとめられるな~とか思い、smallができそうな計算量になる
  • いくらなんでも面倒すぎる(特に復元) 間に合う保証もないし
  • 残り35分、さすがにこのままsmallやるのは無理だと思いちゃんとした解法を考える。そもそもこんなに解かれてるのが難しいはずがない!
  • ポテンシャルを与えて適当にごにょる?とかも考えたがダメ。とりあえずdfs木を思い浮かべる。
  • 木の部分だけ決めたら残り一意かな~と思ったがそうでもない
  • SCCして強連結成分ごとに考えればいーやと思う。そしたらとりあえずサイクルが取れるなとか思う。
  • サイクルに分解しつつやるのかな~とか思うが分解できないときもある。
  • そのときは逆辺使ったことにすればエエヤンって思う。
  • 逆辺を取るときに短いpath取ればサイズが毎回1/2になるのかな?とか思う→違う
  • でもともかく何度も辺使っていいなら毎回サイクル取れんなあとか思う。
  • サイクルの長さはN以下だからなあ…→0の辺があったらそれを含むサイクル見つけて全部0じゃなくなるように適当にaddできるやん!
  • 合わせても辺の値はN*Mやん!もうsmall通ればいいしとりあえず書いちゃお
  • 頑張って書く、フローと似た処理になるが1から書く。
  • とりあえずSCCして2強連結成分の間に辺があるとダメだな、とか思う(そうじゃなくて橋があるとダメ。後で書き直すことになる。まあ貼るだけだから大したロスにはならなかった)
  • そこそこバグるがなんとか書き終わる。
  • 少しデバッグする、閉路検出周りを少し直す。
  • 大体20分弱で、久しぶりに満足できる実装速度だった。本気出せばお前できるやんけ!みたいな
  • ウキウキでsmallを出す。通った!でも順位は35位、なんで?
  • ももうLargeも解ける状態なので、Large解いて本当によかったと思った。順位表を見て、自分はpenaltyなしだから74点2:22なら通ることを確信する
  • とりあえず2:22まで色々見る、特に間違いはなさそう(∵2:22+8でコンテスト終了だから2:22より遅く開く理由はない)
  • 2:22になって速攻で出す。残りの時間は確認に費やす。
  • 出力の絶対値がn*n以下、0でないことが確認できたらこの問題だとほぼ間違いなく通るなあ、と思いあまり身が入らない
  • そういえば証明はn*m以下しかしてないな、と思って焦るけど出力に対してチェックしてるのでい~やと思う。
  • 終わる。Cは結構不安だったので見るのを躊躇した…けど20位が19位になってたのでtestが終わったのを確認。やったぜ。嬉しすぎるだろ

感想

  • 自分が通ったから、簡単だなあ…と直後は思ったけど、Bは結構苦戦したし、これよりボーダーが上というのもあり得ない気がする
  • とにかく長年の夢だったので嬉しい。もう競プロ辞めてもいいとすら思える。でもFinalsまではやっぱり頑張ります(+願わくば次のICPC WFまで…)

解いたものリスト

個人的良問リスト - hogloidのブログ ←4年ぶりに戻ってきました

今回は、主観的面白さでoを0個〜3個つけています。 ☆は自力では解けなかった問題です。 月間更新予定。2017年1月は簡単めのSRMばかりやってたので簡単めのSRMばっかりです。

個人的備忘録のおまけ程度で書いてるのと、あまり真面目に書くとコストが高くなって疲れるので、荒い書き方になっています。おかしな点・分からない点があれば直接訊いてください。

markdown記法を使ったら一部数式が意図しない解釈をされているみたいです(後で直します、あとで…

nothing

529H: 式を適当に変形すると、B,S,#{Big Airport}を固定したらNの上限と下限が求まる形になるからそうやって求める。#{Big Airport}は小さい範囲で動かす(他はかなり自由なので別に求める)
534H: 同じ場所は二度swapしない、とかの考察を進めていくと、欲しい文字を持ってくる&書き換えで済む。 別解多し。o
549H: 全探索してフロー流す。たぶん全探索は色々あるけど、315通り辺の張り方試す(辺を加えながら閉路が生じないかチェック)→辺ごとに高さが1違うかチェック→それが取り方の数の制約を満たしてるかDPでチェック→フロー流せるかチェック をした
550H: (maxCost-(必ず必要な操作のコスト))/33回まで操作できる、としてよい。(s[i]=t[i], s[i]=t[i]+1, s[i]=t[i]+2)(等号はmod3)となる桁の数の3つ組を状態とする遷移が行列で書ける。状態の数は78個ぐらい。あとは、s=tとなる状態を何回訪れたか数えるよう1つ行を加える。
581H: ふつうのbrute-force. 一番上の列を3w通り試して残りは自明に操作が決まるのでそれがvalidか確認し、validなもののminを取る。当時はflipをbit高速化しないと通らない?かも(今やって1.8sec)なので
586H: なんか貪欲っぽく行ける気もする…が収拾つかなくなったのでDP。dp[何番目の文字列まで決めたか][未使用文字][もう使わない文字]:=最小値 みたいにする。遷移で、新たに使う文字、ここでやめにする文字、ここで始めここでやめる文字の数を試す。L_iのうち26以上の数で挟まれたところは消しておき、26以上のiを高々2つにしておくと、「ここで始めここでやめる文字」を非ゼロにするのはその二つのiだけでいいので計算量がよくなる。(C4
(N+C)) オーダーが高次多項式のときありがちだけどあまり何も考えなくても通るっぽい…(実際それで大丈夫そうな気もする)
615H: 簡単すぎィ! 列をつくれるかどうか⇔Rの数-Gの数がどのprefixも0以上M以下、RGの数が2Mの倍数なのでindex,R-G,R+G mod 2M でDP
640H: N2通りの差の素因数を調べればいいが、そのままやるとTLEするので、104.5までの素数についてはその素数でのmodでソートしてmodが同じものの間に素因数を追加、104.5よりでかい素数は1つしか持ち得ないので、それまでの素因数で割っていき1にならなかったらそれが残り。
634H: 2点を結ぶ直線とそれをepsずらしたような分け方のみ考えればいい。1点を原点に固定して、最初は(Y<0 || (Y=0 && X<0))とそれ以外に分けて、ぐるぐる回しながら入れたり出したりする。原点を入れるか入れないかの2通り回せばいい。
645H: 包除原理して、2回できない集合Sを固定する。Sの各元について、2回できないことを決めたので、0回か1回、これをbitDPにして求めていく。DPは[i日使う][1回乗った集合はT]:=通り数、ただし通り数にはS以外のものを遊んだ?回数をカウントする。カウントの仕方はSの部分集合全部についてS以外の部分集合のとり方がいくつあるかを愚直に数える。O(4N*N)
646H: 二分探索して、何位に入るか決め打ち、それより上のチーム・自分以下のチームはすべて勝つことにして、Win/Lose/Drawがいくつあるか求める。 W>=L+(D&1)が必要条件で、加えて自分自身と戦ってしまわないといけないもの除かなければいけないが、W-Lについてはその心配はない(自チームは必ず勝つためそこで組み換えできる) W-D,W-Dも同様。D-Dのみが問題で、2回とも引き分けるチームがありDがその2つだけのときがNG。WLはDDに変えると得になるケースがあるが、↑の理由の通り全部試す必要はなくて2,3個変えればいい 悪問ではないけど嘘じゃないと確信するのが大変で解法自体は思いつきやすく微妙…
679H: 簡単すぎィ!

o

530H: ふつうのDP.よくある、動かすときに決めないで後回しにしておくやつ。 o
532H: ふつうのDP.rowがsimilar⇔ソートした時に一致、なので、ソートした状態で左から決めていく。N行が今のところ同じ、あとM列ある、色はK色使える、色0を今までL個連続して取っている、というキーがあればDPできる。(最後のは同じ色での塗り分けの区別を同一視するため) o
540H: 10=25 で、mod 2に対する答えとmod 5に対する答えを掛け算すればいい。これで見通しが良くなるのであとは前処理(右端が同じ制約を二つに分割、を繰り返す)をしてDPするだけ。 o ☆
559H: たぶん二分探索が楽。[-PI,PI]の数直線上に、どこからどこまでが覆われるかを置いてくやつ。円と円の交点を求めるライブラリがあればヨシ。 o
578H: 切断する辺を決め、rec(v,p1,u,p2):=(p1-v)のv側の部分木、(p2-u)のu側の部分木についての最大値 としてメモ化再帰。毎ステップでは最大重みマッチングする(=>最小費用流に落とす) 負辺だろうが構わず解くライブラリ使ったらその定数倍で落ちた…(できるなら変形したほうがきっと早い)(適当に自明な高速化をしたら通った) o
584H: 最小有向全域木。頭によぎれば帰着は簡単 reachability,loop とかの確認を怠ってはいけない(戒め)けどどうせサンプルにある o
591H: 上からDPしていく。(点とその上1行分にA,Bを到達させることができるかが状態) 斜めに埋めようとしてしまいやたら面倒になったorz o
604H: 無限に置けるかは、ある微小なベクトルがあってその分だけずらしても重ならないようなものがあるかと同値。どちらかが端点でない交点があったらだめ、ある点に3つ以上別の角度から伸びていたらだめ、そうでない場合はなす角とその逆側だけOKなので、共通部分があるか判定する。 o
613H: 行の左右は独立。左の列から順にDPで埋めていく。状態は[i:何列目][i列を含むleftの行のうち、チェッカーおいたのはいくつか][i列を含むrightの行のうち、チェッカーおいたのはいくつか] o
614H: 初期位置が0,0の代わりにゴールを0,0にする。連立方程式を解きたいが、(NM)3かけるとダメなので、グリッドの周縁部だけそれらの間の確率遷移を求め、期待値を求める。初期位置から周縁に行き着く確率を求め、掛け合わせる。 o
617H: それぞれ独立に、Lex.smallestのgreedyに沿って考える。あるprefixがOKかどうかは、それからある文字の埋め方が存在し編集距離をK以下にできる&&それからどう埋めてもK未満である、ということはない 編集距離はDPで o
631H: クエリーの平方分割して、出てくるu,vだけマークする。それ以外の頂点はスキップし、その間の辺の最大値を持つようにする。クエリーに対し、vから登るときにスキップしたグラフを使えばO(B) 前処理もO(N)でできる o
633H: 素因数ごとに考える。ある2数について指数のでかいのはいくつ、小さいのはいくつ、という条件がたくさんつく。これを、ある2数の指数はhoge以下・2数のうち片方の指数はhoge という条件に分解して、1つ目でNGならNG。1つ目はOKだったら、それぞれの数に上限か下限のどっちかを与えるのがよい。辺ごとに、片方を上限にしたら片方を下限にしないといけない(上限と下限が一致する場合を除く)ので、2SATにして解く。 o
635H: 少ないのから順にA,B,C,Dとして、左からA/Bだけ置いてく。dp[Aをいくつ使ったか][Bをいくつ使ったか][A/Bの間または端のうちnon-emptyなものはいくつか]:=通り数 でDPして、最後は適当に求める。 o
642H: prob[i回spinした][場所0のスコア]:=確率、exp[i回spinした][場所0のスコア][K]:=場所Kのスコアの期待値 として求めていく o
653H: 0,1,2に対しRock,Paper,Scissor(R,P,C)をそれぞれいくつ割り当てるかになる。3
3の行列にしてみると、それぞれの列・行に対して値をいくつかに割り当てて、要素は列と行の値の和になるかどうかが必要十分.これはO(m2)で全探索できる(m:最小のカードの数) なんか合わなかったから必要条件集めてO(m3)で候補を全部あげてそれぞれ可能か確認する方針でも通った o
666H: 区間としてカウントするのは、入っていてかつ他の小さい区間に入っていないもののみとしてよい。すべての区間について、[いくつ左に1が続いてるか][今までの1の数の偶奇]の状態組についてこれをこれに移すのがいくらあるか求める。行列累乗とかを使う。 o
668H: DP.一番内側でないカッコは1回しか通れないことに注目。(∵内側のカッコを出るとき値が0で、同じ動作を繰り返してしまう) dp[残り長さ][今の値]:=残りの長さで値を0にする文字列の数 として求めていく。+,-は普通に入れる。は同時に挿入して、長さ・その中で値をいくつ変化させるかを試す。1回で0にならない場合、その中身にがあってはいけないという制約がつく。全体の答えは、↑のDPで最後が0にならない版(同じように解ける) Nまでの約数の和はO(NlogN) なので、 O(N3logN) o
670H: 1~9を互いに区別して部分集合に分ける方法は20000通りぐらい、そのうち細分になっている関係は1.6e6ぐらいなので、まずこれを全列挙する。あとは、ある分け方についてその分け方またはその細分になっているものは、ある辺集合を使わないということと同値なので、その辺集合を先に掃き出す掃き出し法を使えば簡単に求まる。その後、細分の関係を用いて、ちょうど分け方があるものになる通り数を求める。分け方にid付けるとき、mapでやるとTLEするので、trie木を使った。O(へんなの) どうやら200002かけても細分か否かをbit演算でやれば通るっぽい?:angry: o
674H: コスパのいい方を80個以上使ってなかったらそっちに寄せての要領で、最低使用量を決めて残りの重さ803をDPする。O(N4) 2べき分解→小さいのから詰めてく、というやり方でもできる。前者は境界が面倒なのでこちらのほうが楽? o
707H: 動かす⇔コスト-1の辺をたどる にして最小費用流 o
517H: 可能判定は後ろから埋められるところを埋めていけばいい。最小化は、埋められるところが1つでも見つかれば、それを埋める場合について再帰的に解く。それ埋めない場合、逆側の(列/行)は残ってる全てをその色で塗らなければいけなくなる。こう決めたとき可能かどうか・最小値を求る。 o

oo

537H: 最小費用流に言い換えると、最小流量1、コスト全て負のグラフ、source,sinkは無しで費用を最小化する問題になる。 そのままでも少し強いライブラリがあると解ける。逆に、全て辺を流した状態からどれを消すか考えると、費用が正のsourceやsinkのあるふつうの最小費用流になる(どっちも同じことだが) source,sinkにこだわっると前者が見えない(見えなかった) oo ☆
555H: i番目にheadをおいた状態から始めるとすると、何回かそこで完成するチャンスがあるかもしれないが、一番後のものだけ考えればいい(後のものはそれまでの可能な初期値を全て可能とするため)。iについて自由に数を決められるところのbitmaskを持つ。次に、包除原理する。ここで、goalと全く同じ置き方だけは除外して考える。すなわち、Σ(Sの元)番目にheadをおいた状態から始めてすべて可能となる初期状態の数(-1)|S|-1の総和を求めればいいのだが、Sの元から始めたときすべて可能になる部分はbitmaskのandを取って1だったところなので、codeが影響する長さに制限される。逆にこれが長いと、外にはみ出ない制約から有向な初期位置自体が減るので、うまくやると218182とかになる oo
567H: 山をn-1,n-2,…,0と置いてく。全ての列で見える山が見えない限り、置く候補は高々2つ(2つずらそうとすると端が動いてしまう).全ての列で見える山があるとき、素直に全部試す。状態として、マップ全体じゃなくてそれぞれの列の最高地点の配列を持つと、これで自然と状態数2n+nnになる。 oo
576H: |S|で場合分け。ある長さLについて、indexの差がLの倍数のときそれは同じ文字でないといけない。あるマスとあるマスが同じ文字でないとけない、という条件で、片方からもう片方が導けないようなものが二つあるとき、そのGCDは2000以下。(∵縦にa,b違うとき、a
bマス下の行で二つは高々長さ2000で同時に出てきてしまうため)。よって|S|<=のときは全部試す、それ以外については同じでなければいけないという関係ごとに全部見る、どの関係にも属さないものは2|S|-n*m (実装が結構たいへん)(最初に候補を全列挙したほうが楽らしい) oo
580H: 下からDPを埋めてく。i行目に初めて到達して、それがj列目のとき、以後のコストは「min{行内の任意の経路} max{経路の途中で初めて通る列} そこで降りたときのコスト」(maxが成り立つよう壁を張れるし、ある経路に対しそれよりコストを掛けさせることは不可能) これを用い、さらにDPする。列内でくねくね動くことはありうる。(状態は、左、右、行内の移動でのそれまでのコスト、今左端か右端か 3番目の数が9502になるのでは?→ならない。同じ行の初めのDPのコストの差は高々450なので(∵初めに横移動すればいい)、ここで675+450以上掛けるぐらいなら列内を左右に舐めたほうがいい。) oo
588H: Bobが勝つ⇔ある頂点で、そこから伸びる部分木の高さが3以上のものが3つ以上あるところに、BobがAliceより2ターン早くたどり着けるものがある 確かに、思いつけばそれはそう。AliceがBobの方向へ向かっていく感じの解法でもできるが、場合分けが結構大変。 oo
593H: ふつうのDP.dp[i]:=i文字目までの文字列での組み合わせの数、とすると、最後のw..wo…oを全部試すとO(N2)になる。最後の付け加え方について、Sでのwを含むかどうかで場合分け。含むものは、i以前の最後のwとその前後のoから、区間が決まる。含まないものは、逆にdp[i]を求めたときにどこまで可能か次のw,oの場所からすぐわかるので、別に足す。 oo
596H: n = k (mod divisor) ごとに考える。はじめてn
(n-1)…(n-k2) = 0 (mod divisor)となるkを求めておけば、条件を満たすnがどこ以上か分かる。divisorを素因数分解して、うまいこと合成するとできる。 oo
597H: 1列のRG,GB,BRを0,1,2とし、0,1,2をX,Y,Z個置く問題として考える。0で隔てられた残りの部分で奇数個のものがi個となるような置き方を数え、残りの1,2をどう埋めるかの数を掛け、足し合わせる。(奇数個残したいところは0に(1or2)を、偶数個残したいところは0に(1or2)を2個くっつけて組み合わせを取る感じ。左右は場合分けしないといけない。長さ0の場合1,2の埋め方が1通り、他の偶数は2通り) oo
603H: C[i]:=Σmin(a[j],b[i-j]) でC[i]最大の値を求めたい。a[i]>=M,b[j]>=Mとなる(i,j)の組については前通り試し、そうでないものをFFTで数える。min … がk以上となるようなものがCにどれぐらい寄与するかは、 A[i]:=(a[i]>=k?1:0) B[i]:=(b[i]>=k?1:0) という2つの数列をたたみこめば求まるので、合計でO(N4/3(logN)2/3)で求まる。 oo
605H: こんなのどうせでかいのor小さいのから見るに決まってる…かと思いきや、編集後も残りの要素は連続するし順序が保存されるので、左から埋めていくとうまくいく。P[i]がどこまで広がれるか(それより小さい要素のある範囲)を求めて、どこまで埋めたか、次使う数はどれか、何回操作したかでDP oo ☆
608H: 縦軸を時間、横軸を位置としてグラフぽいものを描く。あるA,Bについて、左の壁に接するなら、それより初期位置を左にずらしても最終位置は同じ。右も同様。B+Aを固定し、両方の壁にぶつからない範囲、右につぶれる範囲、左に潰れる範囲に分けて計算。(整理してから実装しないと実装が躍動して大変なことになった…) oo
610H: XY独立。後ろからDPしていくことを考える。利得のかわりに逃す利得の最小値を考える。毎ステップ、ある点を中心にV状に足して、その後小さい値を近くに均していく感じになるが、この形は常に谷状・下に凸になる(帰納的に示せる) DPテーブルをグラフとして見たときの折れ線の傾きが変わるところを全部配列で持って、V状に足すのと谷をでかくする操作をする 谷底の高さがどれだけ上がったかを毎回足し、和が逃す利得 oo
705H: 行列にスイッチのベクトルを掛けて出てくるベクトルのうち1になる要素を最大化したい。行交換・列交換はしてもOK。列の足し算もしてもOK(スイッチの付け方にある変換が施されるがその変換は全単射なので) これを使い掃きだした形が下三角になるよう掃き出し法みたいなことをすると、N個のスイッチのうちいくつかは使っても使わなくても関係ないものになる。残りの有効なスイッチの数をL個とする。L<=27なら全探索。L>27のとき、L個のライトはある1つのスイッチを押すかどうかだけで点くかどうか決まるので、それ以外のM-L個について、いくつかスイッチを押すか押さないか決めたときに点くかどうかを持つbitDP。 oo ☆
705M: これすき ある2つの箱の中身が何回かの(同じfunctional graphとは限らない)操作を経て同じ箱の中身になるかどうか予め求めておく。初期状態から、併合できる箱の中身はどんどん併合してしまう。もう併合できなくなったら答え。(なぜこれでいいかというと、どんな状態も初期状態のsubsetなので最適解にたどり着ける) ☆ oo
625H: まず、DPで[i人おいたとき][j個のクラスターになっている]というものを、クラスター内の順序が同じものはすべて同じとみなして数え上げる。最後に、jこのクラスターを適当にテーブルに配置する。クラスターの個数が同じなら、どんな人数の割り当ての違いがあっても配置の数は同じになるため。 oo
627H: フロー。それぞれのセルに縦か横を割り当て、S側が横にするセル、T側が縦にするセルとする。敵を倒せない割り当て方について、敵のスコアだけカットが生じるような辺を張り、答えから引く。タワーから見てより遠くでよりスコアの小さい敵は攻撃しない。これで単調になる。横のタワーから見て、ある敵までのどこかで縦のセルがあった場合-(敵のスコア)としたいので、横のタワーの頂点から流量(敵のスコア)の辺を新しく作った頂点に張り、その頂点からinfの辺を敵までのセル全てに張る。縦については流れが逆 oo
629H: 結局 PI_{k=1}^N (x+k) でのxKの係数を求めたくなる。これはNについての2K次以下の多項式なので(∵Kについての漸化式がべき乗の和とかを使ってかける)、N<=2KぐらいまでをDPで求め、多項式補完する(多項式を求めるんじゃなくて、直接そこにNを代入したほうが楽) oo ☆
654H: s0-s1のパスではじめに使う頂点で場合分けしようとすると、その点の両隣のパスの辺でグラフを分けたとしても同じ置き方ができる。パスの長さが偶数のときはこれでよし。奇数のとき、s1をパスの中で最も早く使わなければいけない、という条件がつくが、これは単にs0のみでおけるということ。 O(N2) oo
657H: (a,b),(b,c)に辺があり(c,a)にも辺があるならa,b,cは横か縦に揃えて、(c,a)になければ(a,b,c)で横・縦別に置く。これが構成できるかO(N3)で確認。確認したら、1つ辺を決めると残りは全部決まるので、置いてく。連結成分ごとに独立なのでDP。孤立点のみは横に置こうが縦に置こうが同じなので別処理 oo
664H: dp[マージソートのどの区間に対応するか][何回比較するか][与えられたやつの対応する部分列とのLCPの長さ][LCPの次の値が小さいか大きいか(実際は、小さい/それより後ろはdont careのほうがいいかも)]:=通り数 でDP。メモ化再帰のほうが楽なきがするけどそれにしても大変。O(N5logN)な気がする(実際ははやい) oo
669H: 下の桁から埋めるDPをするが、重複が出ないよう、[Miを1を使いつつ1,M,…,Mjまでの和で作る通り数]を求め、Miずつ使う最小のコインで場合分けて足していく。この通り数もまたDPで計算する。Mi=M
M^{i-1}なので、同じようにMiずつ使う最小のコインで場合分けて足す。 oo ☆
671H: 上から埋めてくのは間に合わないが、斜めに埋めてくとWH2min(W,H)の状態でbitDPできる oo ☆

ooo

525H: 自己同型を求める問題であること、その上で角柱であることが分かればGoal。発想度高し ooo
526H: 1つ文字列を加えることで、i文字目までマッチしている確率ベクトルを変化させるような操作を考える。この操作は500回以上やっても500回やったのと同じ(500回以上前に付けた文字列は 「i文字目までマッチしている」に影響しないから) ooo
545H: ビットごとに制約がついているものとみなし、包除原理を使う。つまり、Σ(Sの元の桁の制約をすべて満たさない個数)(-1)^|S| を全てのSについて求める。集合Sを固定する。(Sの元の桁が全て1の要素の数)はR/Bを自由に決めていい。Sの元の桁の制約を破らなければいけないため、その桁が0の要素はR/Bの片方に寄せる。どちらに寄せるか2^|S|通りあるが、このうちi桁目とj桁目がどちらも0のAの要素があると、自由度が1減る。こんな感じの連結成分の個数を数えればいい。22020*20使うとTLEするので、探索にして毎ステップの計算がO(桁)になるようにする。 ooo
577H: それぞれのセルに、左右で塗るか上下で塗るかを割り当てることにすると、そのコストは (隣り合うセルで左右の塗りが異なる組+上下に塗るが上下にもうセルがない辺+左右に塗るが左右にもうセルがない辺)/2となる。(始点と終点を両方数えていることになるため) これはフローに変形できる。隣り合うセルの間に辺を、上下にセルのない辺にはSから辺を、左右…はTに辺を貼る。(最小カットを考えると理解しやすい) ooo
587H: ある辺の張り方が3彩色可能⇔ある長さWの文字列Sが存在し、全ての行について、その行の文字列がSかSのflip(NZ交換) NZのボードをグラフにしたとき、内部で次数が奇数の点があってはいけないことを考えると確かにこれが必要になる(もっと自然な導き方あるのかな…) あとはグラフをbitmaskとかで作りdfs、辞書順greedy ooo
590H: 始点からの最短経路長は、辺で結ばれたものの絶対値が1以下で、0以外は正ならなんでもOK.i番目の頂点への最短経路長がk以下かどうか、という頂点をそれぞれ作り、最小カットを求めればいい。(S側が正しくない述語、T側が正しい述語ととらえると、(i,k) -> (i,k+1)には(want[i]-k+1)2の辺を、さらに辺でつながった(i,j)には(i,k+1)->(j,k)にINFの辺を張ればよい) ooo
KUPC_K_Xor回廊: 綺麗な上汎用性が高そう。今更解いた。 ooo
667H: 順列が作るサイクルに注目する。両側にあるサイクル2つは対消滅できる。(サイズn,mとする。0-0,n-1-m-1,0-i(0<i<m-1),i-0(0<i<n-1),0-m-1,n-1-0の順でswapすれば綺麗に消える) これを使えば同じ側にあるサイクル2つも対消滅できる。サイクル1つは、i-0(0<=i<n),0-0とswapすれば消える。 ooo
518H: 分割統治を考えてみると、O(L2logK)でできる(行列を持つ必要はなくて、なぜならどの行も1行目にxorで入れ替えたものだから) 実は2つの間の(indexをxor、中身を掛け算)の畳み込みはO(NlogN)でできる。X=(A|B),Y=(C|D)とすると、Z=X$Y=(((A+B)$(B+D)+(A-B)$(C-D))/2,*1/2)でできる($は↑の演算) 合計でO(L log L logK) ooo

*1:A+B)$(B+D)-(A-B)$(C-D

ICPC Bangkok '16

ICPC バンコク大会に行ってきました.とても楽しかったです(小並感)久しぶりに更新。

1日目

  • 午前中に荷造りをして夕方成田から飛んだ.
  • 現地23時ごろに空港に着いた.自力ホテルまで移動を想定していたら,大会の迎えが来てくれた.ありがたい
  • 会津のチームもいたのでここで会釈したりした.
  • ここで換金するつもりが,迎えを待たせると悪いのでお金を換えずにホテルへ向かった.中心地に行くと両替できなさそうなので少し不安(この後クレジットカードでキャッシングを試みたけど結局ダメだったので,海外キャッシングの使えるwafrelkaに借りた)
  • ホテルに着く.腹が空きまくるので,近くにあるセブンイレブンでバーガーみたいなのを買った.人畜無害そうな見た目をしつつメチャクチャ辛いのでびっくりした
  • シャワーを浴びようとするけどお湯の温め方が分からないので水のまま浴びた.それでも大丈夫なぐらい暖かい
  • 寝ようとするもあまりに暑くて眠れないので,クーラーの主電源を直接叩いて点けた(実はリモコンがあったのだが,隣の藤原を起こすとよくないので電気をあまり点けていなくて気づかなかった)

2日目

  • 朝7時?とかに起きる.睡眠好きなので明らかに寝足りない
  • 大会が大学までのバン(ちょっとデカい10人乗りぐらいの車)を出してくれた.この後も移動は全部やってくれて助かった.1kmちょいとはいえ暑いので歩くと大変だったかもしれない
  • 時間があるので,食堂で朝ごはんを食べる.普通のメニューが30バーツぐらい(=100円)でうれC この前行ったときは空港からアクセスのいいレストランだったので100バーツぐらいはした気がする
  • 登録をしたりポロシャツを貰ったりする.ちょうど喪服期間だったので,選手が灰色で運営が黒だったりで珍しい(大体カラフルなので)
  • 開会式で踊りとかを見て,ルールの説明などがあった.早起きなのでまだ11時とかでビックリする
  • 午後はプラクティスがあった.ライブラリはこの日提出するルールで持ち込み忘れたので,プラクティス中に頑張って書いて印刷したりした(CxivDxiv伝統)(なお使う機会はなかった)
  • どうやら問題文やverdictが微妙に曖昧で他の人は困ってたらしい(伝聞)
  • この後buddyと呼ばれるガイドさんが,美術館や寺院やデパートに行きたいか聞いてきて,結局そのほとんどに連れて行ってもらった.本当に親切で,選手10人に対して6人ぐらいガイドがついててHuman Resourceを感じた.割とガイドさんたちの思いつきだった気がするけど,市内を自分で回るのは骨が折れるので本当にありがたい
  • ホテルに帰ったあと夜ご飯を食べに近くのフードコートみたいなところに行く.タイ料理があまりなかったけどその中で唯一面白そうだったタイすき焼きを食べに行く.
  • 肉に生卵がかかったものが出されて,卵をくぐらせた状態で茹でるやつ.美味しかった.
  • 寝る

3日目

  • この日は8時に起きる.それでも眠い
  • ギリギリまで寮にいたら朝ごはんを買う時間がなくなった.悲し
  • またバンで会場まで行って,入場などを済ませる.
  • 開始まで結構時間があったので,藤原とdegwerの顔の特徴をひたすら列挙してたら藤原から嫌な顔をされた.(ex.ホクロが左右対称な位置にない,鼻の先端が丸いとか)
  • ゆったりしてたら突然開始して緊張する.予め適度に緊張しておいたほうがいい
  • とりあえず12問のうち真ん中の4問を担当する.
  • E:問題長い,木,読むの後回し
  • F:文字列・ゲーム,読む,少なくともめんどくさそう.
  • G:単純なので考えてみるとフィボナッチ数のKの倍数項の和となることが分かる.そこから先は苦手の臭いがしたので誰かに投げようと思い後回し
  • H:問題文が分かりづらすぎる.
  • 読んでる間にdegwerがL?を通して,PCが空いていたので,慌てて手のつけられそうなEを読んで,案の定手はつけられそうだったので書き始める.必要な実装が多すぎて初手でやるのは間違いだったかな
  • 誰かが書ける問題でき次第代わりつつEを書いていく.実装できない間はHを読んだりFを詰めたりした.
  • Hの方が明らかに簡単なので,PCが空いたときに書いてみる.サンプルが合わない.誤読を心配し後回し
  • しばらくしてるとHのClarが入ってサンプルが間違っていることが分かる.少しデバッグして,提出(AC)
  • Eがぼちぼち完成する.出す.WA
  • なんか間違えてた.AC
  • Fが分かった気がしたので書く.微妙に考察が足りなかったので詰まりつつも出す.WA
  • フォーマットを間違えてたので出す.WA
  • 何が間違ってるのかさっぱり分からない…と思ってたら,まだフォーマットが間違ってた.AC
  • 藤原も同じ原因で,実質2AC獲得みたいなもんよ.これでかなりペナルティ無駄にした
  • Jをdegwerが書いてて,AとKが取り組めそうだったがAは時間がなさそうなのでKを考える.詰まりはしたが通すまではいかなかった.無念
  • コンテスト後はみんなでワイワイして,晩餐会の会場へ向かった.
  • 腹が減ってたけど飯までがやたらと長い,まあしょうがない.degwerとかがナプキン?で鶴を折って圧倒的交流してた.
  • 結果発表は,Seoul National UnivがFを通せば負ける展開だったが,FでWAを大量発生させてて助かった.2位
  • タイの偉い人に「お腹すいたでしょ!ようやくディナーだよ,ガハハ!」みたいな声を掛けられる.やっぱりな
  • 飯!美味しかった.
  • 帰って寝る

4日目

  • この日はアユタヤ観光.朝6時前に起きる.
  • バスで1時間強かかるっぽく,あまりに眠いのでバスで寝る.
  • 最初の寺院はビルマに破壊された遺跡で,なんとも不安になる形をしてた(いろいろ傾いてたり)
  • 次も似た感じの寺院だけど,今度はredecorationされてて色も違うし形もちゃんとしてる.階段の傾斜がすごくて登ると怖い.あと観光用の象が客を乗せて歩いてた
  • 次に水上マーケットにいった.ランチでトムヤムラーメンみたいなのを食べた.うまE.その近くで時代劇みたいなのを見た.ビルマとの戦いを扱ってた.タイが負けてる間に時間が迫ってきたのでバスに戻る.
  • 次もまた寺院に行った.仏像が寝てるものとか,大量の鶏の像とかがあった.
  • 帰りはbuddyとスマホで単語当てゲームをやってた.英語の勉強になりました(小並感)
  • ちょっと時間があったので,夕食を食べてお土産を買いに行く.
  • 空港まで送ってもらって,帰りの飛行機に乗る.

カプセルホテル宿泊記

情報オリンピック本選で1日目と2日目の間に家に帰るのが面倒だったので新宿でカプセルホテルを取りました。これからカプセルホテルに泊まる予定のある人は参考になることがあるかもしれません。


2015/2/7 に 新宿区役所前カプセルホテル に泊まっていました。 ビルの3-8階がホテルになってて少し見つけづらい。あと歌舞伎町に近いので厳重な注意が必要。
最初はフロントに行ってログインした。フロントに居る人を見ると客のうち1/4ぐらいは外国人ぽい感じで、従業員も完全に英語のプロだった。
ロッカーの鍵を預かるが、腕にどうやって付けるかがよく分かららなかったので教わる。力が足りないだけだった。
ロッカーに行って貴重品を置いて、風呂に入る。ロッカーはそこまで幅が大きくないので大きなスーツケースは入らなさそうだった。風呂はオリセンより豪華なぐらいで、ジャグジー・水風呂・普通の風呂・サウナがあった。洗面所には使い捨ての歯ブラシ・髭剃りがあって、小物を忘れた人でも大丈夫。
ロッカーには予め館内着とバスタオルが入っていてこれも助かる。
風呂に上がってから休憩スペースに行ったら思いの外ふつうのホテルっぽい内装でビックリした。インスタント食品の自動販売機やレストラン・電子レンジ・コインロッカーなどいろいろあった。
ひとまず部屋を見てみると、大体大きさは2段ベッドの片割れぐらいの大きさの壁に囲まれた領域がある、みたいな感じ。思ったよりは広かった(なんか棺桶より二回り大きいぐらいのがたくさんあるのかと思ってた)
f:id:hogloid:20150208104144j:plain
↑中からの写真
十分清潔だったけど、そもそもカプセルの部屋にカギが閉まらないのは問題かも。シャッターみたいなのを閉めると外側とは一応遮断されるけど、ある程度光は漏れてくるから完全に暗くないと眠れない人はアイマスクが必要。たまに宿泊階なのに喋る人がいて、音を気にする人は耳栓が必要。
部屋の空調も効いてて寝心地は普通によかったけど前述の光と音のせいであんまりよく寝れなかった。

朝になったら起きて着替えて鍵を返して出発。

まとめると、カプセルホテルは以下のような人に向いています:

  • 安く泊まりたい人
    • 他のふつうの宿の半額以下ぐらいで泊まれます
  • カプセルホテルに一度は泊まってみたいという人
    • 一度は泊まっても悪くはないです
  • 治安・光・音を特に気にしない人
    • これらを気にしないならデメリットはほとんどないです
  • 何も泊まる用の服・器具を持っていないが寝る必要のある人
    • ほぼすべてが用意されています


以下のような人には向いていません

  • セキュリティ意識の高い人
    • 鍵で閉められていない空間に寝るのがそもそも無理という人もいるはず。ロッカーも、頑張ればぶち壊せることが知られています
  • 人のたくさんいる場所が苦手な人
    • 基本的に小さいスペースを最大限に利用しているためいろんな場所の人口密度が高めです
  • 狭い空間で寝るのが嫌な人
    • 圧迫感を感じる人もいるかも

僕としては、もうそんなに積極的に泊まりたくはないです。鍵がないスペースに寝るというのはちょっとこわい。

今までに作った問題たち

そろそろ作った問題たちが増えてきそうなので、それらをまとめて感想を書いておきます。
まとめるのも面倒になるほどたくさん問題を作るぞ:punch:

  • Codeforces #162 Div1C/Div2E Choosing Balls
    • 初めて放出した問題。最初はa,b>=0だったり、クエリーじゃなくてO(NlogN)も許さざるを得ない感じだったけどsnukeやりんごさんの助けでCに置けるぐらいの問題になった。そもそもこの頃は問題のテストケースとかも作らなければいけないとは知らなかったなあ。初めてpolygon(CFの作問プラットフォーム)を使った。
  • Codeforces #263 Div1B/Div2D Appleman and Tree
    • 原案は僕で準備はsnuke。B問題が却下されたけど、日程は決まってしまったっぽいので大急ぎで作ったのがコレ。割と典型っぽいし特に思い入れは無し。
  • Codeforces #263 Div1E Appleman and a Game
    • snukeと一緒に原案を作った。僕だけだったらここまで難しくはできなかったなあ。ちなみにこのCFは夏ごろに3人でsnuke宅に集まって色々しながら原案を作ってた。楽しかったしこういう形式の作問もいいと思う:) この問題は難しい知識もいらないけどちゃんと難しい問題になってて好きです。(まだあんまり作ってないから何ともだけど)
  • Codeforces #286 Div1D Mr. Kitayuta's Colorful Graph
    • evima&yosupoとの合作回。想定解だと、ただ次数の小さい方に注目するだけでオーダーに√Qが出てくるのが面白いなあ、と思ったけど、ふつうの平方分割解もあるし、やっぱり√系の解法のものはFull Feedbackの場所に出すべきという思いを強くしました。div2のはこれの簡単版