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次元でも同様のことをすれば良いわけですが、、、

活動日記 day12

活動内容 :
コンテスト ( チーム戦、他大学の練習会に参加 )
コンテスト : Virtual Arena: Room 3301
アジア地区大会 2011 Kuala Lumpurサイト

コメント :
解けた問題
A : 実装問題。書く。
C : 2つの論理式が等しいか?変数に乱数を入れて適当な回数だけ2つの式の計算結果が一致するかをチェックする。
D : 2次元平面上にいくつかの点と線が存在する。線と点の間に他の点が存在しない場合、その点は線から見えるものとする。存在する点の60%以上の点が見えるか? 各点について、そこから上下左右で一番近い点を列挙する(lower_boundで)。点と一番近い点の間に線分があるかどうかを判定する(これもlower_bound)。
G : 2つの文字列a、bがある。aの後ろとbの先頭で同じ部分文字列が何か所存在するか? ローリングハッシュをマップにつめる。
H : 2次元平面上にいくつかの点とロボットが存在する。ロボットが点aから点bに移動するために必要な移動回数は? コストが1なのでBFSをする。

解けなかった問題
B : BITを使うらしい。
E : 一般マッチングで解けるらしい。一応本番中にtutte行列で完全マッチングを求めるコードを投げるもWA。そもそも問題概要を勘違いしている?(今の解釈だと同じサイズの部屋が2つ以上あると...)
F : サンプル出力を見て実装問題だと思い後回しにしていた。
I : 最初はどの方向でも良いので進んで、後は一番原点から遠ざかる場所に進むようなコードを書いたがWA。コーナーケースは見つけたものの...