https://yukicoder.me/problems/no/698

解法

  • bitDPを使うのが一般的な解法ですが、計算量が増えるものの、next_partial_permutationを使うこともできます。
  • 標準関数ではありませんが、next_permutation(v.begin(), v.end())する直前にreverse(v.begin()+middle, v.end())するだけなので、(next_combinationと違って)インラインで組み込むのは簡単です。
  • v.begin()からv.begin()+middleまでを(middle P sizeの)部分順列として使います。
  • ただし、ループが回るたびに、v.begin()+middleからv.end()まではソートされていることが保証されています。この性質を利用することで、vからsize-middle個選んでから残りのmiddle個を総当たりしたのと同じことになるのです。
  • ループ回数は14P7 = 17297280回です。

解答例

チームを作ろう2

https://abc096.contest.atcoder.jp/tasks/abc096_d

出力

  • AGC001以降のAtCoderでは、区切りは空白区切り改行区切りのどちらでも構いません(trailing spaceも可)。
  • よってputs arr*' 'puts arr、ひいてはp *arrでokです。以下では後者を使います。

解法

  • 5で割ってあまりが1になる整数の集合から5個選んだ合計は5で割り切れます。
  • 素数を列挙していき、1の位が1であるものをN個拾えば良いです。
    • 実際には1の位は(統一していれば)1,3,7,9のいずれも大丈夫です。以下の答案では9を採用しています。
    • 64bytes
1
require'prime';p *Prime.each(1499).select{|e|e%5>3}[0,gets.to_i]
  • 1の位がX(奇数、以下の答案では3)である整数を全て列挙し、素数をN個拾うようにすると以下のようになります。
  • 62bytes
1
require'prime';p *3.step(1499,5).select(&:prime?)[0,gets.to_i]

フェルマーテスト

  • require'prime'をカットすることで字数の節約にはなりますが、Integer#prime?は使えなくなるので、別の素数判定が必要になります。そこで、フェルマーテストを用います。
  • [1]に載っている式、2**i%i==2を使います。なおこの素数判定の場合stepの初期値を1にすることはできなくなるので注意してください(3,7,9は可)。
  • 51bytes
1
p *3.step(1499,5).select{|i|2**i%i==2}[0,gets.to_i]

redo

  • [2]では、ループカウンタをインクリメントしないよう、条件を満たさない場合はredoを使っています。これはPerlだけでなくRubyでも有用なテクニックです。
  • https://abc096.contest.atcoder.jp/submissions/2470406 (最終答案)
  • 46bytes
1
i=3;gets.to_i.times{i+=5;2**i%i==2?(p i):redo}

discussion

  • フェルマーテストやredoの実践例を挙げることができました。どちらもゴルフには有用であると思われます。

reference

  1. cojnaさん https://abc096.contest.atcoder.jp/submissions/2465874
  2. %20さん https://abc096.contest.atcoder.jp/submissions/2467541

https://bcu30-2018.contest.atcoder.jp/tasks/bcu30_2018_a

概要

(現状問題公開されてないですからね…)

1個ずつ数字が書かれた球がA個ある。これを1個ずつ数字が書かれたB個の球にしたい。ただし変換は以下の2種類。

  • 数xと数yが書かれた2個の球を数x * yが書かれた1個の球にする
  • 数xが書かれた1個の球を、(x%y==0となるような適当なyを選んで)数yと数x / yが書かれた2個の球にする

この条件で最終状態を達成できるか?AおよびBは9以下、書かれている数はそれぞれ100以下。

解法

  • 探索…は必要ないです。乗算と余りのない除算のみで構成されるということは、素因数です。素因数の組が等しい…つまり、状態Aの数の積と状態Bの数の積が等しければYesです。
  • 多分、制約は、積がint64に収まるようにってことなんだと思う。

感想

  • 気づきづらい。
  • 本当は「積が等しいかどうか判定せよ」という問題だったけど、がち勢が多かったので難しくしたらしい。
  • おかげで体感300点ぐらいでした…つらいよぅorz

概要

  • N(=3000)枚の寿司ネタ(a-zの26種類)を連続して流す(文字列Sとする)。
  • その中からM(=7)枚の部分列がQ(=30000)個問い合わせられる。ただし場合により部分列は連続していないことがある。
  • そのそれぞれに対し、S上でのインデックスを答える。

決定的アルゴリズム

この問題、D=1とすれば、部分列は連続であることが保証されます。つまり、決定的アルゴリズムを使うことができます。

  • N枚のうちで連続したM枚についてすべて異なるようにSを生成します。
    • 完全に決定的にするには https://en.wikipedia.org/wiki/De_Bruijn_sequence とか使うんですが、発展のために少しでもエントロピーを上げたいので、この部分は乱択を使って良いと思います。
  • すべて異なることがわかっているのだから、M枚の部分文字列を単にSから探すだけで終わりです。
  • Sの生成さえできれば、1ケースに付き30000点、 合計300000点を確実に獲得できます。

  • Rubyの事実上初版 https://rco-contest-2018-final-open.contest.atcoder.jp/submissions/2177816

発展

  • この状態であれば、0..Nのそれぞれ(j)に対し、qがS[j,M*3]中にこの順番で入っている数(ただしSの先頭に入っているほど重みを大きくする)が最大となるjをインデックスとして答える実装にすることで、D=2.5程度までは安定してインデックスを求めることができます。
    • 「*3」は、元となる部分文字列の長さはM*3以下であることを期待しています。
  • この「重み」が評価関数の肝になると思うのですが、調整の余地が残っている気がします。

  • C++の(コンテスト後)最終版(381792点) https://rco-contest-2018-final-open.contest.atcoder.jp/submissions/2179945

  • なお、コンテスト中は元となる部分文字列の長さがMであり、qの長さがM未満になりうると誤読していました、D=1.5にしかできなかったので324730点どまりでした。無念。

記事としての結論

  • 順位表で、ある点数を取っている人が沢山いる場合は決定的アルゴリズムを疑うのは有用ではないかと思います。

補足

  • Sの一例は次のとおりです:
1
kzsbqmuxtqwazgonugucjaouqsihsmgjpvdiwscfaewltvsyolgoenjcmlylyzhqlhgaypshugqlrqfxjigsliujfconzsyrnctoeztichmtznzxfhfkcpytpenkyqxmwxeaihahytbkbqkzxplhdtnzbsnpwhdpzjykrgwoxihvkiqrgmruztplaiuqecvbrvlbkwsbylxgxytyhsyiedtfvkjiylnjmcmhvtlkrmqbafrhngsqrvfbkadbkjshyhbagjoyhqmwipzegzqjkpxoquezkdplxombjqkdtbgnghkdaregkmrxelhpfbfoewbnfewmqvyivwkhfahoryxqvqnoguwpcldzcqlbpfruijrenfofeajcnrtcnqlzhbwdxwglmbkhdfhdyhfinxkwksypafghuoilqofnmbiavcqtjszdtowlqsdienoymvlrhczlysmlokhbvluaelotziotdtcwnvsigjnfjfywkeyalcmxgwyojkjrigvlnoqehmgopgvhntqxvnmxobebiwbzomjracdoerdndvbdygoyeayujwhtoiouxhmdbqusqbmqwnucgbzligimgnaswqbcdjchomvihdwmksltueulypyjsrnjeyoipdfxtveurkuwxatwmawmvrahsgexunjrdzemesmkfxmdzjvqxijdqoabvahbzeklborztczqlicyzbpemqinofcfuvaznakgxaevhcmqgmnescpxghixypxsxcxcqsqpkldvycwkxhkqcwqlqxnpoazsohnoucsztqdizbntfdeteiximtuymuzodlquigwhzoqjezyqahpkifvbyhkibmhslzdwybpojuegpyopwcdigpepmgpgdgdlumhrnfscleimrhriyjxfypdawcybayotfguipljmjvzxixpxugnlzvqemwluzwskegvpmpvrftyrfegxwetstcouotmofsakluqdmliroqiaodhrbvxnqgwrqntenstlhykhjalzlwuqvcmwawfyqojhpymlgycsxyhgqxjvesdbifgxitdikicrtnuzywysuvxrsidvtwisowtvltfyvmeqdpnzhklcvxmygjzmtpfqzezwkgiwfdctpchqfljqenqbxhxuivldilsldfesvtebuxcpqsharzikqnvxudumxqlknkpblcicqjimafnaqbocjmguzcliduealstwhnyqcbypexcnyjndbwgvefjwlbzilcqejkylrwqmbzsxolbvuihmkvyjlwkitvthxsmozyektmnhxifxziytweudfnhipwstdzwqcekmuswolxrvwagpfhlgwqhqsgocwioykxpnlkpcjtzdfwfxnfrdjnpkmfkninbsmpdblqveasiejnqxthdioxfpruxabcjftnkgdphravwvzlcgtonqcftlckmvmxvhojwuzpetwyhzvcrgclxembtiksgkxrnwhpamnrcztbftknzijgsrxwnfxrzhacvfakjapavrbrmdacqhurnqozroebwnqjgmcnpdwkrhzwbrusawknwyglczmewansanujgkljlntcbxeqtuczwnsvawpgkzkzqnruqbnuoepfxylqmqfodorsrlyuhoxtgxqizpzokjqskcapuoctghnhsprjgyayidqelwfaufxvpcqgtbvgltgbrbmtawovsdvsnmjymqdtkjeptmhmcjenmwktbnvmqnjyuceclnpeqktpdhclyvwbszlqlvzbahuktlwyzphaoaftshmvelbhvbqyfatbjmknybdnpjpxtovwodvxzdapgwbekptxputuqwsfrcqyauvegdfcjsjudqnqiqsfzeoevlkdczpkwejcfekodqdcpzqsjfhgkovcjzhtnyosceiknalxljzpcsnqnpvigrmblkflihbrireolvlpmyunynuemvfkmyhryqvwcqrbnryjydnsusbesncslszxjpirhqxbfnsxlwsrbxurvjystorpmeiyxcmgynknfdlzqgatiyhmyfksjbcokchpbgxgjkiafsmzepbfmjzyntzcalnfufqlgqkwynmizavocyqijpuevsjdlvbwmycvepjzvhxznxlyhaeypicgiyfnxwasyukgmiwikmgtkvgwevafmkpnphuvczrjcgqewivjugpikduiofvaeshowxzcuxecemurqieiflobzxbxswciepxwfmhkevjxtngfxgckfvtztjyznqkyiymeauyvkdgspmzgxmxuoztrkpudrdowrysdcozcpbydsygxroclwhldqrzswnldbgjybwhrseljwmclgzabgpmthltqocahrzrnowgpcrzkazcyhxqdknlapzhjyhjsnejbnoeabjvdcxjkgcniokyxyjujkfmtgrxdvwpnbxficmzrbspvozlsmdoxdefbhgmfumuakdxdivrvzjfdngjqxutjeibzahvmktqjvryplivblnetnvukxjmvtgzidxhokfhicoaqvhpmwpoefwgqsznyczfetgnfqtwornmnslycqodunanvrzvtufmxdqubnqfbyzrwcmyteukdskmjhsijkhzqopckiobdabsyzujbxjnymiaroiwafpwbpihqnhlmxsopoxbqrfxhavgqurfpkgskntoavqdbfhqkfyspwmihrtesoemfnbwswyqutsaujcdkepdukawaigywzveizimplsnvalkgrgeuznvbxgeruhwoijvmcazucrvofdmvuqcsyejrmeyclsgafckhcdtpvlvymcvswgfzkphxbmgcdxzlxzqmdwocowclvwrspkurzjsbnxfxiatubjfriasfyxwdejpmsfvmfptijwykizxoubgetmbsogpwqwkqlsfxklopxpwjwrpizgqonplrpfpmqagnmcgcoqgemovxtxrkdnwqugvmyqetbiqchfcmpsunwjnuplmzwjplfj

まず、最下位が0,6,7の場合はNoです。後述する状態1/0への移行は十の位以降で発生する必要があります。in06がこのケースです。

それ以外の場合。 下の桁から順番に見ていきます。3つの状態があるので適切に管理します。

  • 状態2(私のソースコードに生えた数字ですが、まあ「2つのラッキーナンバーが影響している」とでも考えて下さい)のとき、2,3,4,0,6,7を受け付けます。
    • 2,3,4の場合は、繰り上がりがあるので、上の桁から1を引きます。
      • すでに最上位の場合はNoです。
      • (最上位でないが上位桁が0の場合、次の桁で弾かれるため、無理やり引いても通ります。)
    • 6,7の場合は、状態1に移行します。
    • 0の場合は、状態0に移行します。
  • 状態1のとき、0,6,7を受け付けます。
    • 0の場合は、状態0に移行します。
  • 状態0のとき、0のみを受け付けます。
    • ラッキーナンバーが影響し得ないということは、すべての桁が0になっている以外にないです。
    • (間に合わなかった)チャレンジでは、612だと、下位の12で6+6と完結しているのに、新たな600が出てきているので、十の位が不合理となるのです。

https://yukicoder.me/submissions/238472

https://yukicoder.me/problems/no/649

190104

dequeだとTLEになるようになったようです。treeを使うしかないですね…


配列の先頭要素からの削除はO(配列長)ですが、dequeを使うと先頭からの削除は速くなります。 中央からの削除はやはり遅いですが、定数倍の高速化が望めるので、時間制限の設定によっては間に合う可能性があります。

なお、マスと駒と色塗りで、範囲管理をvectorでなくdequeでやると通ってしまいます(setでやるのが最善ではあります)。 - http://cielavenir.github.io/blog/2015/10/29/many-ameba/

https://yukicoder.me/problems/no/648

基本的にはむこさんの解説のとおり、(sqrt(8*n+1)-1)/2を出力すれば良いですが、実装上の別解を。

  1. Integer sqrtの利用
  2. sqrtlの利用
    • long doubleの仮数部が64bitであることを思い出せば、sqrtlを使えば解けることは想像に固くありません。1
    • C https://yukicoder.me/submissions/206063
    • Python (ctypes) https://yukicoder.me/submissions/207816
      • intをマーシャリングするときにfloatを経由されるといけないので、sscanfを用いて自力でマーシャリングする必要があります

  1. あれ、topcoder初出場で撃沈したのは誰だ^^; (SRM 635 Div2 Medやらyukicoder No.413やら)

https://yukicoder.me/problems/no/580

  • 区間スケジューリング問題の、スロットが複数あるバージョンである。
  • 基本的な解き方は同じだが、popするスロットは、「部屋iの(出)時刻がdata[i]の入時刻より早い中で最大」のものである。
    • このスロットを検索するには、multisetを2分探索する以上に効率のよい方法はなさそうである。
      • 勿論普通の区間スケジューリングではこの集合は1個しか無いため定数時間である。
    • 私は最初、最小のものがdata[i]の入時刻より早ければpopする実装にして盛大に間違いました…
  • スロットを線形探索しないため、計算量をnからlognに落とすことができ、合わせてO(m(logm+logn))となる(実際にはn<mだと思われるのでO(mlogm))。

  • https://yukicoder.me/submissions/211209 (現状の最短時間とのこと)

  • n<=10000, m<=100000なるHardバージョンを作ろうと思いましたが必要ない気もするのでやめておきます。。

http://arc082.contest.atcoder.jp/tasks/arc082_c

初版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<long double> P;

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};
bool intersectSP(const L &s, const P &p) {
  return abs(s[0]-p)+abs(s[1]-p)-abs(s[1]-s[0]) < EPS; // triangle inequality
}

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<L>se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      L l(v[i],v[j]);
      int n=0;
      for(int k=0;k<N;k++)if(k!=i&&k!=j&&intersectSP(l,v[k]))n++;
      r=(r-pow_binary_mod(2,n,M))%M;
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

点が載っている判定を直線へ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<double> P;

double cross(const P& a, const P& b) {
  return imag(conj(a)*b);
}

struct L : public vector<P> {
  L(const P &a, const P &b) {
    push_back(a); push_back(b);
  }
};

bool intersectLP(const L &l, const P &p) {
  return abs(cross(l[1]-p, l[0]-p)) < EPS;
}

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<pair<int,int> >se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      if(se.find({i,j})!=se.end())continue;
      L l(v[i],v[j]);
      vector<int>x={i,j};
      for(int k=0;k<N;k++)if(k!=i&&k!=j&&intersectLP(l,v[k]))x.push_back(k);
      for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
          int n=b-a-1;
          r=(r-pow_binary_mod(2,n,M))%M;
          se.emplace(x[a],x[b]);
      }
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

インライン化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <complex>
#include <vector>
#include <set>
#include <cstdio>
using namespace std;

const double EPS = 1e-12;
typedef complex<double> P;

long long pow_binary_mod(long long x,long long y,long long M){
  long long z=1;
  for(;y;y>>=1){
      if((y&1)!=0)z=z*x%M;
      x=x*x%M;
  }
  return z;
}

int main(){
  int M=998244353;
  int N,x,y;
  scanf("%d",&N);
  vector<P>v(N);
  int r=pow_binary_mod(2,N,M);
  set<pair<int,int>>se;
  for(int i=0;i<N;i++)scanf("%d%d",&x,&y),v[i]={(double)x,(double)y};
  for(int i=0;i<N;i++)for(int j=i+1;j<N;j++){
      if(se.find({i,j})!=se.end())continue;
      vector<int>x={i,j};
      for(int k=j+1;k<N;k++)if(abs(imag(conj(v[j]-v[k])*(v[i]-v[k])))<1e-12)x.push_back(k);
      for(int a=0;a<x.size();a++)for(int b=a+1;b<x.size();b++){
          r=(r-pow_binary_mod(2,b+~a,M))%M;
          se.emplace(x[a],x[b]);
      }
  }
  printf("%d\n",((r-N-1)%M+M)%M);
}

Ruby

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/ruby
M=998244353
N=gets.to_i
v=$<.map{|e|Complex(*e.split.map(&:to_i))}
h={}
r=2**N%M-N-1
N.times{|i|(i+1...N).map{|j|
  h[x=[i,j]]||
  (j+1...N).map{|k|((v[j]-v[k]).conj*(v[i]-v[k])).imag.abs<1e-9&&x<<k}&&
  (l=x.size).times{|a|(a+1...l).map{|b|
      r=(r-2**(b+~a))%M
      h[[x[a],x[b]]]=1
  }}
}}
p r

最終版

1
2
3
4
5
6
7
8
9
10
11
12
13
#!/usr/bin/ruby
M=998244353
N=gets.to_i
v=$<.map{|e|Complex(*e.split.map(&:to_i))}
h={}
r=2**N+~N
[*0...N].combination(2){|i,j|
  h[x=[i,j]]||(
  (j+1...N).map{|k|((v[j]-v[k]).conj*(v[i]-v[k])).imag.abs<1e-9&&x<<k};
  r-=2**(l=x.size)+~l;
  x.combination(2){|a,b|h[[a,b]]=1})
}
p r