blogskol

思わず声に出して読みたくなるブログ

PGBATTLE2022 せんべい D

大会サイト : PG BATTLE 2022 - [第5回]企業・学校対抗プログラミングバトル

問題 : https://products.sint.co.jp/hubfs/resource/topsic/pgb2022/2_4.pdf

せんべいでコンテストに参加した人間以外に現在ジャッジが提供されているかは分からず

問題概要

N 頂点の木が与えられる
各頂点 v には重み a_v が書かれている
連結頂点集合 S に対して、 F(S)= (\sum_{v\in S} a_v)^K とする
各頂点 v に対して、 \sum_{S\ni v} F(S) を mod 998244353 で出力

※ 問題文から F(S) の定義を少し変えています

制約

N\leq 10^3
K\leq 50
a_v\leq 10^8

解法

v=0 についての根付き木に対して木DPを用いた解法を考える
これが解けたなら最後に全方位木DPに直せば良い

F(S) は K 乗と言うのが非常に計算し辛い
一旦 F(S) の代わりに G(S)=\prod_{v\in S}a_v だった場合について解いてみる
この場合、 dp_v を v を根とした部分木についての解とすると、 C_v を v の子の集合とすれば、
dp_v = a_v \prod_{c\in C_v}(dp_c+1)
が成り立つから、解くことが出来る

ここで、 a^K=K![x^K]\exp(ax) であることに注目すると、
F(S)=K![x^K]\exp((\sum_{v\in S}a_v)x)
と書くことが出来る

更に \exp((\sum_{v\in S} a_v)x)=\prod_{v\in S}\exp(a_vx) より、 f_v=\exp(a_vx) と置くと、
F(S)=K![x^K]\prod_{v\in S}f_v
が成り立つ

従って、 G(S) の場合と同様に
dp_v = f_v \prod_{c\in C_v}(dp_c+1)
とすれば良い（最後に K! をかけたものを出力する）

コード

FPSライブラリと全方位木ライブラリは記事の最後に付けます

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<(n);i++)

#include <atcoder/modint>
#include <atcoder/convolution>
using namespace atcoder;
using mint=modint998244353;

#include <FPS>
#include <ReRooting>
using FPS=FormalPowerSeries<mint,55>;

int main(){
  
  int n,k;cin>>n>>k;
  vector<FPS> f(n);
  REP(i,n){
    int a;cin>>a;
    f[i]=FPS::exp(FPS(vector<mint>{0,a}));
  }

  mint fact_k=1;
  REP(i,k)fact_k*=i+1;

  auto merge=[&](const FPS&g,const FPS&h)->FPS{
    // dp_c の merge 
    return (1+g)*(1+h)-1;
  };
  auto score=[&](const FPS&g,const auto&e)->FPS{
    // merge された子を dp_v に合成する
    return f[e.to]*(1+g);
  };

  ReRooting<bool,FPS> tree(n,score,merge,FPS());
  REP(_,n-1){
    int a,b;cin>>a>>b;a--;b--;
    tree.add_edge(a,b,0);
  }
  vector<FPS> ans=tree.build(); 
  // ans[v]:vを根とした時の dp_v
  // ただし全方位木ライブラリの設計上、最後の score を取る操作はまだされてない
  REP(i,n){
    ans[i]=(1+ans[i])*f[i]; // 最後の score を取る操作
    cout<< (ans[i][k]*fact_k).val <<"\n";
  }
}

計算量

FPS は常に K 次までしか保存しないので、掛け算は O(K \log K)
掛け算の行われる回数は O(N) 回なので、全体計算量は O(NK\log K)
FPS を使わずに (\sum_{v\in S} a_v)^i を各 i\in{0,1,\dots,K} について持っておく解法もあり、本番はこれで通した
この場合 FPS の掛け算に対応する操作が O(K^2) かかるため全体計算量は O(NK^2)

ライブラリのコード

FPS ライブラリ

#define REP_(i,n) for(int i=0;i<(n);i++)
template<typename T,int MX>
struct FormalPowerSeries:vector<T>{
  using FPS=FormalPowerSeries<T,MX>;
  using vector<T>::resize;
  using vector<T>::size;
  using vector<T>::at;
  FormalPowerSeries()=default;
  FormalPowerSeries(int n,T a={}){
    resize(min(MX,n),a);
  }
  FormalPowerSeries(const vector<T>&f){
    int n=min(MX,int(f.size()));
    resize(n);
    REP_(i,n)at(i)=f[i];
  }
  FormalPowerSeries(const vector<pair<T,int>>&sparse){
    int n=0;
    for(const auto&[co,deg]:sparse)n=max(n,deg+1);
    n=min(MX,n);
    assign(n,T(0));
    for(const auto&[co,deg]:sparse)if(deg<n)at(deg)=co;
  }
  FPS operator-()const{
    FPS g=*this;
    for(T&a:g)a=-a;
    return g;
  }
  
  FPS &operator+=(const FPS &g){
    if(size()<g.size())resize(g.size());
    REP_(i,g.size())at(i)+=g[i];
    return *this;
  }
  FPS operator+(const FPS &g)const{return FPS(*this)+=g;}
  FPS &operator+=(const T &a){
    if(!size())resize(1);
    at(0)+=a;
    return *this;
  }
  FPS operator+(const T& a)const{return FPS(*this)+=a;}
  friend FPS operator+(const T&a,const FPS&f){return f+a;}
  FPS &operator-=(const FPS &g){
    if(size()<g.size())resize(g.size());
    REP_(i,g.size())at(i)-=g[i];
    return *this;
  }
  FPS operator-(const FPS &g)const{return FPS(*this)-=g;}
  FPS &operator-=(const T &a){
    if(!size())resize(1);
    at(0)-=a;
    return *this;
  }
  FPS operator-(const T& a){return FPS(*this)-=a;}
  friend FPS operator-(const T&a,const FPS&f){return a+(-f);}
  
  FPS operator*(const FPS&g)const{
    return FPS(convolution(*this,g));
  }
  FPS &operator*=(const FPS&g){
    return (*this)=(*this)*g;
  }
  FPS &operator*=(const T &a){
    REP_(i,size())at(i)*=a;
    return *this;
  }
  FPS operator*(const T &a)const{
    FPS res(*this);
    for(T&p:res)p*=a;
    return res;
  }
  friend FPS operator*(const T&a,const FPS&f){return f*a;}
  FPS operator/(const FPS g)const{
    return *this*g.inv();
  }
  FPS &operator/=(const FPS&g){
    return (*this)=(*this)/g;
  }
  FPS &operator/=(const T &a){
    assert(a!=0);
    REP_(i,size())at(i)/=a;
    return *this;
  }
  FPS inv()const{
    assert(size() and at(0)!=0);
    FPS res(1,at(0).inv());
    for(int i=0;(1<<i)<MX;i++)res*=(2-res*(*this));
    return res;
  }
  void strict(int n){
    if(size()>n)resize(n);
  }
  FPS pow(int n)const{
    assert(n>=0);
    if(n==0)return FPS(1,1);
    if(n==1)return *this;
    if(at(0)==1)return exp(n*log(*this));
    FPS res(vector<T>{1}),now=*this;
    while(n){
      if(n&1)res*=now;
      now*=now;
      res>>=1;
    }
    return res;
  }
  FPS operator()(FPS f)const{
    if(size()==1)return FPS(1,at(0));
    if(size()==2)return FPS(at(0)+at(1)*f);
    int n=size()/2;
    FPS s=*this;
    s.strict(n);
    FPS t(size()-n);
    for(int i=n;i<size();i++)t[i-n]=at(i);
    return s(f)+f.pow(n)*t(f);
  }
  static FPS differential(const FPS f){
    if(f.size()<=1)return FPS(0);
    FPS res(f.size()-1);
    REP_(i,f.size()-1)res[i]=(i+1)*f[i+1];
    return res;
  }
  static FPS integral(const FPS f){
    FPS res(f.size()+1,0);
    REP_(i,f.size())res[i+1]=f[i]/(i+1);
    res.strict(MX);
    return res;
  }
  static FPS log(const FPS f){
    assert(f[0]==1);
    return integral(differential(f)/f);
  }
  static FPS exp(const FPS f){
    assert(f[0]==0);
    FPS res(1,1);
    for(int i=0;(1<<i)<MX;i++)res*=f+T(1)-log(res);
    return res;
  }
};
#undef REP_

全方位木ライブラリ

//key_t:辺固有の情報　頂点固有の情報はラムダの方でキャプチャさせる
//sum_t:計算結果
template<typename key_t,typename sum_t=key_t>
struct ReRooting{
  struct Edge {
    int from,to;
    key_t cost;
    sum_t dp1,dp2;
    //dp1:部分木の内容
    //dp2:e=g[idx][i]の時、g[idx][0,i)のdp1の累積が入る
  };
  using F=function<sum_t(sum_t,sum_t)>;
  using G=function<sum_t(sum_t,Edge)>;
 
  vector<vector<Edge>> g;
  const F merge;
  const G score;
  const sum_t id;
  vector<sum_t> dp1,dp2;
  ReRooting(int n,const G &score,const F &merge,const sum_t &id=sum_t{})
    :g(n),merge(merge),score(score),id(id),dp1(n,id),dp2(n,id){}
 
  void add_edge(int u,int v,const key_t &c){
    add_arc(u,v,c);
    add_arc(v,u,c);
  }
  void add_arc(int u,int v,const key_t &c){
    g[u].emplace_back(Edge{u,v,c,id,id});
  }
private:
  void dfs1(int idx,int pre){
    for(auto &e:g[idx])if(e.to!=pre){
      dfs1(e.to,idx);
      e.dp1=score(dp1[e.to],e);
      dp1[idx]=merge(dp1[idx],e.dp1);
    }
  }
 
  void dfs2(int idx,int pre,sum_t top){
    sum_t now=id;
    for(auto &e:g[idx]){
      e.dp2=now;
      if(e.to==pre)e.dp1=score(top,e);
      now=merge(now,e.dp1);
    }
    dp2[idx]=now;
    now=id;
    reverse(g[idx].begin(),g[idx].end());
    for(auto &e:g[idx]){
      if(e.to!=pre)
        dfs2(e.to,idx,merge(e.dp2,now));
      now=merge(now,e.dp1);
    }
  }
public:
  vector<sum_t> build(){
    dfs1(0,-1);
    dfs2(0,-1,id);
    return dp2;
  }
};
//使用例:https://atcoder.jp/contests/abc222/submissions/26517686

伝統を重んじる日本人

日本

日本人は伝統を重んじる

長く続いた歴史あるものを尊重し、そう言ったものを軽視する人に対して「非国民」だと言ったりする

言うまでも無く、長く続いたものが必ずしも良いものとは限らない

長く続いたことが付加価値を生むこと自体は否定しないが、現代の価値観にそぐわないものや継続が難しいものは切り捨てるのが自然である

「100 年続いた伝統は無理してでも今後も続けた方が良い」と言う主張を持っている人間はそれなりにいるように感じられる
私はその価値観に賛同しないため、もしそのような運動のために自分の支援*1が強要されると不快になったりする
残念ながら現代そう言った文化は同調圧力を形成しているため、支援を断ると「非国民」とか「自分勝手」とか言われる
「文化祭はクラス一丸となって作るものであり、手伝う気の無い者は自分勝手」と言う考え方に似ている

冠婚葬祭なども概念として近く、参加したいものにだけ参加するようなことは社会的に許されない
渋々出席しながら「私が参加していることで誰が幸福になるのだろうか」と考えたりする

「伝統を重んじるべき」と言う感覚は決して持っていて当たり前の自然な価値観では無いと思うので、自分達が正しいと信じ込んで私を非難しないでほしい
そうは言っても人間が一般的に持っているメジャーな価値観では無いかと考えている人間のために、国外に目を向けてみる

外国

知っての通り「でんとう」は英語で "light" と書く
ここで Weblio 英和辞典を見ると、light には「軽い」と言う意味もあることが分かる

https://ejje.weblio.jp/content/light

つまり英語圏の人間は「伝統を軽んじるべき」と考えていると言うことである
海外に目を向けると価値観が絶対的なもので無いことが実感できると言う好例では無いだろうか

豆知識

伝統を無視する人間のことを「でんとうむし」と言います
今考えました

*1:税金の使用なども含まれる

チェーン店

スーパーとかチェーン店とかについて（2022.7） - blogskol

この記事の続き
前回の記事は調べるのが大変だったのでこっちは単に京都でよく見る店見ない店の列挙程度

京都でよく見る店

エディオン

ショッピングモールの家電量販店はここかジョーシンの二択
両方とも茨城には無いので最初新鮮だった

ヤマダ電機やヨドバシカメラ、ビッグカメラなどの有名どころもある
この間初めて京都駅北のヨドバシカメラに入った
完全に人間のキャパシティを越える広さで、却って何も見ることが出来なかった

なか卯

茨城には県に 8 店しかないため数店しか見たことが無かったが、京都は市内に 29 店もある
マイナー店だと思っていたのですき家や吉野家などと張り合うレベルでたくさんあってびっくりした

餃子の王将

茨城には 5 店しかなく、チェーン店と認識していたかも怪しい
京都は市内に 31 店もあり、至る所で見る
京大から数キロ北にある宝ヶ池店は全国の餃子の王将で一番メニューが多いらしい
卒業前には行っておきたい

デイリーヤマザキ

店舗検索サイトが使いづらくて具体的な店舗数は分からなかったが、京都市内で 3 店くらいは見た気がする
茨城も水戸近くにはそれなりにあるっぽい

天下一品

総本店が北白川にあるので当然たくさんある
おそらく京都に来るまで存在を知らなかった
北関東〜東北辺りは店舗数が少なく知らない人も多そう

大垣書店

ほとんど京都にしかない本屋
大きいショッピングモールには大体入っている
京都イオンの店舗が大きくて検索もしやすいのでオススメ
半分くらいの店舗ではカフェもやっており、綺麗な店内で本を気兼ねなく読めるので気に入っている

ココカラファイン

イズミヤによく入ってるドラッグストア
あれは「ココカラファイン+イズミヤ」という形態かもしれん
今調べたら普通に全国区だった
ただし関東は"首都圏"にばかり出店しているため茨城の人間には馴染み薄いはず

ドラッグストアとしては他に「スギ薬局」「ドラッグユタカ」「ドラッグひかり」「ウェルシア（ダックス）」など
茨城はもっぱらウェルシアかなぁ

ジャンカラ

西日本の人間が全国区だと思い込んでいる東日本の人間が誰も知らんカラオケ
値段が安く持ち込みも出来る良店
予約をしておくと当日はカウンターに行くことなく直接部屋に入ることが出来て、精算も機械なので店員と一切話さなくて良い
最近はクレジットカードを登録しておくことで精算機すら使う必要が無くなった

京都で見ない店

回転寿司

はま寿司とかくら寿司とか
南に行くとそれなりにあるんだけど、京大生の生息地域には少ない気がする
京大近くの店が潰れると「次は回転寿司が入るらしい」と言う噂が流れる事があるが、全部デマだった
くら寿司が多いかな、はま寿司やスシローも無くはないらしいが

ファミレス

ガストとかココスとか、あるにはあるけど全部南の方で、京大以北はサイゼリヤだけが数店
もう少し近所に欲しいとずっと思っている

ホーマック

見たことないなと思って調べたら東日本にしか無かった
同系列のケーヨーデイツーなんかは京大近くにもある

余白

狭い歩道に店のドアが接している店が多い
自転車で走るときなど非常に怖い*1
そういった店には当然駐輪場もなく、そもそも自転車移動が間違いかもと思わされる
カーブミラーも気持ち少ない気がするがこれに関しては嘘かも

*1:もちろん可能なら道路を走る

ARC142-C Tree Queries (too small)

C - Tree Queries

「N = 4 のケースで困った」と言う意見をいくつか見たので、そう言った時の対処法（荒療治）を紹介します
以下では木 T の頂点 u,v の距離を d_T(u,v) と書くことにします

解法1

\mathcal{T} を N 頂点ラベル付き木全体の集合とします
これはケイリーの定理より全部で N^{N-2} 個あり、例えばこちらの記事の証明 1 を参考にしてそれなりに効率的に全列挙することが出来ます

\mathcal{S} \subseteq \mathcal{T} に対し、dp[\mathcal{S}]を 「木の候補が \mathcal{S} である時、残り必要な最低質問回数」とします
「木の候補が \mathcal{S} である時、（回答に応じて行動を変えることで）どのような回答に対しても高々 dp[\mathcal{S}] 回の質問で答えを当てられる」戦略が存在し、「どんな場合に対しても dp[\mathcal{S}] より少ない回数の質問で答えを当てられる」ような戦略は存在しないと言うことです

| \{ d_T(1,2) \mid T\in \mathcal{S} \} | = 1 である時、明らかに dp[ \mathcal{S} ]=0 です
そうで無い時は「最悪の答えが返ってきた時の結果が最良であるような質問をする」ことを考えると、
dp [ \mathcal{S} ] = \min_{u,v} \max_{ k \in \mathbb{Z} } dp [ \mathcal{S}_{u,v;k} ]
が成り立ちます（ただし \mathcal{S}_{u,v;k} = \{ T \in \mathcal{S} \mid d_T(u,v)=k \} ）

この dp 配列を全て計算しておき適切に質問を繰り返すことで、必ず高々 dp[\mathcal{T}] 回の質問で答えを出力することが出来ます
当然 dp[\mathcal{T}] は 2N-1 以下である（そうでなければ問題が問題として成立しない）ことから、この解法の正当性が示されます

dp 配列の大きさ（key の個数）は 2^{ |\mathcal{T}| } = 2^{N^{N-2}} であり、これは N=4 の時に 2^{16}, N=5 の時に 2^{125} なので、N\leq 4 の時のみ使える解法になります

解法2

質問の種類は \binom{N}{2} -1 通りしかありません
もしこれらの質問を全て聞けたのならば、後に述べるように答えは簡単に求まります
従って、\binom{N}{2} -1 \leq 2N の時のみ全部の質問をしてしまうと言う解法を用いることで、N\leq 5 の時は解くことが出来ます

最後に質問を全て聞けた時の解法例を書いておきます
木の辺候補は回答が 1 であるような頂点対のみなので、そのような頂点対の個数が N-1 であれば実際に木を作って見ればよく、N-2 であれば 1,2 を結ぶ辺が存在することになるので、1 が答えになります

その他（上とは完全に別件）

テストケースが弱くて N=4,5 くらいでも落ちるケースが存在するコードが AC になっていると言う話があったはずです
AC しても必ずしもコードが正しいとは限らないので、upsolve をする人は手元でチェックコードを回すと良いかもしれません（N \leq 8 のラベル付き木全部に対して正しく動いているかなどは簡単に確かめられると思います）
逆に問題/テストケースを作る人は、\sum N \leq 10^5 などのマルチテスト問題にすると、一つのテストケース内に N が小さい場合を全部詰め込めて良いと言う話も出ており、確かに〜となりました

スーパーとかチェーン店とかについて（2022.7）

スーパーやチェーン店についての頭の中のあれこれを整理するため、現時点での全て*1を書きます
筆者は高校までを茨城で過ごし、大学は京大周辺に住んでいます（現在6年目）
以下、首都圏と書いたら特に断りのない限り茨城を含まないものとします*2
情報はホームページを見て書いていますが間違っているかもしれません（特に店舗数は数え間違えていそう）

スーパー

種類

カスミ

茨城に 108 店舗あり、大学に入るまで全国にあると信じて疑わなかった店
関東圏にしか無く、京都では誰も知らなくて衝撃を受けた
俺の中でスーパーの代名詞なので特徴は無い
スーパーの概念そのもの
本社 : 茨城県つくば市西大橋599-1

エコスグループ

ヤマウチやTAIRAYA、マスダ、エコスなどの系列
これもカスミと同じく俺の中のスーパーの概念
幼少期は一番近い（自力で行ける）スーパーがこっちだったためより馴染み深い
関東+福島にしか無く、京都では誰も知らない
茨城には 37 店舗
株式会社エコス本社 : 東京都昭島市中神町1160-1
株式会社たいらや本社 : 栃木県宇都宮市平出工業団地9-23
株式会社マスダ本社 : 茨城県取手市東6-10-8

ヨークベニマル

上二つほどでは無いがなじみ深くやっぱり全国チェーンだと思っていたスーパー
山形、宮城、福島、栃木、茨城にあり、茨城には44店舗
「ヨークタウン」って名前のショッピングモールとかみんな本当は知ってるでしょう？
後に述べるように鳥のマークの店
セブン&アイ・ホールディングスの完全子会社であるため、セブンプレミアムの商品などが置かれてる
本社 : 福島県郡山市谷島町5番42号

イトーヨーカドー

これもセブン&アイ・ホールディングスの子会社でマークも似通っているためヨークベニマルとの区別が付かない
こちらは北海道から近畿まで幅広い地域に存在するが、京都には無い
本社 : 東京都千代田区二番町8番地8

ジェーソン

関東一都六県に存在するディスカウントストア
安い飲み物が印象に残ってる
昔凍らせても美味しいカルピスが秋頃に 29円/1本 で売ってて箱買いした
本社 : 千葉県柏市大津ヶ丘2-8-5

とりせん

関東の田舎っぽい県にあるスーパー
名前は知っているが入ったことは無いかもしれない
今年創業110周年らしい
本社 : 群馬県館林市下早川田町700番地

西友

関東だけかと思っていたが今調べたら京都にもあった
長野と福岡にたくさんあるらしい
「他店の方が安かったらチラシを持って来れば同じ値段まで下げる」と家電店みたいなサービスをやっていた気がする
本社 : 東京都北区赤羽二丁目1番1号

ロピア

京都駅北のヨドバシに入ってるスーパー
関西にも少しあるがほとんどは首都圏にある
茨城にも一軒だけ存在
本社 : 神奈川県川崎市幸区南幸町2丁目9番地

業務スーパー

個性的な商品の多い店
オートミールなど輸入商品も多い
日本全国にたくさんあり知名度はかなり高いイメージ
狭くて客が多いのでじっくり商品を見て楽しむといったことはしづらい
株式会社神戸物産が運営
本社 : 兵庫県加古川市加古川町平野125番1

生鮮館なかむら

大学から近く感覚的にここら一帯で一番安価であり、大学生活で最も世話になっている店
でも案外京大生でも知らない人間がちらほら？
CGC グループ自体は茨城でも見かける
京都市にのみ 10 店舗存在する*3
本部 : 京都市左京区田中野神町18

グレースたなか

京都に来たての頃は生鮮館と同じくらい利用していた大学にそこそこ近い店
数年前に下鴨店が出来たが、それまでは１店舗のみであった
そこそこ安い
たまにコストコフェアをやっている
所在地 : 京都市左京区田中飛鳥井町40番地

フレスコ

京都で最もよく見るスーパー
ほとんど京都にしか無く、京都には 68 店舗（フレスコプチ・フレスコミニ・フレスコにっさん・フレスコスマイルを含む）
会社概要 によると、

  • プチ : 女性中心の新スタイル
  • ミニ : コンビニスタイルへの進化
  • にっさん : 株式を 100% 取得した他会社の「スーパーにっさん」をリニューアル
  • スマイル : 上と同様に「スーパースマイル食品館」「マイキッチンスマイル」をリニューアル
  • フレスコベンガベンガ（詳しくは後述） : 上と同様に「スーパーベンガベンガ」をリニューアル

福島と宮城にあるフレスコキクチはおそらく関係は無い？
24時間営業の店舗が多く、値段もそこそこ安い
ディスカウントストアの COREMO もやっている*4
COREMO に前入ったらアイスのガラスケースに張り紙がしてあって、気になって見てみたら二週間後のアイス半額の宣伝だった
本社 : 京都市下京区若宮通五条下ル毘沙門町33番地1

フレスコベンガベンガ

株式会社 フレスコ関東が運営するフレスコで、東京に 2 店舗と神奈川に 4 店舗
Venga はおそらくスペイン語で「いらっしゃい」と言う意味
会社所在地 : 東京都大田区西糀谷4-21-1　ナガイビル3F

ライフ

近畿圏と首都圏にのみあるスーパー
京都には 17 店舗
ライフのロゴがついた商品がそれなりに売っているイメージ
ぱっと思いつく3店舗が全て食品売り場とは別階で生活用品も売っていた気がする*5
本社 : 大阪市淀川区西宮原2-2-22

イズミヤ

京都だけでなく大阪でも割と見かけたスーパー
大阪にはファミリーマートとのコラボ店*6があるっぽい？気になる〜

  • イズミヤ : 衣料・食品・住居用品を幅広く揃える
  • カナート : ショッピングセンター
  • デイリーカナート : スーパーマーケット

と言った形で名前がついているらしい（Wikipedia 調べ）

また、これも Wikipedia によると、

  • 社名の由来は社名の由来は「ヤコブの泉」
  • カナートはアラビア語でオアシス（泉との関連性）
  • 全国各地に類似した名称の企業が少なからずあるが、それらとの関係はない

大阪にたくさんあるが、京都にも 13 店舗
本社事務所 : 大阪市淀川区野中南2丁目8番10号, 大阪市西成区花園南1丁目4番4号

エムジーショップ

主に京都市北西部にあり、全部で 7 店舗（全て京都市内）
生鮮館と同じくCGCグループの運営である*7が、CoGCa カードは使えない（CoGCaが使える加盟店一覧はこちら）
エコに力を入れているらしい？訪れた店舗には段ボールの回収所が付いてた
5 店舗が密集しているため 7 店舗しか無いにも関わらず北西で生まれ育った人間はもしかしたら全国チェーンと信じているのではないだろうか
本社 : 京都府京都市左京区静市市原町357-1

パントリー

東京から広島まで広い地域にあるスーパー
茨城には無く、京都で初めて見た
おそらく高級スーパーで、高級フルーツジュースやおしゃれなアイスなどが売られていた
飲料コーナーにコカコーラやファンタが無いのを見て、育ちの違い的なアレに衝撃を受けた
本社 : 大阪市福島区福島6-10-11

フレンドフーズ

高級スーパーその2
コカコーラどころかペットボトル飲料がそもそも売ってなかった
一店舗しか無いがホームページはかなりしっかりしている
住所 : 京都市左京区下鴨北園町10-6

スーパーマツモト

京都と大阪にのみ存在
京大周りにはあまり無いが、京都市だけで 10 店舗もある
ホームページの写真を見る限り駐車場が広い店舗が多そう？
会社住所 : 京都府亀岡市西竪町61-1

グルメシティ

ダイエーが運営しているスーパー
ダイエー自体がイオンの子会社であるため、topvalue の商品などが置いてある
京大から一番近い北山店は2階建てで 100 円ショップのワッツが入っていた
2階建ての店はそれだけで趣があると思います
ダイエー本社 : 東京都江東区東陽2丁目2番20号
ダイエー本店 : 神戸市中央区港島中町4丁目1番1

サンディ

関東、関西、岡山にあるディスカウントスーパー
茨城には無いため知らなかったが京都に結構あり、大阪には大量にある
500ml 29 円の水を一時期定期的に箱買いしていた
滋賀の店舗で国産白菜が一玉 70 円で売られていて衝撃を受けた
本社 : 大阪府大阪市淀川区西宮原2-7-50 YSサクラビル

大国屋

大学院の近くにあるスーパー
もう１店舗京都の西の方にあるが知らない
会社概要を読むと他にも 4 店開店してるがこれらは潰れたのかな
配置と言うか店の形？が他のスーパーとは異なるイメージ
アイスが入ってるショーケースの蓋がプラスチックでは無く少しだけ中の見える黒いメッシュだった
チラシページの店舗画像がとてもおしゃれ
本部 : 京都市左京区北白川久保田町20

メルシーマルギン

大学院近くにあるスーパーその2
一店舗しかないがホームページはしっかりしており、instagram もやっている
スーパーなのに日曜定休
住所 : 京都府京都市左京区浄土寺東田町47番地

フレンドマート

平和堂が経営するスーパー
滋賀に行く際調べたら大量にあった
入ったはずだがこれといって覚えていることは無い
マークがイトーヨーカドーに似てると言うので茨城出身の人間と通じ合ったが、東海出身の人間には通じなかった

世の中には同じことを考えている人間がいるらしい
こんな記事も教えてもらいました

note.com

実は京都市にも梅津店が存在する

平和堂所在地 : 滋賀県彦根市西今町1番地

ラ・ムー

大黒天物産株式会社が運営しており、大黒天payなるものが使えたはず
中部以西に広く存在し、関東などには無いが元々名前は知っていて、滋賀に行った際入った
今まで入ったスーパーの中で最も興奮した店舗であり、その特徴を上げると

  • 店も駐車場も大きい（滋賀が田舎だから？）
  • とても安く、見た事ないブランドの商品が激安で売られている*8（激安スーパーにありがち）
  • 通路の横幅がやけに広い
  • ドライフルーツなどの量り売りコーナーがある
  • 店の外壁に PAKU-PAKU と言う店が埋まっており、たこ焼きなどが格安で食べられる

ホームページには複合型メガディスカウントランドと書いてあるが、その名に恥じぬ店だと思う
大黒天物産株式会社の他の店舗としてはメガディスカウントストアのディオ、ディスカウントストアのディオマート、コンビニスタイルディスカウントのら・む～マート、100円均一＆ディスカウントストアのバリュー100、中小規模ディスカウントフォーマットのザ・大黒天があるらしく、出来る限り行ってみたい（ほとんどが岡山にある）
大黒天物産株式会社本社所在地 : 岡山県倉敷市堀南704番地5

丸善

滋賀にのみ7店舗存在するスーパー
滋賀に行った際メモはしており、かなり近くを通ったはずだが入った記憶が無い
ホームページを見るにコストコフェアをやっているらしいが、これは田舎スーパーあるあるなのか？

平和堂の子会社と言う情報をいただいた
滋賀を支配している

本社 : 滋賀県犬上郡豊郷町沢338

トライアル

店名ロゴがかっこいいスーパー
茨城にあり京都に無いので関東ローカルかと思っていたが、滋賀に行く際調べたらあった
四国を除く各地域にあり、近畿も 1 府 4 県にあるので完全に全国区 スーパーの割に意識が高いのか、ホームページにとても気合が入ってる
どうやらかなりいろんな種類の店舗があるらしく、IT に力を入れているとかなんとか（Wikipedia 調べ）
本社 : 福岡市東区多の津1-12-2 トライアルビル

KOHYO

北大路や京都駅のイオンに入ってるスーパー
京都の他に大阪、兵庫、奈良に存在
株式会社光洋が運営しているのでおそらく読みは「こうよう」
topvalue の商品が置いてあった気がする
本社 : 大阪府茨木市横江2丁目7番52号 ダイエー茨木プロセスセンター

スーパー玉出

大阪の有名な激安スーパー
いつか行ってみたい
豆知識 : 最近USB紛失事件で話題になった尼崎市は大阪以外で唯一玉出がある
会社の名前株式会社フライフィッシュって言うんですね
本社 : 大阪市西成区玉出中1-11-17 アイセ玉出ビル

個別店舗

ライフ二条駅前店
大きいライフ
とっても大きい
中が全部ライフだったか他の店が入っていたかは覚えていない

イズミヤ白梅町店
大きいイズミヤ
とっても大きい
100円ショップやドラッグストア、家電などいろんな店が入ってる
屋上に上がれるのがポイントで、京都で一番おすすめのスーパーを上げるならここ
屋上以外は大きい割に見どころがなく、スーパー自体は近所のイズミヤと同じ品揃えなのでつまらん
俺屋上が好きなんだな
煙なので高いところが好き

ローソンストア100 紫野泉堂*9
中にダイソーの棚がある
どうやらダイソーとコラボしてる店は他にもあるようで、スーパーの中にダイソーの棚が突如現れた事もあった
同様に京都の七条にはイオンとコラボしてるミニストップがある

京都と茨城

京都の小さめのスーパーに無いもの

  • 駐車場・駐輪場
  • イートインコーナー
  • トイレ

上記は茨城のスーパーには必ずある気がするんですが、おそらく反例は大量にあります
カニンガムの法則 を狙っているわけでは無いので、反例は出さなくて結構です

小話

茨城に住んでいた頃スーパーが入ってる二階建て以上のお店（ショッピングセンターなど）に行くといつもスーパーは一階にありました
「スーパーは建物全体で最も利用者数が多く、一階が一番利用者や仕入れ行者にとってアクセスが良いので、どこも一階にスーパーを配置しているのだろう」と幼い少年は思っていました

京都に来て初めて、地下のあるスーパーに入りました
一階では生活用品などが売られ、スーパーは地下にありました
そのとき私は瞬時に今までの仮定を捨て去り、
「冷たい空気は下に降りるので、食料品のために常にある程度気温を低く保たねばならないスーパーはその建物の最下階にあるのだろう」
と、新たな仮説を立てました
自分の持ってる情報に矛盾しない説をすぐに構築したのですね
これは私が最も自分の頭の良さを実感したエピソードです

小話2

チェーン店の方でより詳しく書くつもりなんですが、全国展開する店と地域展開する店の違いみたいなのが気になります
コンビニは多くが全国規模なんですが、スーパーは特定の地域にのみ数店から数十店程度の店が多くて、不思議な気持ち
あと「全国規模だと思っていたが実はローカルだった」と言う話が大好きなので、そう言うのはどんどん教えてください
スーパーに限らずチェーン店や方言、学校の行事などなんでも
お便りフォーム
単にこの記事の感想とか送っても良いです（ポジティブなものに限る）

小話3

イオンなど大きめのお店が田舎っぽいかどうかを人が判断するメカニズムを最近見つけました
衣類や生活用品を売っている店がイオン系列かどうかです
UNIQLO などの店がきちんと入っている店は田舎っぽくありません
「生活品売り場」といった名前の場所はいくら建物が大きかったりしても田舎っぽいです
大きめのスーパーなんかも同じことが言えます
イオンの田舎度合い判定の参考にしてください

スーパーを見るとき

遠出して知らないスーパーに入る際、どう言う点を見るといいのか
筆者自身あまり分かっていないが、意識していることなどをいくつか書き残す
普段買うものであれば相場を把握しているので値段の安い高いも分かるが、そうでないものはよく分からない
ある程度の棚をぼんやり物色するのはもちろんとして、特色が出やすいのは惣菜コーナーと牛乳だと思っている
牛乳ってスーパーの種類ごとに違う商品を扱っていませんか？そう言うイメージがあります
知らない牛乳を見るとテンションが上がるのですが、遠征中に購入は難しい
2泊くらいホテルを取っていた時は 1L の紙パックを買いましたが、そういった機会はあまり多くありません
広告もレイアウトの時点で結構店舗によって差が出るイメージがあります
おそらく大枠は共通のテンプレートがあると思うのですが、詳しくありません

チェーン店

長くなったので別記事で

*1:但しある程度自身と関係のあるところに限定

*2:これは自明では無い

*3:筆者が買い物をした経験があるのはおそらく5店舗

*4:今出川通の、百万遍と出町柳の間に最近できた緑のやつ

*5:ライフには生活と言う意味があるよ

*6:コラボと言う表現は適切では無さそう

*7:https://www.cgcjapan.co.jp/cgcgroups/group/area.php?area=%E8%BF%91%E7%95%BF

*8:納豆一パック40円など

*9:スーパーでは無いけど

競プロの環境

最適解ではありません
知見はいつでも募集中
いろんな人のコードを見よう

oj

oj を入れておく
以下の内容のいくつかは oj と重複している

エディタ

一番よく聞くので vscode

template

template-dir にデフォルトで欲しいファイルを全て置いておく
問題を解く時はこのディレクトリの中身を丸々コピーする（後述）

b.cpp

メインのコード
#include <bits/stdc++.h> や REP マクロなど欲しいもの全部書いておく
pragma region を用いることでエディタ上ではこれらのテンプレートは全て隠して置ける

tle.cpp

愚直解用のコード
b.cpp と同じ準備をしておく

make_random.py

入力生成をするコード
便利な関数を書いておく
例 INTS(l,r,n) : 各要素が l 以上 r 以下の、長さ n の配列を返す
木やグラフ、distinct な数列などを作る関数なども書いておくと良い 関数は全てさらに別の library.py に書いておけば import を書くだけで良くなる

cnt.txt

自分で新たに作ったサンプルの個数を数えるようのファイル
0 を書いておく

.bashrc

alias や関数を書いておくことで、ターミナルで色々実行できるようにする
PATH と書いてある部分は実際には絶対パスが入る

基本
alias g++='g++-11 -std=gnu++17 -D=__LOCAL -O2 -I PATH/acl -I PATH/local'

alias G='g++ b.cpp'
alias GTLE='g++ tle.cpp -o tle.out'

alias a='./a.out'

alias TLE='code tle.cpp'
alias RA='code make_random.py'

alias ..='cd ../'
mkcd(){
  mkdir $1
  cd $1
}

g++ の -D=__LOCAL で __LOCAL を define させてる理由は後述

新しい問題を解く時
np(){
  mkcd $1
  cp -r PATH/template-dir/ ./
  chrome_cpy
  oj d "$(pbpaste)"
  code b.cpp
}

例えば np a と打つと

  1. ディレクトリ a を作成しそこに移動
  2. a に template-dir の中身がコピーされる
  3. chrome_cpy は applescript を用いて現在 Google Chrome で開いているページのリンクをクリップボードにコピーする alias （中身省略）
  4. oj d "$(pbpaste)" によってそのリンクのサンプルをダウンロードする
  5. b.cpp を開く
愚直解との比較
C(){
  for _ in $(seq $1);do
    python make_random.py > input.txt
    ./a.out < input.txt > wrong.txt
    ./tle.out < input.txt > correct.txt
    if [ "$(diff --brief wrong.txt correct.txt)" = "Files wrong.txt and correct.txt differ" ];then
      echo "$(<input.txt)"
      echo "Wrong:"
      echo "$(<wrong.txt)"
      echo "Correct:"
      echo "$(<correct.txt)"
      cnt=$(cat cnt.txt)
      cnt=$(( $cnt + 1))
      echo "This sample is x-sample${cnt}"
      mv input.txt test/x-sample${cnt}.in
      mv correct.txt test/x-sample${cnt}.out
      echo $cnt > cnt.txt
      break
    fi
  done
}

ランダムケースを生成し、./a.out と ./tle.out の結果を比較
結果が異なっていた場合、入力と二つの結果を出力したのち、そのケースを test/x-sample1 として追加する（添字は毎回増える）
従って、以降 oj t をした場合既存の sample に加えて新しい hack ケースもチェックしてくれる

以上のことを C n で hack ケースが見つかるまで実行する
ただし n は実行上限回数で、hack ケースが見つからないまま n 回試し終わった場合そこで止まる

提出
TS(){
  out=false
  for f in test/*.in;do
    result=$(diff --brief <(./a.out < $f) ${f/.in/.out})
    if [ ${#result} -ne 0 ];then
      out=true
      break
    fi
  done
  if "${out}";then
    oj t
  else
    oj s b.cpp --yes
  fi
}

提出用の関数
test 内全て一致するか試し、撃墜ケースがあれば出力、無ければ提出をする
後でコンパイル機能付きのも作る

debug

local/debugに以下を書いておく
別に b.cpp に直接書いても良いが、local でしか実行しない関数なので #include した方がかっこいいと思う

#  define debug(...) debug_internal(#__VA_ARGS__, __VA_ARGS__)

template <class T, class... Args>
void debug_internal(const char* s, T&& first, Args&&... args) {
    constexpr const char* open_brakets = sizeof...(args) == 0 ? "" : "(";
    constexpr const char* close_brakets = sizeof...(args) == 0 ? "" : ")";
    std::cerr << open_brakets << s << close_brakets << ": "
              << open_brakets << std::forward<T>(first);
    ((std::cerr << ", " << std::forward<Args>(args)), ...);
    std::cerr << close_brakets << endl;
}

以下のようなことが出来る

//テンプレート

int main(){
  int a=3,b=4;
  char c='a';
  double d=3.5;
  string s="hoge";
  debug(a,b,c,d,s);
}
// (a,b,c,d,s): (3, 4, a, 3.5, hoge) と出力される

また、出力を自分で定義しておくことで以下のように他の型も扱えるようにしてある

//テンプレート

int main(){
  vector<vector<int>> v(5);
  REP(i,5)REP(j,i*2)v[i].push_back(i+j);

  pair<int,int> P={1,2};
  
  set<int> se;
  REP(i,10)if(i&1)se.insert(i);
  
  map<vector<int>,int> mp;
  for(auto ve:v)mp[ve]=ve.size();
  
  debug(v); // v: [[],[1,2],[2,3,4,5],[3,4,5,6,7,8],[4,5,6,7,8,9,10,11]]
  debug(se,P); // (se,P): ({1,3,5,7,9}, [1,2])
  debug(mp); // mp: [[]:0][[1,2]:2][[2,3,4,5]:4][[3,4,5,6,7,8]:6][[4,5,6,7,8,9,10,11]:8]
}

提出の際には働いてほしく無いので、手元のコンパイル時に __LOCAL を define させておき、コードに以下を書いておく

#ifdef __LOCAL
 #include <debug>
#else
 #define debug(...) void(0)
#endif

手元で debug の結果を見たく無い時は 2>/dev/null でエラー出力を無視する