naoya_t@hatenablog

いわゆるチラシノウラであります

GCCのバグ?未定義動作?g++とclang++で違う結果になるコード

こないだAtCoderの過去問を解いてて
ローカルでは正解が出ているのにサーバ上でREが出まくってはまったのでメモ。

再現できる形で変形&単純化を繰り返した結果がこんな感じ

#include <vector>
#include <cstdio>

std::vector<int> a, b;

int f() {
  a.push_back(-1);
  b.push_back(-1);
  return (int)a.size();
}

int main() {
  int first = f();
  printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
  a[0] = f();
  printf("a[0]=%d, b[0]=%d\n", a[0], b[0]);
  return 0;
}
続きを読む

ARC006-D アルファベット探し

みょんみょんがツイートしてたやつ

7x7ピクセルで定義されたA,B,Cの文字(正の整数で等倍拡大したもの、90度刻みで回転したものを含む)の出現回数を数える問題。
f:id:n4_t:20170702234607p:plain

続きを読む

拡張ユークリッド互除法の話

先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)

拡張ユークリッド互除法というのは、ax+by=gcd(a,b) を満たすx,y\in\mathbb{Z} を求める方法。
a,bgcd(a,b) で割れば a'x+b'y=1(a'とb'は互いに素)という形になる。

続きを読む

Crayfish Scrivener (IOI 2012, day 1)

6月は永続データ構造強化月間(そういうことにしました)、ということで
qnighy先生の
Re永続データ構造が分からない人のためのスライド
で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。

続きを読む

連分数 (continued fraction)

連分数 - Wipikedia

こないだのJune Long ChallengeのEuler Sumを考えてる時に
Mark Jason Dominus氏のスライド
Arithmetic with Continued Fractions
を読んだ時のメモ。

連分数とかいじるのって多分昔SICPを読んだ時以来。

続きを読む

小さい数n(100万までとか)の素因数分解

CodeChefのフォーラムで June Challenge 2017の問題 Chef and Prime Queries (PRMQ) の解法を読んでいて
discuss.codechef.com

素因数分解をするのに

This can be done by creating a Smallest Prime Factor array in the sieve function itself.

とあって。エラトステネスの篩 (Sieve of Eratosthenes) をするときに、篩と同時に一番小さい素因数のテーブルを作ってしまえば素因数分解が簡単、っていう話。

続きを読む