C-merのブログ

ザ・雑記

ICPCアジア地区横浜大会に参加しました(2018年まとめ)

こんにちは.C-merです.
今更なのですが,12月8,9日に行われたICPCアジア地区横浜大会について振り返りたいと思います.

実に3週間も経ってしまいまいしたし(なんか申し訳ございません),一部誇張,誤解,記憶違いあるかもしれないですが,そうゆう場合はぜひご指摘ください.

チームはCatKOder(KO大学)でAlbicilla, tokuminiと出ました.

 

1. 事前準備編
本番と同じ環境に慣れるということでCLionでコーディングしたりしなかったり,,
実行方法などに癖がある(?)ので,チームメンバー全員がそこでつまづかないというのは,良いと思った

あとは,キーボードをちょうどUS配列にしたので,その点も戸惑わずにできてよかったかと..

 

2. 8日リハーサル編
諸事情あり,朝は4時半に起き,横浜某所で5kmほど泳ぎ,そのあと図書館で少し問題を解いたりしていた
パソコンについては起動が少し遅い&初めに画面が乱れるという謎トラブルがあったりしたが特に問題なしという感じ.リハーサル用問題が普通に難しくて萎えた.

 

3. 9日 本番編
前日のabcではキャスト忘れというしょうもない理由で全完を逃してしまった(アホ)ため,テンション低め&少し寝不足といったところ.前日にコンテストは出なくても良いかも(実際,出た人が少なかったとか?(JOIもかぶっていたようです)).

〜開始〜
着実な4完を目指し,みんなでA問題を読む.自分が数字はそのまま,文字にはASCIIコードに大きな定数に足して数列として,比較する解放を思いつき(この日1番の活躍?),実装はtokuminiさんに任せて次の問題へ.そんなに遅くなく,幸先の良い滑り出しとなった.

そこからはBとCを交互に見たり見なかったり.

Cについては逆に入れるといいんじゃねとなり,自分が実装を始める.
焦って,座標という概念がわからなくなる←
サンプルケースや自分たちで考えたケースについても,通るので提出するもWAで絶望,,
そこから時間が経つ
2人に解放そのものが間違ってる可能性もあると言われ凹む.
Albicillaにループ内の実際には処理を行わないときは,continueしたら?とのことなので,とりあえずそれで提出.tokuminiさんにも助けを求めようとしたら,通った.

Bについてはtokuminiさんが通してくださる.

その後,Gについてもtokuminiさんが通してくださる.

D問題で解法を出せば即座に反例を返すごっこをしたり,K問題を読んだりして,終了.

 

4. 9日 コンテスト後の色々編
コンテスト後には,講評や表彰式みたいなものや,懇親会的なやつをやって楽しむことができた.(なんかしらの企業賞が欲しかったりもした..)
悪名高き情◯工学実験のために10日の企業見学ができなかったので,ここで色々な企業を見て回れたのは大変よかった.

 

5. 総括
結構tokuminiさん頼りになってしまったので,精進していきたいと思った.
楽しかったので来年も是非参加したい.
あと,風邪には気をつけましょう.

AtCoder Regular Contest 061 D - すぬけ君の塗り絵 / Snuke's Coloring

問題
AtCoder Regular Contest 061 D - すぬけ君の塗り絵 / Snuke's Coloring
beta.atcoder.jp

使用言語
C++

要点
・ある塗られたマスを含む9つの各3*3の正方形にスコアを設けてそこの数だけをカウントする
・mapで管理して,キーはpairにする
 要素へのアクセスは{,} でも make_pairでも出来るっぽい
・マスの番号が1〜Nなのに注意
・0のものについては,一つ以上塗られたマスを含んだ時に全体から引いた
・ans[0]でキャストし忘れてバグりました

所感
・Dにしては難しいと思ったのですが,どうなのでしょうか
・解説雑ですみません

コード

ull ans[10];
map<pair<int, int>, int> mp;

int main()
{
  int h, w, n;
  cin>>h>>w>>n;
  ans[0] = (ull)(h-2) * (w-2);

  REP(i,n) {
    int a, b;
    cin>>a>>b;
    FOR(dx,-1,2) {
      FOR(dy,-1,2) {
        if (a+dx<2 || a+dx>h-1 || b+dy<2 || b+dy>w-1)
          continue;

        //cout<<a<<" "<<b<<" "<<a+dx<<" "<<b+dy<<endl;
        pair<int, int> tmpp = {a+dx,b+dy};//make_pair(a+dx,b+dy);
        //ここの入力形式はどちらでも問題がないようです
        if (mp.find(tmpp) == mp.end()) {
          mp[tmpp] = 1;
          ans[0]--;
        } else {
          mp[tmpp]++;
        }
      }
    }
  }

  for (auto itr : mp) {
    ans[itr.second]++;
  }

  REP(i,10) {
    cout<<ans[i]<<endl;
  }

  return 0;
}

SRM 519 Div 1 - Problem 250 BinaryCards

問題
SRM 519 Div 1 - Problem 250 BinaryCards
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
0から63までの数字のカード(全て1枚ずつ)を使う.数字xのカードには2ˆxのドットが描かれている.
最初全てのカードは伏せられている.AからBまでの連続する整数について,カードを表にして,カードに描かれるドットの数で表す.表になったカードのドットの合計を求める.

方針
表のカード(のドットの数)について考えると,
 6: 2 4
 7: 1 2 4
 8: 8
となる.表になったドットは 1+2+4+8=15
→各数字のビット和でわかりそう

しかし,O(N)で最大10ˆ18になるので連続する整数のビット和を全て取るのは現実的でない.

ここで単純化して考える.
A = 2ˆ30 + 1, B = 2ˆ30 + 24とする.
答え(Cとする)にはもちろんA, Bが含まれる(C|A==A, C|B==B)
差分について考えると,23 = 16 + 4 + 2 + 1 = 0x10111
これの最上位ビット以下のは全て1になりそう(例 20ˆ3+8)
なのでそれ以下を1にする.

所感
・わかりにくすぎる問題文に反して,楽しい問題
・コード短すぎ問題

コード

class BinaryCards {
    public:
    long long largestNumber(long long A, long long B) {
      ll ans = A | B;
      //差分の最上位ビット以下のビットが1になるようにOR
      //どうせ最上位以下のビットは全て1になるので,最上位1つずつ左シフトしてforループ
      for (ll i = B - A; i > 0; i = i>>1) ans |= i;
      return ans;
    }
};

SRM 518 Div 1 - Problem 250 LargestSubsequence

問題
SRM 518 Div 1 - Problem 250 LargestSubsequence
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
与えられた文字列から各文字の相対的な順序は変えずに,文字列を抽出し,その中で辞書順で最も大きくなる文字列を返す.

方針
文字列 .*XY.* について,
 X>=YならXは残す
 X所感
・文字列の連結が自然にできるのはありがたい.言語仕様に感謝.

コード

class LargestSubsequence {
    public:
    string getLargest(string s) {
      string ans = "";
      int l = s.length();
      ans += s[l-1];
      for (int i = l-2; i >= 0; i--) {
        if (ans[0] <= s[i]) ans = s[i] + ans;
      }
        return ans;
    }
};

Tax Rate Changed (1192)

問題
Tax Rate Changed (1192)
税率変更 | Aizu Online Judge


使用言語
C++

方針
・一つの数式で強引に解こうとする→失敗
・素直に本来の値段で全探索

所感
・素直に生きたい

コード

#define xplice(p,q) p * (100 + x) / 100 + q * (100 + x) / 100
#define yplice(p,q) p * (100 + y) / 100 + q * (100 + y) / 100

int x, y, s, ans;

int main()
{
  while (cin>>x>>y>>s, x) {
    ans = 0;
    for (int a = 1; a <= s; a++) {
      for (int b = 1; b <= s; b++) {
        int tmp = xplice(a,b);
        if (tmp < s) {
          continue;
        } else if (tmp == s) {
          ans = max(ans, yplice(a,b));
          //cout<<a<<" "<<b<<" "<<tmp<<" "<<yplice(a,b)<<endl;
        } else {
          break;
        }
      }
    }
    cout<<ans<<endl;
  }

  return 0;
}

AtCoder Beginner Contest 111 C - /\/\/\/

問題
AtCoder Beginner Contest 111 C - /\/\/\/
C - /\/\/\/

使用言語
C++

方針
・iが奇数,偶数の時に登場する数の個数で考える.奇数,偶数でaiがどれくらい出てきたかをp1[i], p2[i]で管理.
・場合分け
 p1,p2のどちらかに複数の最頻値があるor p1,p2の唯一の最頻値が使う
  →その最頻値を使う
 上記以外
  →p1の最頻値とp2の2番目かp2の最頻値とp1の2番目のどちらかを使う(片方の最頻値ともう片方の2番目が同じ数字になることはない,上で弾かれるため)

所感
・バグ祭りで死にましたかかってしまった.無念..
・ACまでに想定していた時間の5倍くらい

コード

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
#define FOR(i,a,b) for (size_t i = a; i < b; i++)
#define REP(i,b) FOR(i,0,b)
#define RFOR(i,a,b) for (size_t i = a-1; i >= b; i--)
#define RREP(i,a) RFOR(i,a,0)
#define INF 1e7
#define num 111111

int p1[num], p2[num];
vector<int> a, b;

int main()
{
  int n, m1 = 1, m2 = 1, tmp;

  cin>>n;
  REP(i,n/2) {
    cin>>tmp;
    p1[tmp]++;
    cin>>tmp;
    p2[tmp]++;
  }

  REP(i,num) {
    if (p1[i] > m1) {
      a.clear();
      a.push_back(i);
      m1 = p1[i];
    } else if (p1[i] == m1) {
      a.push_back(i);
    }

    if (p2[i] > m2) {
      b.clear();
      b.push_back(i);
      m2 = p2[i];
    } else if (p2[i] == m2) {
      b.push_back(i);
    }
  }

  if (a.size() > 2 || b.size() > 2) {
    cout<<n - m1 - m2<<endl;
  } else if (a[0] != b[0]) {
    cout<<n - m1 - m2<<endl;
  } else {
    sort(p1, p1+num);
    sort(p2, p2+num);
    int r = max(m1 + p2[num-2], m2 + p1[num-2]);
    cout<<n-r<<endl;
  }

  return 0;
}

SRM 517 Div 1 - Problem 250 CompositeSmash

お久しぶりです.

問題
SRM 517 Div 1 - Problem 250 CompositeSmash
TopCoder Statistics - Problem Statement

使用言語
C++

問題概要
Nを任意の回数(0回でも良い)分割して,targetに(どちらかの整数が)一致したらYes,一致しなければNoを返す.
分割とは,整数xを分割するとき,2以上のy,zに分割され,それらの積はxになる.


方針
・任意の回数→再帰
再帰の中身
  数値がtargetと一致→Yes
  それ以外→全ての分割した数字の組みについてtargetと一致するか判定or更に分割

所感
・動かしたら動いたのでよかった.

コード

bool smash (int a, int b)
{
  if (a == b) {
    return true;
  } else {
    //flag: 素数じゃないか(分割できるか)判定
    //rtn: 全ての分割した結果がtargetに行き着くかを返す
    bool flag = false, rtn = true;
    for (int i = 2; i * i <= a; i++) {
      if (a % i != 0) continue;
      else {
        flag = true;
        rtn = rtn & (smash(i,b) | smash(a/i,b));
      }
    }
    if (flag) return rtn;
    else return false;
  }
}

class CompositeSmash {
    public:
    string thePossible(int N, int target) {
      if (smash(N, target)) return "Yes";
      else return "No";
    }
};