足跡-sokuseki-

りかの日進月歩の記録

ACPC2017参加記

会津大学競技プログラミング合宿2017 : ATND に参加してきました。

 

day 0 

 

今年も会津の地に前日入りした。昼過ぎの京都発の新幹線に乗って、会津若松駅に着いたのが18時ごろだったので、やっぱり会津は遠いな〜と1年ぶりに思った。

新幹線の中では主にデレステをしていた。

 

ホテルは駅前だったので移動が楽だった。ホテルではデレステをしていた。

 

なんか合宿前の高揚感とガシャの引きによる高揚感で4時まで眠れず(ア

 

day 1 立命館大学セット

 

 

起床のプロなので7時半に起きた。

 

 

ホテルの無料朝食おいしい。

 

 

ヅに島村卯月の中の人が来るらしくて羨ましい。

 

 

初日なので自己紹介があって、(何かネタに走ろうかとも考えていたけど)普通に名前だけ言った。ウクニキアさん(@ukuku09)が面白かった。

 

コンテストは、立命館がジャッジ側だった。コンテストが始まってから、解説スライドを作りながら自分たちが考えた問題が解かれていくのを眺めてた。

 

コンテスト後にC問題の解説*1をした。

 

原案はAとCと若干B*2。Aはもともとシャトルランを題材にしていて、2回連続で線にたどり着けなかったら終了みたいなのを考えていたけど、シャトルランの定義が難しいということで丸付けになった。CはTwitterをしていたら降ってきたもの。Twitterから作問のインスピレーションを得ることが多い。

 

初日の懇親会は会津の人がたくさんいるテーブルにいたので、会津の人の話を聞いていた。その場にいないのにbeetさん(@beet_aizu)とうしさん(@ei1333)が話題にされていた。ツカサさん(@tsukasa_diary)と隣だったので北海道の話も聞いた。

 

ホテル帰ってかららずくん(@Luzhiled)とめる先輩(@ixmel)と一緒にデレステをした(DEGwerさんもいた)。

 

日付変わる前くらいに解散して明日の準備をしてからデレステをした。

 

 

 

 

 

結局グダグダ4時まで起きてた(ア

 

 

day 2 会津大学セット

 

 

 

朝起きるのが世界一下手なので二度寝して8時半に起きた。それでも起床のプロなので(?)無料朝食と集合時間には間に合った。

 

コンテストに問題を解く側として参加。

 

B問題を担当して、1時間くらいかけてバグらせながらACした。そのあとはDの考察に加わったり問題を読んだりしてたが、とくに貢献はできず。

 

 

解説はDとMが頭良すぎて素晴らしくてやばかった。

解説が終わってから懇親会会場に移動するまでの間にkzyKTさん(@kzyKT_M)とK問題について少し話した。

 

懇親会に移動するときに近くにうしさんがいたので少しお話しした。

 

 

が、話すのが苦手なのですぐにTwitterに逃げた。

 

 

 

2日目の懇親会は右隣にらずくん、左隣にkzyKTさん、正面にめる先輩がいて、途中でみんな揃ってデレステの宝くじとガシャをやり始めたのがハイライト。

 

 

 ホテル帰ってかららずくん(@Luzhiled)とめる先輩(@ixmel)と一緒にデレステをした。

 日付変わる前くらいに解散して明日の準備をしてからデレステをした。

 

3日目は集合が早いので早く寝ようと思っていたら気づいたら3時回ってた(ア

 

day 3 北海道大学セット

 

 早起きするのが世界一苦手なので7時半に起きた。それでも起床のプロなので(?)無料朝食と集合時間には間に合った。

 

 

コンテストに問題を解く側として参加。

 

 

チーム名は何かのアニメに出てくる高校の名前らしいです(よく知らず……

 

B問題担当で、問題を見た瞬間数学で内心*3ハイテンションだった。が、考えてみると難しすぎて、imulanさんと一緒に考察していた。1時間くらいかかったけど、0WAで通せた(実装したのはimulanさんなのでぼくが通したわけではない)のは良かった。

Bを通した段階で チームとしてはABCの3完でDの考察も結構進んでいて、その後特に貢献とかはできなくて、考察や実装を眺めていた。

 

 

おみやげを買って会津若松で電車に乗ろうとしたらうしさんとらずくんに会った。のでデレステをした。(立命館勢が乗り込んだ後に他のACPC参加者も乗ってきたので競プロer率がやばかった)

 

 

郡山で新幹線の乗り換えまで時間があったのでアニメイトに行った。広かった。

 

新幹線に乗ってる間はデレステをした。

 

 

まとめ

 

問題はあまり解けなかったけど、普段合わない競技プログラマーと直接会って交流できたのでよかった。とても楽しかった。

次の合宿は春のRUPCなので、それまでにもっと難しい問題を解けるようになりたい。

 

RCOさんのおかげでおいしい食事を食べられたので良かった。懇親会と牛丼ありがとうございました!

会津大学のみなさんもありがとうございました!

 

 

*1:会津合宿 2017 - 立命館大学情報理工学部プロジェクト団体RiPPro

*2:Bの原案はテセウスの船みたいな感じ

*3:三角形の内接円の中心ではない 

ICPC2017国内予選 参加記

ICPC国内予選に出ました。

参加記を書くまでが国内予選みたいな風習があるっぽいので書きます。

ACM-ICPC 2017 国内予選

 

予選前

 

去年のチームは同学年3人で組んでいたので今年も同学年で組むか〜となって、yebi君(@sigsigma19)としゅもん君(@shumon_84)と組むことに(去年とメンバーは違う)。

1回生たちも出るみたいだから負けたくない!って3人でずっと言ってた(これがフラグとなる)(たぶん)。

6月末に部内コンでチーム練を始めたら、1回生チームたちと互角の戦い(ほんまか?)をしていて、これはやばいとなる。

 

模擬国内は3人で出て、2完でした。B問題を担当してバグらせながら通した。

1回生に負けたのでお通夜だった。悲しいね。

f:id:wk1080id:20170715123629p:plain

 

本当に予選で1回生チームに負けることが現実的になったので、それから予選までの2週間はおびえていた。

部内コン(AOJ-ICPCの問題以外も含まれている)では1回生に負け続け精神的負担が大きかった。今年の1回生はプロが多い。っょぃ。

 

前日は(きっと使わないであろう)ライブラリをいくつか印刷した。あと、超健康児(?)なので日付が変わる前に寝た。

予選当日は普通に授業日だったので直前まで授業を受けていました。

 

 

予選開始

 

とりあえず問題文の印刷が終わるまでyebi君がA問題を解くという話だったので、A問題を任せる(といいつつ印刷に時間がかかっていたので3人で見てた)。O(N^2)の全探索が間に合うのでそれでいこうとなってyebi君が書いてA問題をAC。 そのころに問題文が来たので、B問題を読んだ。yebi君がC、しゅもん君はDを考え始める。B問題は前から見ていくだけでできるでしょ!wとなったのでコーディングを開始。が、実装が終わってサンプルを試すと合わなかったので、印刷クエリを投げて、yebi君に替わってCの実装をしてもらうことに。その間紙デバッグをしていた。Dはなんか二部マッチング臭がすると言われて、誰も書けないのでDは諦めるか〜みたいな話をした。しゅもん君には他の問題に目を通してもらうことにした。

Cの実装が終わってサンプルが合わないようだったので、コーディングを替わってもらった。Bはサンプル出力が合ったのでsubmitしたらWAでつらい気持ちになった。 印刷クエリを投げてyebi君に交代したら、Cが通った。プロ。

自分はというと、サンプルが合ってるのにWAでどこが間違っているかわからなかった(世界一頭が悪い)ので、しゅもん君にB問題をバトンタッチして他の問題を考察することにした。Eの構文解析は全くできる気がしなくてパスして、Fの折りたたむやつは去年の会津合宿の立命セットぽさを感じて(よく考えたらそうでもない)、無理そうな雰囲気を感じ取った。Gはdfsかbfsでできそうな感じがした。Hは幾何だから考えたくもないと思って放置。

一番できそうなGの考察をyebi君としていた。各部屋を1度しか通れないことから、対角線に移動するのは不可能だとわかるので、宝の取り方は左上->左下->右下->右上->左上の順番だけ考えればいいということがわかる。宝の場所に移動するまでに遠回りをすると通ることのできない場所が増えてしまうので、最短距離のルートで通ればいいんじゃないかとなる。しゅもん君の実装が終わり次第yebi君にGを実装してもらうことにしてHを考えてみる。

Hは移動する頂点と移動先の頂点を決めれば、2回の移動で頂点を重ねられることと、5回以上の操作が必要な場合はそこで計算をやめていいので、場合分けすればいけるか?となった(が、幾何ライブラリはあるものの使いこなせないので無理ゲー臭がしたので諦めた)(あと、幾何ライブラリを写すのに時間がかかりすぎる)。

しゅもん君がバグらせながらもB問題を通してくれたので、Gをyebi君に書いてもらう。

その間にEを少し考察したが、できそうにないので、しゅもん君とともに実装を見ていた。最後まで実装できずにコンテストが終了。

  

結果は3完99位でした。

 

f:id:wk1080id:20170715131642p:plain

 

 

なお1回生チームに負けた。先輩ってなんですか。後輩がプロなので先輩を名乗るのをやめたい気持ちでいっぱい。 

 

 

予選後

 

 

部室で菓子パしながらゲームとかで盛り上がってた。

22時くらいに警備員さんにはよ帰れって追い出されて辛かった。 

 

 

そういえば去年の国内予選でもBをバグらせてACできなかったなあとか思い出して悲しい気持ちになった。成長できてないじゃん。実質バグ担当。つらい。

 

次のチーム戦はおそらく会津合宿になるだろうから、それまでにもっと(主にグラフ系の)知識をつけたいなと思った(その前に簡単な問題をバグらせる癖を直したい)。

 

チーム名について

 

ICPC参加登録の直前まで名前がきまっていなくて、どうしようとなったときに、素数うさぎ関連にしないかということになって(ぼくが言い出したわけではない)、Prime Rabbitになった。が、某がごちうさ要素を入れてもいいんじゃないかとか言い始めたので、アルファベット数が575になる「prime rabbits house」を提案してみたらなぜかそれでいくことになった。なんでみんなそんなに素数うさぎが好きなんだろう……。

 

 

ABC008 C コイン

数学ができないので。
期待値問題は苦手です。

C: コイン - AtCoder Beginner Contest 008 | AtCoder

問題概要

 N 枚のコインを無作為に一列に並べる。左端から順に、そのコインよりも右側にある、そのコインに書かれた数  C_i の倍数が書かれたコインをすべてひっくり返す。最終的に表を向いている(偶数回反転した)コインの枚数の期待値を求めよ。

制約
 1 \le N \le 100
 1 \le C_i \le 10^9


満点解法

期待値は、起こりうる確率を足し合わせることで求められる。よって、各コインについて、並べ方によって表を向く確率を計算して、それを足し合わせるという方針。

今見ているコインをCとすると、Cをひっくり返すことに関わるコインはCの約数が書かれているコインのみである。よって、Cの約数が書かれているコインの数に注目する。

Cが表を向いている(偶数回ひっくり返えす)とき、Cの左側にはCの約数が書かれたコインが偶数枚ある。
このことから、Cの約数が書かれたコインの数をSとすると、
Cが表を向いている場合の数は

  • Sが奇数のとき  \frac{S+1}{2} 通り
  • Sが偶数のとき  \frac{S}{2}+1 通り

となる。
よって、Cが表を向いている確率は

  • Sが奇数のとき  \frac{ \frac{S+1}{2} }{S+1} = \frac{1}{2}
  • Sが偶数のとき  \frac{ \frac{S}{2} +1 }{S+1} = \frac{S+2}{2S+2}

であるので、これを各コインについて足し合わせればよい。

計算量は  O(N^2)


Submission #1241223 - AtCoder Beginner Contest 008 | AtCoder


感想

数学は苦手。
今回は解説を見たけど、期待値問題を自力で解けるようになりたい。

もしも日付を約分することができたなら



というツイートが流れてきて、「日付を約分できたら1年はどんな感じになるのかなあ」と思ったのがきっかけ。





ということで、プログラムを書いて計算しました。検証は

  1. 1年間には何種類の日付が存在するのか
  2. 1年間は最短で何日と言えるのか

です。あらかじめ言っておきますが、ソースコードの可読性は低いです。はい。言語はc++です。



Q. 1年間には何種類の日付が存在するのか




結論から言うと、231日です。



解法1

素数を高速に求めるエラトステネスの篩っぽいやり方で計算してみた。

#include<iostream>
using namespace std;

int main(void) {
  int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                              
  int ans=0;
  int date[13][32]={};
  for(int i=1;i<=12;i++){
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(date[i][j])continue;
      ans++;
      for(int k=2;i*k<=12&&j*k<=days[i*k];k++)
        date[i*k][j*k]++;
    }
  }
  cout<<ans<<endl;
}
解法2

月と日の最大公約数が1のペアだけ数えればよくね?みたいになったので、gcdを計算する方法で書いた。
(互いに素の話をはじめに@kyo_math1729 さんがしていたのをすっかり忘れていた)

#include<iostream>
#include<algorithm>
using namespace std;

int main(void) {
  int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                              
  int ans=0;
  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(__gcd(i,j)==1)ans++;
    }
  cout<<ans<<endl;
}

__gcd関数って便利ですね。





Q. 1年間は最短で何日と言えるのか


これまた結論から言うと、4日です。
@asagi_a4ac さんの言う通り、1/1 -> 1/2 (2/4) -> 2/5 (12/30) ->12/31 が最短でした。

(追記:これは日付を巻き戻すことを考慮していません。なので、たとえば、1/31に行くときに1/1 -> 2/2 -> 2/1 -> 1/31 という動きかたはしないものとしています。)

解法1

再帰関数に突っ込むという方法。12/31から戻っていくと、貪欲に計算できます(たぶん)。

#include<iostream>
#include<algorithm>
using namespace std;

int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                                

int date_num(int month,int day){
  int same_month=month/__gcd(month,day);
  int same_day=day/__gcd(month,day);
  if(same_month==1 && same_day==1)return 1;
  if(same_day==1){
    return date_num(same_month-1,days[same_month-1])+1;
  }else{
    return date_num(same_month,same_day-1)+1;
  }
}

int main(void) {
  cout<<date_num(12,31)<<endl;
}
解法2
dp[i][j]:=i月j日にたどり着ける最短日数

として、DP(動的計画法)で求める方法。

#include<iostream>
#include<algorithm>

using namespace std;
#define INF 1e9


int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                                

int main(void) {
  int i,j;
  int dp[13][32];

  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++)
      dp[i][j]=INF; //初期化

  dp[1][1]=1;
  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(days[i]==j){
        if(i==12)break;
        dp[i+1][1]=min(dp[i+1][1],dp[i][j]+1);
        break;
      }
      dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);
      for(int k=2;i*k<=12&&j*k<=days[i*k];k++)
        dp[i*k][j*k]=min(dp[i*k][j*k],dp[i][j]);
    }
  cout<<dp[12][31]<<endl;
}
おまけ

1年のそれぞれの日付が最短何日でたどり着けるのかを調べた。
使ったソースコードはこれ。最後の出力を少し変えただけ。

#include<iostream>
#include<algorithm>

using namespace std;
#define INF 1e9


int days[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};//各月の日数                                

int main(void) {
  int i,j;
  int dp[13][32];

  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++)
      dp[i][j]=INF; //初期化

  dp[1][1]=1;
  for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      if(days[i]==j){
        if(i==12)break;
        dp[i+1][1]=min(dp[i+1][1],dp[i][j]+1);
        break;
      }
      dp[i][j+1]=min(dp[i][j+1],dp[i][j]+1);
      for(int k=2;i*k<=12&&j*k<=days[i*k];k++)
        dp[i*k][j*k]=min(dp[i*k][j*k],dp[i][j]);
    }

 for(int i=1;i<=12;i++)
    for(int j=1;j<=31;j++){
      if(days[i]<j)break;
      cout<<i<<"月"<<j<<"日は"<<dp[i][j]<<"日目"<<endl;
    }
}


で、結果はこうなりました。

1月1日は1日目
1月2日は2日目
1月3日は3日目
1月4日は4日目
1月5日は5日目
1月6日は6日目
1月7日は7日目
1月8日は8日目
1月9日は9日目
1月10日は10日目
1月11日は11日目
1月12日は12日目
1月13日は13日目
1月14日は14日目
1月15日は15日目
1月16日は16日目
1月17日は17日目
1月18日は18日目
1月19日は19日目
1月20日は20日目
1月21日は21日目
1月22日は22日目
1月23日は23日目
1月24日は24日目
1月25日は25日目
1月26日は26日目
1月27日は27日目
1月28日は28日目
1月29日は29日目
1月30日は30日目
1月31日は31日目

2月1日は32日目
2月2日は1日目
2月3日は2日目
2月4日は2日目
2月5日は3日目
2月6日は3日目
2月7日は4日目
2月8日は4日目
2月9日は5日目
2月10日は5日目
2月11日は6日目
2月12日は6日目
2月13日は7日目
2月14日は7日目
2月15日は8日目
2月16日は8日目
2月17日は9日目
2月18日は9日目
2月19日は10日目
2月20日は10日目
2月21日は11日目
2月22日は11日目
2月23日は12日目
2月24日は12日目
2月25日は13日目
2月26日は13日目
2月27日は14日目
2月28日は14日目

3月1日は15日目
3月2日は16日目
3月3日は1日目
3月4日は2日目
3月5日は3日目
3月6日は2日目
3月7日は3日目
3月8日は4日目
3月9日は3日目
3月10日は4日目
3月11日は5日目
3月12日は4日目
3月13日は5日目
3月14日は6日目
3月15日は5日目
3月16日は6日目
3月17日は7日目
3月18日は6日目
3月19日は7日目
3月20日は8日目
3月21日は7日目
3月22日は8日目
3月23日は9日目
3月24日は8日目
3月25日は9日目
3月26日は10日目
3月27日は9日目
3月28日は10日目
3月29日は11日目
3月30日は10日目
3月31日は11日目

4月1日は12日目
4月2日は13日目
4月3日は14日目
4月4日は1日目
4月5日は2日目
4月6日は2日目
4月7日は3日目
4月8日は2日目
4月9日は3日目
4月10日は3日目
4月11日は4日目
4月12日は3日目
4月13日は4日目
4月14日は4日目
4月15日は5日目
4月16日は4日目
4月17日は5日目
4月18日は5日目
4月19日は6日目
4月20日は5日目
4月21日は6日目
4月22日は6日目
4月23日は7日目
4月24日は6日目
4月25日は7日目
4月26日は7日目
4月27日は8日目
4月28日は7日目
4月29日は8日目
4月30日は8日目

5月1日は9日目
5月2日は10日目
5月3日は11日目
5月4日は12日目
5月5日は1日目
5月6日は2日目
5月7日は3日目
5月8日は4日目
5月9日は5日目
5月10日は2日目
5月11日は3日目
5月12日は4日目
5月13日は5日目
5月14日は6日目
5月15日は3日目
5月16日は4日目
5月17日は5日目
5月18日は6日目
5月19日は7日目
5月20日は4日目
5月21日は5日目
5月22日は6日目
5月23日は7日目
5月24日は8日目
5月25日は5日目
5月26日は6日目
5月27日は7日目
5月28日は8日目
5月29日は9日目
5月30日は6日目
5月31日は7日目

6月1日は8日目
6月2日は9日目
6月3日は10日目
6月4日は11日目
6月5日は12日目
6月6日は1日目
6月7日は2日目
6月8日は2日目
6月9日は2日目
6月10日は3日目
6月11日は4日目
6月12日は2日目
6月13日は3日目
6月14日は3日目
6月15日は3日目
6月16日は4日目
6月17日は5日目
6月18日は3日目
6月19日は4日目
6月20日は4日目
6月21日は4日目
6月22日は5日目
6月23日は6日目
6月24日は4日目
6月25日は5日目
6月26日は5日目
6月27日は5日目
6月28日は6日目
6月29日は7日目
6月30日は5日目

7月1日は6日目
7月2日は7日目
7月3日は8日目
7月4日は9日目
7月5日は10日目
7月6日は11日目
7月7日は1日目
7月8日は2日目
7月9日は3日目
7月10日は4日目
7月11日は5日目
7月12日は6日目
7月13日は7日目
7月14日は2日目
7月15日は3日目
7月16日は4日目
7月17日は5日目
7月18日は6日目
7月19日は7日目
7月20日は8日目
7月21日は3日目
7月22日は4日目
7月23日は5日目
7月24日は6日目
7月25日は7日目
7月26日は8日目
7月27日は9日目
7月28日は4日目
7月29日は5日目
7月30日は6日目
7月31日は7日目

8月1日は8日目
8月2日は9日目
8月3日は10日目
8月4日は11日目
8月5日は12日目
8月6日は13日目
8月7日は14日目
8月8日は1日目
8月9日は2日目
8月10日は2日目
8月11日は3日目
8月12日は2日目
8月13日は3日目
8月14日は3日目
8月15日は4日目
8月16日は2日目
8月17日は3日目
8月18日は3日目
8月19日は4日目
8月20日は3日目
8月21日は4日目
8月22日は4日目
8月23日は5日目
8月24日は3日目
8月25日は4日目
8月26日は4日目
8月27日は5日目
8月28日は4日目
8月29日は5日目
8月30日は5日目
8月31日は6日目

9月1日は7日目
9月2日は8日目
9月3日は9日目
9月4日は10日目
9月5日は11日目
9月6日は12日目
9月7日は13日目
9月8日は14日目
9月9日は1日目
9月10日は2日目
9月11日は3日目
9月12日は2日目
9月13日は3日目
9月14日は4日目
9月15日は3日目
9月16日は4日目
9月17日は5日目
9月18日は2日目
9月19日は3日目
9月20日は4日目
9月21日は3日目
9月22日は4日目
9月23日は5日目
9月24日は4日目
9月25日は5日目
9月26日は6日目
9月27日は3日目
9月28日は4日目
9月29日は5日目
9月30日は4日目

10月1日は5日目
10月2日は6日目
10月3日は7日目
10月4日は8日目
10月5日は9日目
10月6日は10日目
10月7日は11日目
10月8日は12日目
10月9日は13日目
10月10日は1日目
10月11日は2日目
10月12日は2日目
10月13日は3日目
10月14日は3日目
10月15日は2日目
10月16日は3日目
10月17日は4日目
10月18日は5日目
10月19日は6日目
10月20日は2日目
10月21日は3日目
10月22日は3日目
10月23日は4日目
10月24日は4日目
10月25日は3日目
10月26日は4日目
10月27日は5日目
10月28日は6日目
10月29日は7日目
10月30日は3日目
10月31日は4日目

11月1日は5日目
11月2日は6日目
11月3日は7日目
11月4日は8日目
11月5日は9日目
11月6日は10日目
11月7日は11日目
11月8日は12日目
11月9日は13日目
11月10日は14日目
11月11日は1日目
11月12日は2日目
11月13日は3日目
11月14日は4日目
11月15日は5日目
11月16日は6日目
11月17日は7日目
11月18日は8日目
11月19日は9日目
11月20日は10日目
11月21日は11日目
11月22日は2日目
11月23日は3日目
11月24日は4日目
11月25日は5日目
11月26日は6日目
11月27日は7日目
11月28日は8日目
11月29日は9日目
11月30日は10日目

12月1日は11日目
12月2日は8日目
12月3日は9日目
12月4日は9日目
12月5日は10日目
12月6日は10日目
12月7日は11日目
12月8日は11日目
12月9日は12日目
12月10日は12日目
12月11日は13日目
12月12日は1日目
12月13日は2日目
12月14日は2日目
12月15日は2日目
12月16日は2日目
12月17日は3日目
12月18日は2日目
12月19日は3日目
12月20日は3日目
12月21日は3日目
12月22日は4日目
12月23日は5日目
12月24日は2日目
12月25日は3日目
12月26日は3日目
12月27日は3日目
12月28日は3日目
12月29日は4日目
12月30日は3日目
12月31日は4日目

面白いですね。ちなみに2/29は2/28から遷移するので15日目のはずです。

感想

こういうクソくだらないことを考えるのが結構楽しい。

RUPC2017参加記

3/22から3/24に立命館大学で行われたRUPC2017に参加した。

立命館大学競技プログラミング合宿2017 : ATND

 

Day1 : 立命館大学&大阪大学セット

 

コンテスト前 

会場の設営のために10時半くらいにBKCに着いたけど、Twitterではすでに到着している参加者がいてびっくりした。

会場であるBKCで卒業式をしていて、人がとても多かった(怖い)。

あと、自己紹介フェーズがなくなってしまって悲しかった(運営側として申し訳ない気持ちもあります……)。

 

コンテスト

出題側だったので、コンテスト中はジャッジを眺めながら風船運びをしたり、B問題の解説スライドを作ったりしていた。 

コンテストの問題は、B問題とK問題の原案を考えて、B問題の解説をした。 

 

コンテスト後のRCOの宣伝コーナーが面白かった。競プロerに優しい会社。 

 

懇親会 

学内のユニオンフードコートというところで立食パーティーをした。

Twitterでよく見るうくさん(@ukuku09)やらてさん(@LatteMalta)、夏の会津合宿でチームを組んだ そうめんさん(@somennagasi)たちとお話しした。とても楽しかったです!!!!

 

懇親会後

大学の宿泊施設に移動して、チェックイン。

 

私の就寝時間までは時間が結構あったのと、RUPC前の1~2週間くらい前から全然競プロできてなくて鈍ってそうだったので、バチャコンをすることに。  

 

 こんな時間にもかかわらず5人も参加してもらえて嬉しかった。

 

 そのあとはTwitterでタイムラインを監視していた。

 

 もちろんベッドで寝ました。

 

 

Day2 : 会津大学セット

 

コンテスト前

 

目覚ましをかける前に寝落ちしてしまって、起きるのがギリギリになって焦った。

湖西線トラップ*1 にかかってしまった人がいて、開催時刻が30分遅くなったので、お菓子を食べてた。おいしい。

 

コンテスト

 

私はB問題を担当することになったので、冷雨さん(@_ybrliiu)にA問題を実装してもらっている間に考察していた。参加者を1人決め打ちすると、その人が勝者になる回数と引き分けになる回数はupper_boundやlower_boundを使うとO(logN)で求められるので全体でO(NlogN)になっていけそうとわかる。A問題がバグっている間にコーディングを代わってもらってB問題をAC。

そのあとA問題を見て、場合分けでいけると思ったので、方針を伝えてから、コンブさん(@konbu1610)と一緒にC問題を考える。因数定理をつかって項を一つずつ見つけていけばいいという方針が立って、とりあえず構文解析の実装に移る。構文解析だけでもだいぶバグらせていて辛かった。

ここらで、A問題のバグが取れないので方針を変えて、tをループで回すことにした。冷雨さんが実装してA問題がAC。その後私は構文解析のところを書き終えてから、多項式の割り算を時間をかけながら実装してACした。

この段階で残りがあと1時間半くらいだったので、E問題をコンブさんと考えていた。各辺の労力/長さを計算して、労力/長さが大きい順に木を構成していけばいいんじゃないかと思って、コンブさんに実装してもらっていたけど、嘘解法だとわかって、どうしよう……となったところでコンテスト終了。

 

悲しかったけど、「展開する前のそれぞれの一次式の元の定数項は相異なることが保証される」を理解していなかったのが悪かった。うん。

 

 

懇親会

南草津駅前の魚民に行った。RUPCのほぼすべての参加者が2日目の懇親会に来ていた。

@kenkoooo さんと同じ机だったので、RCOの話を聞いていた。あとKaggleの話も面白かったです。

 

懇親会後

 先輩たちが泊まっている部屋に遊びに行った。そして例によって例のごとくコンテスト。

コンテスト後は解法を教えてもらったり、蟻本やTwitterの話をしたりと、だいぶ長い間居座っていた。いろいろな話ができたので嬉しかったけど、寝る時間を削ってしまって申し訳なかったなあと思ってます。

 

 

Day3 : 北海道大学セット

コンテスト前

目覚ましをつけるとちゃんと起きられるタイプなので、 7時半くらいには起きた。それから荷物をまとめてチェックアウトして、ゆっくり会場に向かう。

ドリンクがなくなっていて、お菓子も少なかったので、RiPProの先輩たちと学内コンビニに買い出しに行った。

 

コンテスト

 

 

A問題を担当することになったけど、「並び替えて」という言葉を読み飛ばして(誤読して) これ本当にA問題か?と思いながら考えていた。実は前日のバチャコンで文字列から削除する系の問題*2を見ていたために、頭の中で(これもしかしてDPする感じか……?)と思って、B問題を考えていたちゃっくさん(@chakku_000)と代わってもらうことにした。その後、kawabysさん(@s1230151)がA問題、ちゃっくさんがC問題を考えることになって、ちゃっくさんがC問題をAC。

B問題は現在8位のユニットとユニット1の差を見て、いくつ増やせばいいかを求めるのかなと思って実装したら、ユニット1の値を変えると他のユニットの合計得点が変わってしまうと気づいて、誤解法だとわかる。その後私がB問題を考え直している間に、A問題がAC。B問題は、値を変更する数をループで回して、その後に合計得点を計算し、ユニット1が8位以上なら答えとするという方法を思いついたので、それを実装した。

実装したはいいけど、バグが取れなくて、kawabysさんと一緒にデバッグしていた。その間ちゃっくさんはE問題を考察。残り30分くらいでB問題をACした。

そしてEが解けないままコンテストが終わる。

A問題を誤読してB問題をひたすらバグらせる害悪でした。

 

 

コンテスト後

解説が(アニメネタとかがあって)とても面白かった。 

解説後は立命館の成績返却とガイダンスに行かなければならなかったので、すぐに会場を去った。もう少しお話ししていたかった。

 

全体を通して

 

 Twitterで見かける人や初めて知った人などたくさんの人と交流できてよかった!

次のオンサイトは会津合宿かな?(オンサイトは楽しいのでHUPCやQUPCやNJPCなどのオンサイトがあればぜひ行きたいです!!)

 

 

 RCOさん、ありがとうございました!!!!!!!!!!

 

 

 

余談

Day1のK問題について。 

K問題原案ですが、大学の定期考査期間中(1月末)に、テスト勉強したくない気持ちが強くなってきて、来期は期末考査がなくレポートだけで成績が決まる講義をたくさん受けたい!!!!と思っていたら降ってきました。やったね。

なお、原案は

  • レポートの数
  • 友達の数
  • AORイカちゃんが自力でレポートを仕上げる最低回数
  • AORイカちゃんと友達のそれぞれのレポートの点数

が与えられて、合計得点の最大値を求める問題(難易度はBくらい)だったのですが、先輩による改変を経て化けました。びっくりしました。

 

*1:京都大阪方面から滋賀に向かうJRには琵琶湖線湖西線があり、南草津に来るには琵琶湖線に乗らないといけないのですが、京都や滋賀に住んでいる人でも間違えることがあります

f:id:wk1080id:20170325010402j:plain

*2:D: ヘイホー君と削除 - CODE FESTIVAL 2015 あさぷろ Easy | AtCoder

gitあれこれ

作問につかった。忘れそうなのでメモ。

githubのレポジトリの「Clone or download」からurlを取得
f:id:wk1080id:20170314123412p:plain

作りたい場所に移動してから「git clone 取得したurl」を入力

$ git clone https://github.com/~

既存の(誰かの)フォルダをコピーして、自分の名前に変える。

フォルダに入って、main.ccを編集して自分の回答にする。

テストしてみる。

$ rime test

OKがでたら良い。

「git add フォルダ名」で自分のフォルダを追加して、「git commit -m "コメント"」でgitにcommitする。

$ git add rika
$ git commit -m "rikaの回答を追加"

終わり。

ABC 006 C スフィンクスのなぞなぞ

数式が出てきたのでメモ。

C: スフィンクスのなぞなぞ - AtCoder Beginner Contest 006 | AtCoder

問題概要

大人、老人、赤ちゃんの足の数をそれぞれ2本、3本、4本とする。
街の人数Nと足の数Mが与えられるので大人、老人、赤ちゃんの人数の組み合わせを1つ答えよ。存在しない場合はすべて-1で答えよ。

制約
 1 \le N \le 10^5
 1 \le M \le 10^5

部分点あるけどここでは割愛

解法

連立方程式を解くだけ。

大人の人数をa、老人の人数をe、赤ちゃんの人数をbとする。
ただし、人数なのでそれぞれ非負整数である。

このとき、街の人口については

 a + e + b = N  …(1)

足の本数について

 2a + 3e + 4b = M  …(2)

という2つの方程式を立てることができる。

よって連立させて式を変形させることで、変数を1つに減らすことができる*1

まず(1)式をeについての式に変形する

 e = N - a - b  …(3)

そして(3)式を(2)式に代入して、aについて解く

 2a + 3( N - a - b ) + 4b = M

 3N - a + b = M

 a = b + 3N - M  …(4)

また、(4)式を(1)式に代入して、eについて解くと

 ( b + 3N - M ) + e + b = N

 2b + e + 2N - M = 0

 e = M - 2N - 2b  …(5)


以上のように、(1)(2)の連立方程式から(4)(5)の式が得られた。(4)(5)の2式は人口についてと足の本数についての制約を満たすので、あとは3つの変数a、e、bが非負整数であれば、答えとなる。

変数bが決まればaとeは確定するので、bがとりうる値(0からNまで)をループで回してやれば、全通り試せる。
よって、計算量は  O(N)


Submission #1152289 - AtCoder Beginner Contest 006 | AtCoder

感想

数学は楽しい(これは真理)。

実は私のソースコードだと  a = e = 0 の場合も答えとなってしまう(サンプル1だと「 0 3 0 」を出力する)けど、実際問題、街に大人と老人がいなくて赤ちゃんだけ存在するというのはおかしいなあ大丈夫かなあと思いながらsubmitしたらACしてしまったので拍子抜けした。

*1:連立方程式は連立した式の数だけ変数を減らすことができる。変数が3つで式が2つなので、変数は2つ減らせる