競技プログラミング引退します

PCK2017予選は4完でした.

まぁこれで才能がないことがわかったので気持ちよく引退することが出来ます.

次回はこれに移行はしません.

ABC066

ABC066

テンプレは省略

A

sortして先頭2つを取っておわり.

ソース

#include <bits/stdc++.h>
using namespace std;

signed main() {
  int a[3];
  rep(i, 3) cin >> a[i];
  sort(all(a));
  print(a[0] + a[1]);
}

B

与えられた文字列が偶数の長さで,半分に割ったときに左右で一致していれば偶文字列と分かるのでsubstrで分割してあげる.

ソース

#include <bits/stdc++.h>
using namespace std;

signed main() {
  string s;
  cin >> s;
  int res = 0;
  
  while (true) {
    string a, b;
    s.erase(s.begin() + s.size() - 1);
    res++;

    if (s.size() % 2 != 0) continue;
    a = s.substr(0, s.size() / 2);
    b = s.substr(s.size() / 2, s.size());
    if (a == b) {
      break;
    }
  }
  print(s.size());
}

C

反転して末尾にpushしていくのは,先頭と末尾へ交互にpushしていくことと変わらないのはすぐに分かる. 先頭・末尾へのpush,アクセスが高速なデータ構造といえばdequeであるから,この子を丁寧に扱ってあげると答えに導いてくれる.

ソース

#include <bits/stdc++.h>
using namespace std;
 
signed main() {
  deque<int> q;
  int n = in();
  
  rep(i, n) {
    int a = in();
    if (i % 2 != 0) q.push_back(a);
    else q.push_front(a);
  }

  if (n % 2 != 0) {
    rep(i, n - 1) {
      cout << q[i] << " ";
    }
    print(q[q.size() - 1]);
  } else {
    rrep(i, q.size() - 1, 1) {
      cout << q[i] << " ";
    }
    print(q[0]);
  }
}

D

逆元を用いた {{}_n C_r \pmod{a} } の実装が分からず,時間内に解けなかった.

 {N}個の数が必ず一つ以上使われている長さ {N + 1}の数列から,長さ {k}の部分列の個数を出力する問題.

 { {}_n C_r} (組み合わせ)を使う.

そのままやってしまうと重複部分を数えてしまうので,重複分を引いてあげる.

 { {}_{N+1} C_k } (長さ {k}の部分列の個数)

 { {}_{N-d} C_{k-1} } が重複分( {d}は被った2つの数字の数列上での距離)

 {{}_{N+1} C_k - {}_{N-d} C_{k-1} }

逆元と親身に接することで答えがでる.

ソース

#include <bits/stdc++.h>
using namespace std;

lint fact[100010], ifact[100010];

lint pow(lint a, lint k) {
  if (k == 0) return 1;
  lint res = pow(a, k / 2);
  res = res * res % MOD;
  if (k & 1) res = res * a % MOD;
  return res;
}

lint inv(lint a) {
  return pow(a, MOD - 2);
}

lint C(lint n, lint r) {
  if (n < 0 || r < 0 || r > n) return 0;
  if (r > n / 2) r = n - r;
  return fact[n] * ifact[r] % MOD * ifact[n - r] % MOD;
}

signed main() {
  lint n = in();
  int N = n + 1;

  fact[0] = ifact[0] = 1;
  rep(i, 1, 100010) {
    fact[i] = (fact[i - 1] * i) % MOD;
    ifact[i] = inv(fact[i]);
  }

  int d = -1;
  int used[100010];
  fill(all(used), -1);

  rep(i, N) {
    int a;
    cin >> a;
    if (used[a] != -1) {
      d = i - used[a];
    }
    used[a] = i;
  }

  rep(i, N) { print((C(N, i + 1) - C(N - d - 1, i) + MOD) % MOD); }
}

1125 -> 1173(+48, Highest!!)

はやいところ水色になりたいです

Bash on Ubuntu on WindowsとWindowsでクリップボード共有っぽいことする

初投稿です.既出だったら許してください. Qiitaに投稿したやつをここにも残しときます

qiita.com

Windows10は2017年4月11日にCreators Updateが配信されました. そこで新しく追加された機能の中に「Windowsアプリケーションとの相互運用」があります.
今回はこれを利用して,Bash on Ubuntu on Windows(以下BoW)とWindowsとのクリップボード共有まがいのことをしてみようと思います.

準備

Windows10側での準備

まずはWindows10でのCreators Updateを行ってください.
そのあとghuntley/pasteboardreleasesから「pasteboard-v1.1.0.zip」をダウンロードしてください.この中の pbpaste.exe を使います.

ダウンロードし,展開したフォルダpasteboard-v1.1.0pasteboard にリネームした後,任意の場所に移動,コピーして環境変数pasteboard-v1.1.0 までのパスを追加します.

ここでは C:\app\pasteboard環境変数に追加しました.

コマンドプロンプトpbpaste と打って動くか確認したら準備は終了です.

BoW側での準備

改行コードや文字コードの変換に必要なnkf をインストールします.
sudo apt-get install nkf でインストール出来ます.Linuxはコマンド一つでインストール出来てとても楽ですね.

nkf --help と打ってヘルプが表示されたら準備は終了です.

作業

さぁ,実際に使うための作業をしましょう.
BoWを起動し,vim ~/.bashrc などで.bashrc を開きます.
ここに以下のコードを追加してください.

alias wcopy='clip.exe'
alias wpaste='pbpaste.exe'

保存して,source ~/.bashrc するかBoWを再起動してください.

使ってみる

windowsで適当なテキストファイルを作りましょう.ここではデスクトップにhoge.txt を作ってみます.

ばっしゅおんうぶんつおんうぃんどうず

ぽよよ

BoWで/mnt/c/Users/{Windowsのユーザ名}/Desktop に移動します.

cat hoge.txt | wcopy と入力するとコピーが出来ます.

その後pbpaste と打つとターミナルにコピーした内容が表示されますが,文字化けしていると思います.そこで間にnkf をはさみ,文字コードを変換してからコピーするようにします.

nkf -w hoge.txt | wcopy
(ちなみに,ここで改行コードをLFに変換してもclip.exe の仕様のせいかCRLFになってしまうっぽいのでwpaste したあとに改行コードを変換する必要があります)

wpaste で確認すると文字化けが解消されているかと思います.

また wpaste > out.txt とすることで wpaste の内容をout.txt に保存することが出来ます.

使い方まとめ

  • cat ファイル名 | wcopy でコピー
  • wpaste でコピーした内容が見れる
    • wpaste > ファイル名 でファイルに出力できる

以上でクリップボード共有まがいを実現する計画は完了です.
もし何かあったら,コメントかTwitterでリプしてくださると助かります.

2016年リリースデレマス曲個人的ランキング

この記事はProlab Advent Calendar 2016の"23"[::-1]日目の記事です.

www.adventar.org

だれ?

kurokoji(@kuro_koji_)です.
沖縄高専のメディア情報工学科2年の人間です.
久留米高専生ではないです.
情報オリンピック本選に出ます.宜しくお願いします.

藤忍佐々木千枝の担当をしています.

最近ではデレステのコミュ第39話 「The Words for LOVE」 にて,千枝が向井拓海藤本里奈大和亜季らを一喝するシーン

f:id:kurokoji:20170102003858j:plain

を見て

f:id:kurokoji:20170102003944j:plain

となっていました.

2016年リリースデレマス曲個人的ランキング

3位: Love∞Destiny

Love∞Destiny(佐久間まゆ,北条加蓮,小日向美穂,多田李衣菜,緒方智絵里)

第3位はデレステイベント LIVE Groove Dance burst(2016年6月30日から7月7日まで開催) にて登場した「Love∞Destiny」です.

出逢った瞬間に ココロは決まっていたの 未来永劫 添い遂げるって

好きな人に対する深い愛がストレートに伝わってくる曲であります. また,ぼくはこの曲のダンスが好きで,特に

f:id:kurokoji:20170102004004p:plain

f:id:kurokoji:20170102004008p:plain

の部分がめっちゃ好きです.

2位: 咲いてJewel

咲いてJewel(鷺沢文香,速水奏,橘ありす,塩見周子,二宮飛鳥)

第2位にランクインしたのはTHE IDOLM@STER CINDERELLA MASTER Cool jewelries! 003 に収録されている,「咲いてJewel」です.

前奏とかのテレテレテレテレ↑テレテレテレテレ↓テン↑テテテン↓(楽曲試聴で11秒あたりとか)がすごい好きです.

曲中の

「誰も知らない調べが」

の部分はありす (橘ですっ!!) が歌っているのですが,これがね,最高なんですよ.

1位: ハイファイ☆デイズ

ハイファイ☆デイズ(佐々木千枝,櫻井桃華,市原仁奈,龍崎薫,赤城みりあ)

堂々の1位にランクインしたのはLIVE Groove Dance burst(2016年3月31日から4月7日まで開催) にて登場した「ハイファイ☆デイズ」です.担当の千枝がいるよ!!

「昨日の涙は今日の勇気」

流した涙は決して無駄ではない,未来への糧となるんだというのが伝わってきます. 落ち込んでいるときに是非聴きたいパッションな曲です.

番外編 ~カバー曲~

jewelriesシリーズには,選出メンバーそれぞれがカバーした曲も収録されています.その中で好きなものを上げたいと思います.

きみにとどけ

きみにとどけ(橘ありす)

THE IDOLM@STER CINDERELLA MASTER Cool jewelries! 003 に収録されている,橘ありすが歌う「きみにとどけ」.

「きみにとどけ」は2009年10月6日から放送されたTVアニメ「君に届け」の主題歌です.

一番最初に聴いたとき,ありす(佐藤亜美菜さん)のウィスパーボイスと歌詞・メロディがマッチしており耳がとろけるかと思いました. 大音量&(イヤホン|ヘッドホン) で聴くことを強くオススメします.

佐藤亜美菜さんは天才だと思います.
リクエストしたミノPさんは天才だと思います.

みんなCD買おう

どうでしょうか.言葉は少々足りないと思いますが,多少は興味を持ってもらえたのではないでしょうか.

これは裏話なんですが,ぼくが初めてCDを買ったのがこのデレマス関係でして(このときはTulipとPaJe002を買った)自分でも驚きです.お金を掛けられるほど好きなものが出来たのも初めてです.デレマス,いや,アイマスはこれからの僕の人生に大きい影響を与えそうです.

デレマス全然しらないぞ,デレマス分かるけどデレステ程度でしか曲聴かんぞ,という方もこの機会に是非ともCDをご購入いただき,この世界にどっぷりと浸かって頂きたいです.
jewelriesシリーズはボイスドラマも入ってるし最高だよ!!最高!!

明日はふなちさんです.

第16回日本情報オリンピック 2016/2017 予選に参加した話

結果

これと比較した感じだと380点でした.
提出ミスしてなければ幸いです.
(追記) 360点で予選通過してました.プロ各位宜しくお願いします.ちなみに5問目の1ケースにinputを投げてしまい,20点を失いました.

1問目

やるだけ.もうちょっとコンパクトなコードを書きたかった.無駄な部分が多い.

// テンプレ省略

signed main() {
  int a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;

  int ans = 0;
  if (b == a) {
    print(ans);
    return 0;
  }
  if (a < 0) {
    ans += c * abs(a);
    a = 0;
  }
  if (a == b) {
    print(ans);
    return 0;
  }
  if (a == 0) {
    ans += d;
  }
  print(ans + (b - a) * e);

  return 0;
}

2問目

これもやるだけ.b は使わなくていい.

signed main() {
  int n, m;
  cin >> n >> m;
  int ans = 0;
  vi a(m);
  REP(i, m) {
    int b;
    cin >> a[i] >> b;
  }
  sort(ALL(a));
  reverse(ALL(a));
  REP(i, m - 1) {
    if (a[i] < n) {
      ans += (n - a[i]);
    }
  }
  print(ans);

  return 0;
}

3問目

D という長さになればいいのである地点から東西南北4方向を見て# でなければそこからdfsをして,深さがD になったら答えに1加える.方向を引数でもってやればいい.最終的に出た数は被りがあるので2で割ってやる.別にfor でやっても良かった.
例年の3問目よりかなり簡単なのでは.多分ここらへんまでで30~40分.

int n, m, d;
char s[128][128];
int ans;

void dfs(int y, int x, int dep, int ddy, int ddx) {
  if (dep == d) {
    ans++;
    return;
  }
  int ny = y + ddy, nx = x + ddx;
  if (!inside(ny, nx, n, m)) return;
  if (s[ny][nx] == '#') return;
  dfs(ny, nx, dep + 1, ddy, ddx);
}

signed main() {
  cin >> n >> m >> d;
  REP(i, n) cin >> s[i];

  REP(i, n) REP(j, m) {
    if (s[i][j] != '#') {
      REP(k, 4) {
        int ny = i + dy[k], nx = j + dx[k];
        if (!inside(ny, nx, n, m)) continue;
        if (s[ny][nx] == '#') continue;
        dfs(i, j, 1, dy[k], dx[k]);
      }
    }
  }
  print(ans / 2);

  return 0;
}

4問目

テストケース1~3まで通しました.bitDPらしいですね.わかりません.
脳を完全に停止してnext_permutation() をし,順列を全列挙した.順列は最大でm! 種類あるのでm が大きい値だと計算量がまずい.このコードだとO(n * m!)になりますかねえ.ひどいなこれ. 順列と元のぬいぐるみと比較して,違う種類だったらカウント.そしてmin をとる.1時間ぐらいずっと回してた.

signed main() {
  int n, m;
  cin >> n >> m;
  vi a(n), b(m), cnt(n + 1);
  REP(i, m) b[i] = i + 1;
  REP(i, n) {
    cin >> a[i];
    cnt[a[i]]++;
  }
  int res = INF;
  do {
    int c = 0;
    int idx = 0;
    REP(i, m) REP(j, cnt[b[i]]) {
        if (a[idx++] != b[i]) c++;
      }
    }
    chmin(res, c);
  } while (next_permutation(ALL(b)));
  print(res);
  
  return 0;
}

問題5

解法が思いつかず,適当にdfsしたら1ケース目は通った.残りはなんかセグフォが起きたので諦めた.

int h, w;
vvi a;
int sum = 0;
bool vis[1000][1000];

void dfs(int y, int x, bool fi = false) {
  bool flg = false;
  REP(i, 4) {
    int ny = y + dy[i], nx = x + dx[i];
    if (!inside(ny, nx, h, w)) continue;
    if (a[y][x] > a[ny][nx]) {
      flg = true;
      dfs(ny, nx);
    }
  }
  if (!flg && !fi && !vis[y][x]) {
    sum++;
    vis[y][x] = true;
  }
}

signed main() {
  cin >> h >> w;
  a = vvi(h, vi(w));
  REP(i, h) REP(j, w) cin >> a[i][j];
  int res = 0;
  REP(i, h) REP(j, w) {
    memset(vis, 0, sizeof(vis));
    sum = 0;
    dfs(i, j);
    if (sum > 1) res++;
  }
  print(res);

  return 0;
}

問題6

拡張dijkstraらしいですね.
「いい感じにするdijkstraやろ!w」
と思ったけど,ぼくはスーパー適当なdijkstraを書いてsampleが通らないけど取り敢えず出しました.全ケース落ちました.コードは載せません. まぁでも,去年はdijkstraという言葉すら知らかったので成長はしたのかなという感じです.

感想

つらいです.3問目までめっちゃ簡単で「いけるやろ~」と調子に乗ったら,難易度が跳ね上がりました.明らかに精進不足です. もし予選通ってたら,本選までにDPとか克服していきたいです.

あと3問目まで答えを格納する変数名がans なのに4問目からres なのウケますね.

あー ねんまつ

JOI予選お疲れ様です

疲れました.僕は多分380点です.

この記事はICT Advent Calender2016 11日目の記事です.

僕が今年出た大会まとめ

今年は,去年より大会に出たいという気持ちが大きかったからか,多くの大会に出てるような気がします.
この中では,パソコン甲子園2016プログラミング部門もう一つの本選で8位になれたことは印象に残っていて,「工藤忍北条加蓮というチーム名がPCKのホームページに載っているのが面白かったです.因みに,FirstACも取れてウケてます.来年は本選に行きたいと思います.

覚えた・習得したこと

  • C#(高専プロコンでGUIを作った)
  • 競プロ(去年からやっているが今年は結構成長出来たと思う)
  • vim(今年からプラグインとか入れてる)
  • 画像処理(高専プロコンでほんのすこし触った)

興味があること

  • マラソンマッチ系の大会(まだ出たことないのでCodingameとかやっていきたい)
  • CTF(少しだけやって結構面白かったのでやりたい)
  • 画像処理(面白そう)
  • バイル系アプリ開発(Androidとかやりたい)
  • Python(面白そう)

欲しいもの

今年なんかめっちゃオタクになったっぽい

もうちょっとでモバマスのほうもPLvが100超えそうですし,デレステも楽しいですし(絶対特権主張しますっ!がすき),佐々木千枝は心臓が痛くなるほど可愛いし,工藤忍はリンゴの皮を剥くのが上手いです.
CDも結構買ったような気もします.

あと最近は冴島清美ちゃんが僕の中でキテます.














逸れ!w話が逸れ過ぎてシルク・ド・ソレイユになった!w














そんなことはどうでもよくて

来年からどうなるんだろうという不安があります.
何でも出来る人@orisano先輩が卒業されるので,ICT委員会の技術力が著しく低下するのでは,ということがあります.

僕もorisano先輩には色々教わっていますし,他の人もそうだと思います.しかし,来年はいません.今度は僕らが後輩に教えないといけません.特に競技プログラミングは誰が引っ張っていくのでしょうか.今,一番出来る人は@37kt_先輩なので是非とも後輩教育をお願いしたいものです.僕もやりますけど.

来年の目標

  • 高専プロコン競技部門†優勝†
  • パソコン甲子園2017プログラミング部門本選出場
  • SuperCon2017本選で上位

この3つの目標を達成するために頑張っていきたいです.

最後に

以上です.

明日は@yagamian_sobaya先輩と@Luzhiledです.
昨日は@manae_manawayでした.