読者です 読者をやめる 読者になる 読者になる

YNU.cpc

横浜国立大学競技プログラミング部 ( YNU.cpc )

活動日記 day14

活動内容 :
コンテスト ( 個人戦 )
コンテスト : DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 - DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選 | AtCoder


コメント :
今日はディスカバリーチャンネルコードコンテスト2016の予選があったのでそちらに参加しました。
以下解けた問題の簡単な解説です。

A. C / A * Bが答えです。

B. まず、すべてのカットの長さを求めて、あとは、長い方のカットを順次足し合わせていきましょう。

C. 各Aの要素について、Kの素因数以外の素因数は必要ないので捨てます。
つまり、A[i] = __gcd(A[i],K) としておきます。
こうすると、Kの約数は高々その2*ルートくらいしかないので、Aの中に出現する数の種類が高々そのくらいになります。
そうなればあとは全探索で答えをもとめることができます。
コード:

#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;++i)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
typedef long long ll;
 
int N;
ll K;
vector<ll> A;
 
void compute() {
  rep(i,N) A[i] = __gcd(A[i],K);
  map<ll,int> mp;
  rep(i,N) ++mp[A[i]];
  ll answer = 0;
  for(map<ll,int>::iterator it=mp.begin();it!=mp.end();++it) {
    for(map<ll,int>::iterator it2=mp.begin();it2!=mp.end();++it2) {
      ll v1 = it->first;
      ll v2 = it2->first;
      if( v1 == v2 and ( v1 * v2 ) % K == 0 ) {
	  answer += ( (ll)( it->second - 1 ) * (ll)( it2->second  ) );
      } else if( (v1*v2) % K == 0 ) {
	answer += ( (ll)it->second * (ll)it2->second );
      }
    }
  }
  cout << (answer>>1) << endl;
}
 
int main() {
  cin >> N >> K;
  A.resize(N);
  rep(i,N) cin >> A[i];
  compute();
  return 0;
}

D. 解けていません。

活動中の様子です。
f:id:ynu-cpc:20161105232659j:plain
{<解けない...}
たくさんエナジードリンクを飲んでみたものの解けないようです (真似してはいけません)。
Cを考えていった結果、(a0,b0,..,c0), (a1,b1,..,c1), ...,(ax,bx,...,cx)のうち、ある数列の異なる2つの要素i,jについて、(ai,bi,...,ci) < (aj,bj,...,cj) ただしi < j となるようなものの最長の長さをもとめる問題に帰着してしまったと頭を抱えて倒れこんでしまった○ロイド君の画像です。
ここで(ai,bi,...,ci) < (aj,bj,...,cj)とは、ai < ajかつbi < bjかつ...ci < cjであるような関係のことです。
この問題はICPC2013会津大会G問題の完全上位互換になりますね、、
これはn次元LISを求める問題ですが、どうしたものでしょうか、
2次元の場合は2次元平面上に点を追加して、Lの字(Lがなんのことを言っているのかわかった人はすごい)の内部にある点をすべて消す、ということをやりましたね。
ということはn次元でも同様のことをすれば良いわけですが、、、