いつも頭に問題を

競技プログラミング中心で思ったことを書いてく

AtCoder Grand Contest 009 B - Tournament

問題

B - Tournament
トーナメント形式の大会が開かれたが,不平等で何回戦なのかが人によってバラバラ
1番目の人が優勝した
1番目の人以外が誰に負けたかという情報が与えられる
トーナメントの深さが最小になるようにした時の深さを出力

考察

序盤は何も方針が立たなかった
とりあえずトーナメント表を作って比べていくと,多分貪欲に構築する手段が良さそうではある
例えば1に負けた人が5人いて,それぞれの深さが一意に定まるとして,2,2,3,3,3だったとすると,戦うべき順番も小さい方から貪欲に2,2,3,3,3と戦っていくと,それぞれの最終的な深さが7,6,6,5,4となる
つまり深さが浅い人ほど1と先に戦わせる事で深く,深さが深い人ほど後で戦わせる事で浅くするようにすれば最適っぽそう

続いて入力をどう扱うといいか考えていると,負けた人は勝った人へ有向辺を張る木構造ならうまく扱えそうだと思える
上の処理をいい感じにdfsしたいなと思うと木DPっぽい気持ちになったので1から下へ下がっていって,なんかうまい処理ができたら上に上がっていって1に入ってる値が答えになるようなものが作れれば良さそう
書いたら合うので投げるとAC,ウェイw

解法

a_iからiへ有向辺を張る木を構築する
戻るために親も持つようにした
各点で配列を保持する
これに対してdfsで下り,子が無い点は0を親の点の配列にpush,そうで無い点は戻りがけに自身の配列を降順ソートして,index+配列の値のmaxを親の配列にpushしていく
最終的に1の配列の中での同様の処理でのmaxが答えになる

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;
int mod2=998244353;
const int INF=1e9;
 
const int MAX_N=1e5+2;
vector<int> G[MAX_N];
vector<int> rG[MAX_N];
vector<int> dp[MAX_N];
 
void dfs(int p){
  if(G[p].size()==0){
    dp[rG[p][0]].push_back(0);
    return;
  }
  for(int i=0;i<G[p].size();i++){
    dfs(G[p][i]);
  }
  sort(dp[p].begin(),dp[p].end(),greater<int>());
  int maxn=0;
  for(int i=0;i<dp[p].size();i++){
    maxn=max(maxn,dp[p][i]+i+1);
  }
  dp[rG[p][0]].push_back(maxn);
  return;
}
 
signed main(){
  int n;
  cin>>n;
  for(int i=1;i<n;i++){
    int a;
    cin>>a;
    a--;
    G[a].push_back(i);
    rG[i].push_back(a);
  }
  rG[0].push_back(MAX_N-1);
  dfs(0);
  cout<<dp[MAX_N-1][0]<<endl;
}

Submission #4643424 - AtCoder Grand Contest 009

自力で解けてよかった
トーナメントという形で表現されているけど木構造に落とし込めるのがキモっぽい

AtCoder Beginner Contest 119 C - Synthetic Kadomatsu

問題

C - Synthetic Kadomatsu
目標とする門松の長さa,b,cと所有する待つの長さlがn個与えられる
2つの松をくっつける操作のコストを10
ある松を1増減させるコストを1
この時目標達成のためにかかるコストの最小値を求める

考察

nが小さいので全探索を考える
合成するという操作を一旦無視して考えると,aに一番近い松,bに一番近い松,cに一番近い松を選んでそれぞれの絶対値を取っていけばO(1)で答えになりそう
合成という操作と,増減の操作を分離して考えれば良さそう
松を順番に見ていって,i番目の松はaにくっつける,みたいな操作を全探索,それが終わったら各目標との絶対値をとるみたいな感じにすると良さそう
これはdfsを書けばいいので細かいミスに気をつけて実装する

解法

dfsで各松をa,b,c,使用しないの4状態に分類していく全探索をして,最後の松まで使ったら各目標との絶対値をとる

#include "bits/stdc++.h"
using namespace std;
#define int long long
#define endl '\n'
int mod=1e9+7;
int mod2=998244353;
const int INF=1e9;

int n,a,b,c;
vector<int> l(8);
int ans=1e5;
int deep=0;
int na=0;
int nb=0;
int nc=0;
int tmp=0;

void dfs(){
  if(deep==n){
    if(na&&nb&&nc)ans=min(ans,tmp+abs(a-na)+abs(b-nb)+abs(c-nc));
    return;
  }


  if(na)tmp+=10;
  na+=l[deep];
  deep++;
  dfs();
  deep--;
  na-=l[deep];
  if(na)tmp-=10;

  if(nb)tmp+=10;
  nb+=l[deep];
  deep++;
  dfs();
  deep--;
  nb-=l[deep];
  if(nb)tmp-=10;

  if(nc)tmp+=10;
  nc+=l[deep];
  deep++;
  dfs();
  deep--;
  nc-=l[deep];
  if(nc)tmp-=10;

  deep++;
  dfs();
  deep--;
}

signed main(){
  cin>>n>>a>>b>>c;
  for(int i=0;i<n;i++)cin>>l[i];
  dfs();
  cout<<ans<<endl;
}

Submission #4635874 - AtCoder Beginner Contest 119

汚ねえソースだ,後から見返せばもっといくらでも綺麗に書けそう
昔ならD問題として出てきそうかなと思ったけどそうでもない気がする
C問題でdfs全探索とかは昔から出てるしCにしては難しいけどDにしては簡単,最近は難化してるらしいし妥当みたいな感じだ

AtCoder Grand Contest 031 B - Reversi

問題

B - Reversi
カラフルな石が一列に並んでいる
同じ色の石を2つ選んでその間にある石を全て選んだ石と同じ色にする操作を何度でも行って良い
最終的にできる石の列の種類数を出力

考察

とりあえず隣接していて同じ色の石は無視して良さそうなので削除して考える
制約が1e5あるので線形かO(NlogN)くらいを考えていきたい
1212みたいなのを考えたら,121の部分を111にすると後ろの2を使って色を変える操作ができなくなる事を考えるとかなりややこしいので全探索かDPに頼りたくなる
同じ色の石に辺を張ってみたくなるのでノートに書いてみる
一番左の石から一番右の石まで行ける経路の数だと言い換えができそう
ノートで実験するとサンプル2の答えが1大きくなって
425424
のとき,1番目の4と3番目の4をつなぐ辺と,1番目と2番目,2番目と3番目の4をつなぐ辺を通った時で結果が同じになってしまう
数を増やしても意味があるのは一番近い同じ数だけっぽいのでやると答えがあう

解法

DPでひとつ隣へ進むか,今見ている石と同じ数字で右側にあり一番近い石に進むの2種類の遷移を行う

#include "bits/stdc++.h"
using namespace std;
#define int long long
//#define endl '\n'
int mod=1e9+7;
int mod2=998244353;
const int INF=1e9;
 
signed main(){
  int n;
  cin>>n;
  vector<int> a;
  vector<int> G[2*100001];
  for(int i=0;i<n;i++){
    int b;
    cin>>b;
    //隣接して同じ数なら削除
    if(i==0||b!=a[a.size()-1]){
      a.push_back(b);
      G[b].push_back(a.size()-1);
    }
  }
  vector<int> dp(a.size()+1,0);
  vector<int> bp(2*1e5+1,0);
  dp[0]=1;
  for(int i=0;i<a.size();i++){
    (dp[i+1]+=dp[i])%=mod;
    if(G[a[i]].size()-1>bp[a[i]]){
      (dp[G[a[i]][bp[a[i]]+1]]+=dp[i])%=mod;
      bp[a[i]]++;
    }
  }
  cout<<dp[a.size()]<<endl;
}

Submission #4617073 - AtCoder Grand Contest 031


なんかあっさり解けて複雑な感じだ

AtCoder Grand Contest 031 A - Colorful Subsequence

問題

A - Colorful Subsequence
文字列Sから同じ文字を含まないように部分列を取り出す組み合わせ数を出力

考察

正直わからんかった
最初トポロジカルソート とかしたくなったけどそこで手詰まる
全探索を考えると各文字を使うか使わないかの2通りがn個あるので,同じ文字がなければ作れる部分列は0文字を除いてn^2-1通り
ここから同じ文字を使うものを引こうとすると沼って詰んだ

解法

どの位置のaを使うか,どの位置のbを使うか,...,どの位置のzを使うか,のそれぞれの通り数を数えてかければいい

#include "bits/stdc++.h"
using namespace std;
#define int long long
//#define endl '\n'
int mod=1e9+7;
int mod2=998244353;
const int INF=1e9;
 
signed main(){
  int n;
  string s;
  cin>>n>>s;
  int ans=1;
  map<char,int> mp;
  for(int i=0;i<n;i++)mp[s[i]]++;
  for(char c='a';c<='z';c++){
    if(mp[c]>0)ans*=(mp[c]+1);
    ans%=mod;
  }
  ans+=mod;
  cout<<(ans-1LL)%mod<<endl;
}

Submission #4608027 - AtCoder Grand Contest 031

なんかこういう問題昔はサクサク解いてたイメージがあって速解きでレート稼げてたんだけど最近苦手意識がある
イメージだけど日頃からやってないとこういうのがダメになっていくんだと思った

今更就活を振り返る

大学院に進学してから早くも2年間が経過しようとしています,らてあです.
そもそも大学院に進学した理由として大きなウェイトを占めていたのは働きたくないからでした.
昔からなのか家庭環境からなのか,他にも色々あったような気がするけどかなり人付き合いとかが苦手でした.
知らない人と新たに関わることや,新しい環境に飛び込むのが怖くて嫌で,バイトとかも全力で避けてきました.
わかる人にはわかると思うんですがお店に入るのが怖かったりします.
最近は少しずつ思考を変えて自分をごまかし割り切り乗り切ろうとしてはいます.
研究に自分は向いていないこともよくわかり,修士1-2年の間で結局就活をしたわけですが,周りの人たちや環境に恵まれたのか,想像していたよりはずっと楽に終えることができました.
そんなわけで似た境遇の人とかに参考になればいいとか,実はそんなことは一ミリも考えてなくて自己満足で就活を振り返る記事を書きます.
冗長な記事になりそうなので目次を置いておきます.

入学直後

某就活エージェント社の人が就活に関連した話をしてくれて飯を奢ってくれるイベントがあるみたいな話を研究室の先輩からもらう.
就活が嫌で学部で何もしなかった僕はロクに企業を何も知らなかったのでなんとなく行ってみる.
優しそうなおじちゃんが食堂で話をするのにわざわざペットボトルのお茶を奢ってくれて僕含め学生3人に話をしてくれた.
そもそも何も知らなかったのでweb系とかSIとか研究職に分類されるみたいな話を聞いて何も知らなかったことを自覚する.
まあ大学院パワーでなんとかなるんやろとか思ってたけど自分は無能なので成績とかで同期に勝てないから推薦とか無理っぽいことをあとで悟る.

他にもいくつか似た会に参加して焼肉とかしゃぶしゃぶとか奢られながら就活の話を聞く.
これ割と精神的に辛くてあんまり話した内容が記憶に残ってない.
Twitterで愚痴って同期に励まされたりそういう人間認識を広めたりしてしまった.
ただで肉を食べることより知らない人と話す方が普通に辛いっぽい.
就活を終えた先輩になんでも聞く会みたいな奴で「就活なんてウチの大学院優秀だからどうとでもなる」とかばかり聞かされあんまり参考にならなかった記憶もある.
まあそういうことを聞かされると信じたくもなるしそう願いたくなってしまったりもしたがそもそも僕にとっては面接や電話そのものが辛いので幻想は打ち砕かれる.(当たり前)

他にも数社企業の人を呼んで飯を食べながら会社の概要を聞くイベントにいく.
すごく話しやすい兄ちゃんみたいな人だったので素直に働きたくない旨を伝えて,そんな社員とかいますか?みたいなことを聞いた.
後から思い出すと結構恥ずかしいっぽいけど,まあイメージしている働く事と実際の内容がかけ離れている場合もあるし,深く考えすぎなのと,世間の働くに対する話題が悪いものしか目立たないからそうなるのも無理はないみたいな感じだった気がする.
その場に来ていた会社の雰囲気はどうもその通りであったようには感じた.

インターン

夏のインターンに周りの人間が応募していて色々焦りつつ興味がありそうな会社を数社受けることにした.
そもそもインターンって何か知らなかったけど学部の同期が行っていた記憶だけがあった.
学部の同期はクソだったとかつまらんかったとか,ただの作業だったとか言っていて,いいイメージがなかったけど給料がもらえるとかそんな話を聞くとちょっとは期待が持てたのと,やっぱり焦りが大きかった.
結論から言うと4社受けて3社落ちて1社予定が合わず面接を辞退した.
精神的ダメージがとても大きかったが,受けた会社がレベルが高いような話も聞かないでもないし,コミュ障だし仕方がないのかなとも思った.
ここで落ちた1社の人事とご飯に行く機会があってお話をすると合格圏内だったけど定員があふれていて家が遠いから落としたとか聞かされた.
おかげで夏休みまるまる競技プログラミングをすることができた.

冬にもインターンに応募した.
面接を受けてコーディングテストを瞬殺したけどこれも多分コミュ障故落ちた.

逆求人イベント

何度か逆求人イベントに応募していた.
軽い面接みたいな感じで電話をもらって現状を話す機会があって,働きたくないので辞退したいと告げた.
いまだに働くことに恐怖を持っていたのですが,まあやっぱりそう言う思考が良くなくて,少しずつでいいから考え方を変えて言ってほしい,1ヶ月後また電話するし別の逆求人イベントどう?みたいな感じだった.
その1ヶ月で少しは気持ちの整理がついたので逆求人イベントに参加することにした.
確か11月とかだった気がする.

形式は企業の人事かエンジニアに学生のプロフィールみたいなのが配布されていて,気になる学生のブースへ行き30分くらいで話すみたいな感じで,最初にスライドを使って5分で自己紹介をする.
がっつり研究の話をしている人とか,興味ある技術の話をしている声が割と聞こえて来た.
僕は競技プログラミングの話と趣味の話と働きたくない話を自己紹介でしていた.
それに対する企業のリアクションは3種類くらいあって,半分くらいの人は素直さをすごく気に入ってくれた.
めちゃくちゃ印象が良くて是非受けてくれ〜とか一緒に仕事がしたいとかそんな感じだった,お世辞には見えないくらい真剣に言ってくれていたので多分本当だと思い込んでいた.
実際嘘ついて就活しても入社後に損するしそんなもんですよね〜みたいなことを言って置いた.
残りは今の君にはうちは受けて欲しくないけど思考はいいと思うしどうすれば良くなるか一緒に考えようって言ってくる人事と,むっちゃ厳しいことを言ってくるエンジニアとか.
前者はすごく好感が持てて,いろんなことに触れて興味を持てることを探す,その上でうちに興味が持てたら受けてくださいって感じだった.
後者は競技プログラミングは役に立たない論法をしていたので終わり.

懇親会で以前のイベントで働きたくないと告げた兄ちゃんと再開する.
イベントに来たことや,自己主張がしっかりできていた事をもう一人の人事から聞いたとかでめちゃくちゃ褒めてくれた,すき.
ピザ食って酒飲んで解散になったけど駅に行ったらすぐに再開してすごく励ましてくれて応援してくれた.
イベントとしては来てよかったなとかなり感じて,ここに来ていた会社のうち4社をのちに受けた.

就活

上記のような感じでなんとなく是非受けてって言われたからしたがって受けたため就活が始まった.
社の名前を出すのがためらわれるので察してほしい.

1社目

イベントで僕をすごく気に入ってくれて今まで面談した中で一番よかったとか一緒に働きたいとか社風にあってるとか言ってくれた人事の所.
スマホゲーの会社で,考え方とかはまあ好きかなって感じだったのと,昔遊んだことがあってゲームシステムが好きだった.
コード開示して有名になってて少しアレ.
コーディング試験があって,あと数秒あれば間に合ったけど間に合わなかったので0点になったっぽくて提出間に合わなかったんだけどってメールを送ったら提出させてもらえた.
その後一次面接があって,エンジニアと画面通話した,これも印象が良くて一瞬で落ちた.
なんやねん.

2社目

イベントで是非受けてって言われたけどあんまりいい印象を持っていなかった.
特に全分野に精通している即戦力的な人材を求めている印象があった.
スマホゲームを作っている会社.
AtCoderで競プロのコンテスト開いていたけど,開いた理由を聞いたら楽しそうだったからって言われた.
ウェブテストがあって,コーディングかと思ったらがっつり数学と物理とかだった.
3Dゲーを作るからか,そっちよりの知識をかなり要求していて,険しかった.
案の定落ちた.

3社目

インターン落ちた社
スマホゲーを作っている会社でAtCoderでコンテストをしたこともある.
某P社のサービスから応募した.
イベントにも来ていてかぶってゴメンって感じだった.
人事の人がなんでも話してくれてすごく印象が良かったので受けた.
コーディングテスト,人事面接,エンジニア面接2回が画面通話で行われた.
P社のサービスで面接のフィードバックが帰ってくるけど数行でべた褒めされていた.
面接した感じもすごく感じ良かった.
最終面接が東京であった.
行くと今までと打って変わって怖い人が現れ厳しく研究の話ばかりさせられこちらからは何も質問させてもらえなかった.
落ちたしフィードバックに何も書かれていなかった.
怖すぎる.

4社目

なんども出てくる気のいい兄ちゃん社.
画面通話で面談をして次の選考をメールするねと言われてから永久に連絡がなかった,終わり.

5社目

イベントでお話しした社.
検索エンジンと乗り換えアプリが印象的.
コーデイングテスト,画面通話で人事面談,エンジニア面接を経て東京で面接,大阪で人事面接で内定をいただいた.
東京では人事とエンジニアに向かって学業等で頑張った事をプレゼンすると聞かされていた.
メールでは資料を用意しても良いと書いてあったのでなしでもいいと思っていたら人事に「何も使わないんですか!?」みたいな事を言われて挙動不審になった.
日本語が宇宙一下手.
本質のプレゼンではICPCに向けて精進した話をした.
英語が苦手なので海外コンテストに出たり,チームで僕が明らか弱者なので自分にできることは何か模索して頑張った事を伝えた.
話がまとまっていて分かり易かったとかそんなリアクションだった.
大阪の人事面談では最終確認だけみたいな感じで,あっさり内定をもらった.

その後別の会社と迷ってる旨を伝えると,できる限り待ってくれることと,エンジニアとかと面談して一緒に考えていこうという事を言ってくれた.
ここまでするのは納得した上で入社してほしいからって言われてかなり好感が持てた.
エンジニアと2回くらい面談した.
迷ってる理由とかを伝えると内定承諾して受かったらこっちを蹴ればいいんじゃないかとか言われてそこまで言っていいのかアンタって感じだった,結果的にそうなってしまったけど.
なんか僕はかなり優秀な評価で内定が出たらしくて限界まで待ったけど内定が出た時期が早すぎたのでもう待てないと言われて内定承諾した.
後で辞退することになってしまったので,かなり謝ったし,理由や聞かれたことには全部素直に答えた.

6社目

最大手ゲーム会社.
昔から行きたかったので最悪記念受験でもいいと思って行った.
会社説明会に参加して久々にスーツを着た.
社員となんでも質問タイムみたいな時間があって好きなゲームとか話してた.
社内環境がいいかというと微妙っぽかった.
ただゲームに関して面白いアイディアがあればどの立場の人間でも提案できて,それが完成品に織り込まれると聞くとワクワクしてたまらなかった,
ESを書くと落ちた.

7社目

ICPCで見学に行って興味を持った.
京都でコードレビューのイベントがあったので申し込むと,知ってる競プロerも来ていてウケてたら知ってる競プロerが講師でもっとウケた.
イベントはとても衝撃的で刺激的で,感動的だった.
ここで受ける決意が固まったので.
ESを出してウェブコーディングテストがあって,しばらくして一次面接で東京に行った.
海外エンジニアと通訳がいて,自己紹介をするとホワイトボードに問題が書かれコーディングするって感じだった.
1時間だったけど問題は30分くらいで解けて,あとは質問時間だったのでくだらない質問もなんでもかたっぱしから聞いたら全部紳士的に丁寧に答えてくれた.
次が最終面接で再び東京で今度はホワイトボードコーディング1時間*3回だった.
自己紹介をするとすぐ始まって1時間ずっとコーディング,終わると次の面接官が入れ替わりで入って来てまたコーディングみたいな感じで終わったらヘトヘトになった.
問題は全部解けたけどコーディングで詰まる場面が多かった.
それでもとても楽しくて,伝わった時の快感とか最高だった.
期日までに連絡がなかったので落ちていて,悔しいけど納得できた.

8社目

AtCoder経由でメールで面談のお誘いが来たので東京へ行った.
複数回人事と面談をしつつ課題をこなして,エンジニア面談,偉そうな人と面談を経て内定をもらった.
今までの経験が生きていたのかはわからないけど素直に自信を持って自分の意見が述べられていたと思う.

思ったことポエム

就活とても辛かったです.
多分僕が受けた業界に限った話かもしれないんですけど,素直さが大事で,嘘で固めて面接官を騙して入社したとしてもその後どこかで違和感を感じたりすることが多いと思います.
就活はマッチングみたいな感じで,僕みたいな人間でも社風にあっているとかで必要としてくれる会社もあれば,全然相性が悪い会社もあると思っています.
なので素直に働きかたに関する考えとか,エンジニアに対する考えとかそういうのが喋れてよかったなと思いました.
同期の皆様や東京に行くたびに空いた時間を狙って遊んでくれた人々には感謝します,ありがとうございました.
なんかまずい記述があれば指摘くだされば直しますのでよろしくお願いします.

AtCoder Beginner ContestのD問題はいいぞ

この記事は「Competitive Programming (1) Advent Calendar 2018 - Adventar」の21日目の記事です.

ちなみに去年は連続ACを8ヶ月続けた事について書きました.
ratea.hatenablog.com
想定読者はAtCoder緑上位~水色くらいです.
それより上の人は多分つまらないですごめんなさい.

[目次]

大学院進学とともに競技プログラミングをはじめました,1年と8ヶ月くらいになります.
永遠に水色ですどうもありがとうございました.
f:id:ratetion:20181206012529p:plain
shichinomiya - AtCoder
個人的に速解きだけで水色まで上がったけどあまり学習しなかったのでそこで停滞してしまったという印象があります.
ABCもまあまあ埋めました(全部じゃないんかい)
f:id:ratetion:20181206021404p:plain


経緯

CODE FESTIVAL2018に向けて精進していた時によく解いていたのがAtCoder Beginner ContestのD問題でした,特に昔の物をよく解きました.
解いていて感じた事として,よく名前を聞くが,問題を解いた事がなかったり,実装経験がないアルゴリズムやデータ構造が出題されている事が多いように思いました.

これはどうでもいいんですが以前Yazaten氏に
「らてあ君って意外とレートの割にアルゴリズムとか知らないよね」
みたいなことを言われました(要出典)
何から学んでいいかわからないという僕のような人は特にABCのD問題を埋めていくことをお勧めします.
実際のところ,自分がちょうど解けるかどうかの問題を解くのが成長につながると思うので.

おすすめ問題

全部です.

すいません嘘です,優先的に解くべきだと僕が感じるものを偏見で列挙するので上の内容に共感した人は是非解いてください.
ネタバレになるので白文字で感想を書いておきます.
あくまで感想なのであてにはしないでください.
解説開きたくないけどヒント欲しい時に役に立つ可能性もあります.

D - マーブル
難しい,DPにこういう使い方もあるんだなぁという感じ,こういうややこしい問題もしっかり考えればDPで解決できちゃうのはいい知見っぽそう

D - おいしいたこ焼きの焼き方
DPでも累積和でも,まあよく見ると思う

D - トランプ挿入ソート
こういうのを知らないから驚かれたりするんだろうか,最長増加部分列

D - 禁止された数字
桁DP,君もpekempey先生の記事で桁DP入門しよう!https://pekempey.hatenablog.com/entry/2015/12/09/000603

D - 金塊ゲーム
これめっちゃ難しいと思う,強い気持ちでしっかり詰めたDPを書いて圧倒的成長

D - 浮気予防
蟻本を開いてフローに入門しよう

D - 阿弥陀
これ賢い,ダブリングってすげえと思う

D - 閉路
ダブリングを出した次の回でLCAを出すとか教育的すぎると思いませんか?

D - 高橋くんの苦悩
DPに慣れてきたな〜って思うと解けたい

D - 食塩水
これは誰もが通る道だと信じたいとても辛い教育的だと思う

D - トレジャーハント
最近似た問題が出たんだけど僕は解けなかったけどみんなド典型って言ってて辛かったよ

D - 塗り絵
木DP,ちょっと捻らないとダメな気持ちになるんだけど解説曰く簡単らしい

D - プレゼント
これもめっちゃ解く価値があると思った,あと蛍光灯とか似てる

D - 道路の老朽化対策について
UFを貼ると通る,僕は最小全域木でUFを学んだんですがこれで入門するのもいいんでしょう

D - 徒競走
トポロジカルソートのbitDPのなんかややこしい感じなので整理して頑張りたいやつ

D - 井井井 / ###
なんか似たような問題よく出るような印象ある

D - Built?
最小全域木を生やす

終わりに

ハァハァ...今日のところはこの辺にしといてやるよ...
いやまあここであげてないD問題も全部価値あると思うんでそのうち僕も全部埋めます.
個人的にですが,昔の方が教育的な問題が多いようには感じます.
CODE FESTIVALにこそ行けなかったものの,CODE THANKS FESTIVALでは上であげた問題に似た問題が2問は出て両方解けたので,かなり精進してよかったと思ってます,パーカーこそ得れませんでしたが.

明日はnotさんの「JAGの作問環境」です.
かなりの量を作問されてるので†楽しみ†ですね.

硬派パズル,the Sequence [2]の紹介

はじめに

この記事は「プログラマーにオススメしたいゲーム紹介 Advent Calendar 2018 - Adventar」の18日目です.
なんか最近スマホゲーとノベルゲーくらいしかやってないのでスマホゲーで面白かったパズルを紹介します.
似たようなものがsteamに転がってた記憶があるのでそっちやった人には物足りないかもしれないけど後半の難易度は凄まじいのでそう言う方にも是非

概要

iOS版,Android版があります.

the Sequence [2]

the Sequence [2]

  • Maxim Urusov
  • ゲーム
  • ¥240
play.google.com


値段は240円(iOS),220円(Android)です,僕のご飯3食分です.
因みに[2]と言うだけあって1もあります.

[the Sequence]

[the Sequence]

  • Maxim Urusov
  • ゲーム
  • ¥240
play.google.com

1では4方向だったのが2では6方向になってます,なにがやねん.

ルール

すごく基本的なルールとして,ユニットをゴールへ5回運ぶことが要求されます,簡単ですね.
f:id:ratetion:20181217003317p:plain
こんな感じの画面です,このゴールとユニットの周辺の何もないマスにシーケンスを配置してゴールまでユニットを運ぶのが目的となります.
5個運ばないといけないので注意が必要です.
f:id:ratetion:20181217003441p:plain
シーケンスはこんな感じで好きな数使えます,後半にいくにつれてシーケンスの種類が増えていきます,とりあえず置いて見ましょう.
f:id:ratetion:20181217003544p:plain
置きました,このシーケンスは矢印の方向に1マスユニットまたはシーケンスを押す効果があります.
置いた順,又は設定した順にシーケンスが動作して,壁にユニットをぶつけたりして動作不可能になるまで動作し続けます.
なのでこの場合はこの画像がこのままクリアとなります.
またどのシーケンスも押す,引くの切り替え等が可能で,1マス引く効果を持たせることもできます.
f:id:ratetion:20181217003737p:plain
基本ルールはこれだけです,シーケンスには他矢印の列に乗っているユニット,シーケンスを全て押し引きする,シーケンスの周辺を回す,シーケンスそのものの向きを回す,シーケンスの押し引きパターンを入れ替えるなどがあります.
全部で100ステージあるらしくて,僕は80ステージくらいで詰んでます.

序盤の例題

1問だけここで解いて見ます.
ネタバレになるのでここまでの僕の素晴らしい解説で書いたくなってしまった人はこの記事をツイートしてついでに星もつけて,そのあとブラウザバックして購入してきてください.

他にももう少しギミックがあるんですが,ここで解説した内容だけで解ける問題を選びました.
f:id:ratetion:20181217004136p:plain


解説

まずはじめに下のユニットを動かさないと始まりません,とりあえず下のユニットに対して引きます.
f:id:ratetion:20181217004436p:plain
これを動作させるとこうなります.
f:id:ratetion:20181217004759p:plain
今置いたシーケンスが邪魔になるので退けます,左下から押します.
f:id:ratetion:20181217004902p:plainf:id:ratetion:20181217004913p:plain
これでまた上に引っ張れるようになったのであとはゴールへ運んで,動かした1のシーケンスを戻してやればクリア.
f:id:ratetion:20181217005026p:plain
1個目のユニットをゴールまで動かしたあと,初期状態に戻っているのでこのまま動かせば5個同じように運べるのでクリアです.

これはステージ15とかなんですが,シーケンスが押せるみたいな説明がなかったのでINF時間溶けました.

終わりに

拙い記事で申し訳ねえ申し訳ねえ.
なんかアルゴリズムっぽいしパズルだし雑にプログラマーそう言うの好きやろがとか思って選んだんや,俺は好き.
まあ記事じゃ魅力伝えきれないし,ちょっとでもおっとか思った人は買って見てくれ.
240円あれば3食飯が食えるのでリスキーだと思った人はYouTubeに動画も少しは上がってるからそう言うの見てから買うか決めたらいいと思う.
ちんちん.
明日はfalさんがハースストーンの新環境やってから2週間たった感想を書くらしい.
奇遇にも僕もハースやってるんで個人的に勝手に楽しみにしています.
それでは.

ICPC2018 アジア地区横浜大会参加記(JAGサイド)

こんにちは,ICPC大好きおじさんのらてあです.
12月8-9日に横浜で行われたICPC2018 アジア地区横浜大会にJAGからボランティアとして参加してきました.
僕は去年は選手だったので去年の記事を置いておきます.
ratea.hatenablog.com

普段よりは少しだけ真面目に書きます,面白かった出来事は多分Twitterに書ききったのでそちらを.
何か書いててまずいことがあったら修正しますのでお教えください.

登録

JAGのslackにボランティア募集のメッセージが流れてきたのでとりあえずICPC用のSlackに参加した.
登録フォームに必要なことを書いて,集合時間とかわからなかったので備考欄に遠方からの参加のため間に合わないようなら不参加でお願いする旨を書いた.
クレタリーの方からメールが着てもう一泊用意するから7に横浜来れるなら宿泊して8の朝から参加しないかというメールで,予約の関係で至急返信するように書いてあったので条件反射で行きますお願いしますとメールしていた.
後になって,あまり想定されてないってことは遠方からの参加勢は自分だけじゃないか,ボランティア未経験の僕に交通費と宿泊費だけでわんさか出してもらっていいのかみたいな葛藤があった,手遅れなんですけど.

前日入り

出してもらう金額分の働きができるのか不安でしょうがないけどとりあえず新幹線に乗り横浜へ.
マニュアルを2回じっくり読んだ.
Yazaten,しょラーさん,odanさんとご飯へ行った.
しょラーさんとodanさんとは久々に会ったんですがなんかいつも通りで変な感じで楽しかったです.

8日

ホテルの朝食を食べて会場へ行って受付でTシャツと名札をもらう,しばらくして集合があって,4班くらいに別れて作業をすることになった.

午前

なんか一発で別れて,誰もこの仕事嫌とか言う事なくささっと分担してて(当たり前かもしれないけど僕はすごいと思った),人が少なそうなデバッグ班になった.
デバッグ班は主にIDEがクラッシュしないかとかを確かめるのが仕事で,片っ端からIDEを起動して世界に挨拶をしていた.
選手は3人だし3つ同時に起動しとけばええやろと思っていたら素晴らしいデバッグだとか言われてなんか面白かった.
他に配信チェックとかを確認して,大丈夫っぽかったのでふうせん班に合流した.
ふうせん班は紐に輪っかを作ってふうせんを取り付けヘリウムを注入する作業だった.
IOIで余ったドワンゴのボールペンがふうせん止めとして使われていてなんともシュールな光景だった.
practice用のふうせんを作りきったので,膨らませるのはやめて本番用の輪っかまでをある程度作って終了した.


どっかにいます.
ご飯を食べて再集合とのことだったのでお弁当をいただいた,さすがYokohama飯がうまい.
きゅうりさんと喋っていて僕の名字と僕のHNは知ってるけど同一人物とは知らなかったとか,自然言語は難しいとか外国人エンジニアは遅刻はするが終了時刻はキッチリ守るとかそんな話をしていた.

午後

practice準備が始まった,僕は英語が得意ではないんですが,英語に強い人がほとんど受付班になっていたのでアリーナ班になってしまった.
新幹線でマニュアルを2回読んだおかげで説明された内容を全て知っていました.
基本的にはアリーナを巡回して質問対応をする仕事で,わからなかったらセクレタリーを呼ぶようになっていました.
選手が続々入場して来たんですが知り合いが多すぎてあまり話すと怒られるので(不正の疑惑が出てしまう)ごめんねと言う感じでした.
オープニングが終わってpracticeが始まったので,巡回仲間がいなさそうな列を選んで歩く.
トイレ行きたいとか明日お弁当持ち込みたいとかペットボトルの蓋は閉めてねとかそんな事を英語で対応しました.
出来なくはないけどビビって声が小さいのを自覚していました.
中盤から足が痛くて辛かったけど考察の会話とかが聞こえて来て楽しかったです.
グラフを描いているチームやら,「森になるから」とか会話しているチームを見て混ざりたいと思っていました.

practiceが終わり選手たちが退場するとゴミの回収をし,翌日のパスワード用の封筒作成をしました.
封筒作成は紙をハサミで切る人とシールを剥がす人と貼る人とテープをちぎる人とテープを貼る人がいつのまにか出来てて,すごい効率で封筒が生産されていて,昔受けた授業で似たような作業をやって全然うまく行かなくて「作業って計画が大事でしょ?この講義ではそう言うことから学びます」とか言われたのを思い出したんですが,ここの人たちは初めからそれが出来るのか,同じ講義を受けたのかのどっちかだと思います.

その後僕を含めた3人を指名し「テレビを作って」と言われました.
正確にはテレビ台みたいなもので,割と組み立てが大変らしかったので説明書とにらめっこしながら組み立ててました,去年組み立てた人からも脅されるほどの難易度でした.
組み立てが終わるとJAGは既に解散してご飯に行ったとかで,残ったメンバーでご飯に行きました.
なんか晩ご飯代を出してもらえるらしくて,それ削ってチーム増やして欲しいとかぼやいたらチーム増やす金に比べたらずっと安いし英気を養って翌日頑張ってもらわないといけないからねと言われて,最初の方に書いてた交通費とか諸々もどうでもいいっぽいことに気づいて安心した.
中華街が近くにあってサイコーでした✌️

9日

開場まで

昨日組み立てたテレビを設置と準備しに行く.
なんかネットワークとかがゴタゴタしてコンテスト開始に間に合わなかったけど,ほぼ影響ないくらいで済んでよかった.

コンテスト

設置が済んだら急いでふうせん,印刷物配りに合流した.
こちらの仕事はシステム化されていてプリンター前係から受け取った印刷物にチーム名と解いた問題が書かれているか,さらに印刷物が渡されるので,指示に従って該当チームに届ける.
誤配はやってはいけないので毎回しっかり確認して届けるようにしていた.
1時間程度ごとにアリーナ巡回とふうせん配りを繰り返していた.
ふうせん配りを待っている間に問題を考察したり配信を観戦していて,盛り上がっていてみんなICPC好きすぎるし,善意というか好意というかそういうので成り立っているんだなぁと思った.
すごいエンジニアとかが無償でふうせんを運ぶお仕事をしている.
そんな感じで適宜アリーナとふうせんを行き来してるとコンテスト終了間際になった.
アリーナを巡回すると足が痛くなり,巡回から戻ると腰が痛くなりみんなすげえとか思ってたけどみんな足が破壊されたとか言っててみんなすげえ.
順位表が凍結すると,コーチ向けの順位表ディスプレイ(組み立ててたテレビ)がいらないので回収に行った.
解体して箱にしまう,組み立てた記憶が新しいからかすごい速度で完了した,RTAなら全一取れます.

懇親会まで

選手たちが退場し会場片付けが始まった.
ここでも何度か班分けとかしててみんな積極的に参加していて圧倒されるばかりだった.
ゴミ掃除とふうせん回収をして,椅子を収納,壁のふうせんも剥がしてPCとディスプレイを仕分けして移動,LANケーブルと電源ケーブル回収と仕分けなどをして人があまりはじめたので,Yes/Noおじさんを見に行っていいようになったのでホールへ移動して秋葉さんの圧倒的スピーチや順位発表を見ました.
秋葉さんかっこよかった.

懇親会

終電の影響で最後までいれないことがわかっていたので,セクレタリーの人に伝えて(すでにわかられていた,ありがとうございます)最後の片付けに参加できなくてごめんなさいと行って帰れる準備をしておきました.
懇親会では,競技終了まで選手との会話ができなかったので競技中に目があった人片っ端から話しかけに行ったり欲しいノベルティをもらったりして来ました.

帰りの準備をしていると,さっきのセクレタリーの人がいて,入り口付近におにぎりとかあるから新幹線ででも食べてと言ってくれたので移動中に頂きました.
帰宅し今に至ります.

ポエム

ICPCの手伝いをして思ったことですが


がおおよそ全てです.
記事内でも何度か書きましたが,作業効率がいいし積極的な人しかいないしすごかったです.
去年はわからなかったけど,本当にたくさんの人が携わって成り立っている大会であることがよくわかりました.
来年も可能であれば必ず参加したいと思っています.

とは言えどの仕事も人数はギリギリで,みんなが優秀だから成り立っているような印象を受けました.
あなたも次回から参加してみませんか?
と言うことでICPC引退後の方はまずJAGへ参加!
Join - ACM-ICPC Japanese Alumni Group
やっぱりこんなオチになりましたね,ここまで読んでくださりありがとうございました.

JAG夏合宿2011Day3F Beautiful Currency

問題

Beautiful Currency | Aizu Online Judge
数列が与えられる
数列の要素を変更してa_{i+1}%a_i==0になるようにしたい
仮にa_iからbに変えたいとき,変更コストを|a_i-b|/a_iとする
この変更コストの最大値の最小値を求める

考察

なんかDPっぽいんだけど制約が怪しくて間に合うかわからない
DPするならdp[i][j]を,数列のi番目の数をjにする時の最小コストとするとうまく行きそう
この時更新範囲はjの倍数の部分だけ行えばいいのでjを全探索すると
\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+...+\frac{n}{n-1}+\frac{n}{n}
になるのでO(NlogN)になる
これ知らんかった



ここで各aの変更する範囲が1e5ではダメでWAが出るんですけど,適当にどんなに大きくしても1e5*20でしょって思って出すとMLEする
答えは最大値の最小値なのでどんなに大きくても1以上にならないようにできるなぁと思うとa_n番目を頑張って変更する時が最大値になるのでa_n*2が最大とわかるので1e5*2まで変更すればいい

#include "bits/stdc++.h"
using namespace std;
#define int long long
int mod=1e9+7;
const int N_MAX=1e5*2+1;
 
signed main(){
  int n;
  cin>>n;
  vector<double> a(n);
  for(int i=0;i<n;i++)cin>>a[i];
  vector<vector<double> > dp(n+1,vector<double>(N_MAX,1e9));
 
  for(int i=1;i<N_MAX;i++){
    dp[0][i]=abs(a[0]-i)/a[0];
  }
 
  for(int i=1;i<n;i++){
    for(int j=1;j<N_MAX;j++){
      for(int k=j;k<N_MAX;k+=j){
        dp[i][k]=min(dp[i][k],max(dp[i-1][j],(abs(a[i]-k)/a[i])));
      }
    }
  }
 
  double ans=1e9;
  for(int i=1;i<N_MAX;i++){
    ans=min(ans,dp[n-1][i]);
  }
  cout<<fixed<<setprecision(20)<<ans<<endl;
}

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3265223#1

まあ解説記事とか見つからなかったし知見も得たのでとりあえず記事にしたけど解説になってるかわからん許して

CODE THANKS FESTIVAL 2018 参加記

どうもみなさん,らてあです.
11月25日に行われたCODE THANKS FESTIVAL 2018に参加してきましたので参加記を書きます.
いつものことなんですが時系列のクソポエムほのぼの日記です.
ついでに去年のはこれです.
ratea.hatenablog.com
一回twitterアカウントを消したので引用したツイート画像が見れなくなっててなんか申し訳ないです.
よろしくお願いします.

予選

予選Bで3完92位で通過しました.
予選Aで絶望してから精進したんですが,でた問題は閃き系であんまり意味がなかったなぁとかカッコつけて偉そうなツイートをしておきました.

前前日

なんか勢いで実況動画をあげました.

反響があればまたあげます.
反響があるならば次回がある-次回がないならば反響がない

前日

ゲームマーケット

当日開始時間が早いので前泊を用意していただけることになったので東京へ.
ちょうどゲムマをやっていたので11192916とreminさんと合流して試遊めぐりをしていた.
ボドゲも2つ買ってお家へ帰れるか不安な金額になる.

ばんごはん

TABくんとmonkukuiさんと合流して鍋を食べに行った.
僕もTABくんもお店を予約したことがなくてお互いにあわあわしながら新幹線から電話をかけたら相手がちゃんと聞き取ってくれなくて別の名字で予約されたけど無事美味しい鍋が食べれた.

ドワコン

3人でホテルで出ようとしたら僕だけ予約されてたホテルが別だったのでソロ参加になってしまった.
なんかbit演算部分でlong longを扱うときに1LLにし損ねたのを一生気付かずレートが消えて険しい気持ちになってしまった.

当日

起床フェーズ

7時におきた,開店凸を決めるために速攻で会場に向かった.
途中乗るつもりだったバスに乗り損ねて3駅分くらい歩いたけど無事到着した.
開場まで隣のスペースでルービックキューブとかやってた.

コンテストまで

会場に入るとIndeedTシャツを着ていたため社員さんに声をかけてもらったりした.
Tシャツをもらって着替えたりしてたらシンヤカトーが目の前にヌッって現れたりKokiYmgchが後ろからススッって現れたりYazatenが後ろの方からツイッターで僕の実況をし始めたり11192916が服を脱いだり着たりc7c7くんが颯爽と入場してきたり碧黴くんに名刺をもらって無修正すけべイラストはpixivにあると教えてもらったりしていた.
chokudaiさんに謝罪をしたらAtCoderステッカーをもらったので大切にしまっておいた.
fineさんの席をYazatenが暴露したので2秒であいさつしてきた.
隣の席の人が来てtwitterで見たと言われておよおよしながらあいさつしました.

オープニング

かっこいいBGMが流れ始めて社員さんがルール説明とかをし始めた.
パーカーは50位までもらえるって言われて会場内レート順位を確認すると87位だった,悪いイメージしかできなくなる.
パーカー大好きマンだし去年まるで手が届かない領域だったしどうしても獲得したかった.
なんでこんなに欲しがっているのか自分でもそろそろわからなくなっていた.
こどふぇすは学生しか出れないのでラストチャンスなんだよなぁとかぼんやり思ってたらオープニングが終わっていた.
弁当早食いフェスティバルをしました.
叙々苑弁当美味しかったです.
開始30秒前に入って来た人がいた,伝説の男minamiだった.

コンテスト

beta.atcoder.jp

A問題

去年はFA賞は風船が貼られるだけだった記憶があるのでまあいいやと思いながら適当に読む.
適当に場合分けを書いて投げてWAを出す.
あーこれよくないやつだと思いながらちゃんと読んでAC

B問題

難しすぎる,死んだわオイオイ
なんか雑に4引いたりして投げたりしてWAを量産した.

飛ばしてCDを通した後眺めるもわからないので全探索+randで提出しつつ,実行時間に余裕があればループ数を増やして投げ直すを繰り返してたらACした,これが最適戦略や.

C問題

どっかで見たことあるなと思った.
今振り返るとこれだった.
beta.atcoder.jp
どの問題だったかその場では思い出せなかったけど解法はわかっていたのでそのまま書いてAC.

D問題

なんか配点に騙されて誤読してWAを増やしたけど読み直したらあっさりAC.
落ち着きが足りなさすぎる.

E問題

DPっぽいなぁって思ってノートで詰める.
最初はO(n^2)でなんとかしようと思ってたけど明らかに遷移仕切れてないと気づいてO(n^3)を書いてみると数ケースしか通らない.
自分でテストケースを作ると重複して遷移している箇所が見つかったのでループの順番を変えて投げるとAC.
この時点で確か残り20分くらいで順位表を見ると凍結していたが53位までは凍結前にEまで通していて絶望する.

F問題

とりあえずダイクストラ貼って距離求めて和でなんとかしようとしてたが詰めきれず終わった.

コンテスト後

シンヤと11192916と喋ってたらちょくだいさんが来て
「君は出し過ぎ,もっと落ち着け〜〜〜〜」


って言われた.

シンヤに連立方程式は中学生でも解けるってバカにされた.
ブチギレ,許さん.
中学生が必死で解く連立方程式をマシンリソースで殴ってんだよこっちはなぁ!?

解説が始まるので席に戻って凍結解除された順位を見ると67位だった.
僕にしては健闘した方だしEよく通せたなと思うけど悔しすぎて指の爪が手のひらに刺さって流血していた.
こどふぇすパーカー通販始めてください,心の底からお願いします.
とはいえ去年は歯が立たなかった僕がまあまあ解けたので精進の成果はあったのかもなぁ.

解説を真面目に聞いているとちょくだいさんに煽られた.


あとで調べ直すとrandで通したのではなかったけど.

後半の問題もひょっとしたら発想できたなってところがあってEで時間溶かしすぎたのが悔やまれる.

懇親会

ヌメッと始まった.ヌエック.
コネクションビンゴは速攻でビンゴしたが3位だったのでノートみたいなやつをもらった.
寿司食ってかっささんと名字トークをしたりblue_jamさんとルービックキューブしたりtorusさんと闇深い(?)話をしたりヘクトさんとJAG夏の話をしたりけんしょうさんがシール配りをしていたりした.
色々ありすぎて一瞬で時間が過ぎ去ってしまった.
事あるごとにシンヤがパーカーを自慢して来たので次会った時に彼の人生が幕を閉じます.
会場出口で余ったお菓子とか配ってたんだけど何故か1.5Lのコーラが大量においてあって気がつくとカバンの中に入っていてなんで僕は筋トレしながら帰路につくんだ???って感じだった.
T.MくんとnoyくんとYazatenと帰りがまあ似てるし帰るか〜みたいな感じで一緒に帰った.
帰りの新幹線で永久にTwitterの通知がなり続けていて充電が死んだ,ぴょまえら許さん.
アンケートメールが来ていたのでパーカー売ってくれって答えといた,頼むぜ.
それはさておき真面目に答えた.

感想

結構頑張って思い出しながら書いたんだけど喋ってくれたのに名前出せてない人とかごめんなさい.
喋ってくれた人ありがとうございました.
最高のイベントでした.

ただしシンヤは許さない.