足跡-sokuseki-

りかの日進月歩の記録

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つ減らせる

ABC017 C ハイスコア

自力で満点解法思いついたの嬉しかったのでその記念。

C: ハイスコア - AtCoder Beginner Contest 017 | AtCoder


問題概要


 N 個の遺跡があり、遺跡を探索すると宝石と得点が得られる。
 i 番目の遺跡を探索したときに、得点  s_i 点を獲得し、 M 種類ある宝石のうち  l_i 番目から  r_i 番目までの宝石を得られる。
すべての種類の宝石を1つ以上獲得すると魔王が復活してしまうので、魔王が復活しないように遺跡を探索したときの得点の合計の最大値を求める。


制約

 1 \le N \le 10^5
 1 \le M \le 10^5
 1 \le l_i \le r_i \le M
 1 \le s_i \le 5000

部分点

30点……  N \le 8 ,  M \le 8 を満たすテストケース
100点……  N \le 5000 ,  M \le 5000 を満たすテストケース
101点……すべてのテストケース


TLE解法


100点解法*1
魔王が復活しないとき、少なくともどれか1つの宝石は獲得していない。獲得してはいけない宝石を1つ決めると、各遺跡について、その宝石を獲得できるかどうかで、その遺跡で得点を獲得できるかがわかる(最大の得点について考えているので、獲得してはいけない宝石をその遺跡で取ることができないならば、その遺跡を探索して得点を得た方がよい)。
つまり、獲得してはいけない宝石を1つ決めたとき、そのときに取りうる最大の得点は一意に決まる。

獲得してはいけない宝石を順番に試すのに  O(M) 。獲得してはいけない宝石を決めた後、各遺跡でその宝石を獲得できるかを調べるのに  O(N) かかる。よって、全体の計算量は  O(NM)


Submission #948966 - AtCoder Beginner Contest 017 | AtCoder


満点解法


(私が解法を考えていたときの脳内をだいぶ忠実に再現してみる)

「すべての宝石を獲得してはいけない」というのが最大の制約なので、獲得してはいけない宝石を一つ定めるという方針はそのままでよさそう。……TLE解法のとおり、獲得してはいけない宝石を決めたときに、その宝石を獲得してしまう遺跡の得点は得られない。……「得られない」ということは、「獲得してはいけない宝石を決めたときに、各遺跡で何点得られないか」というふうに全体からの引き算で考えることができる。もちろん、得られない点数が一番小さくなる宝石を、獲得してはいけない宝石として選べば良い。


試しに、サンプル1を表に書いてみる。

f:id:wk1080id:20170308022800p:plain

はじめに各遺跡について、獲得してはいけない宝石の欄にその遺跡で得られる得点をマイナス表記する。
その後、獲得してはいけない宝石を1つ決めると、その宝石の列さえ見れば最終的な得点が求まることがわかる。
そこまでわかって、いもす法*2を使えばこの表を圧縮して、計算量も落とすことができる!と気付いた。やったね!たえちゃ(ry



いもす法を使うことで、獲得してはいけない宝石を1つ決めると、そのときの最大の得点は  O(1) で求まる。
よって計算量は、いもす法の前処理(記録+シミュレート)に  O(N+M) 、各宝石を獲得しない場合について計算するのに  O(M) かかるので、全体で  O(max(N,M))



Submission #1150134 - AtCoder Beginner Contest 017 | AtCoder

ソースコードでは、さっきの表と違い、各遺跡で取ることができない点数を負数ではなく正数で計算している(ので最後に総得点から引き算している)。あと、宝石のindexに注意する。

感想


得点が0点の状態から考えて何点獲得できるか、ではなく、得点がMAXのときから考えて何点獲得できないか、に思考をシフトさせるのが面白かった。
例示は理解の試金石*3だ!!!!と再確認させられた。サンプル試すの大事。


↑悲しい……






あと、いもす法は好きです(なら間違えるな

*1:30点解法は考えてないので知らない。たぶんすべての遺跡について、探索するかしないかを全探するんじゃないかな。……と思ったけど、制約が8だしnext_permutationを使ってシミュレートするのか。

*2:いもす法知らない人はこちらを参照してください->いもす法 - いもす研 (imos laboratory)

*3:数学ガールの主人公「僕」がよく言う台詞