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 アルファベット探し
みょんみょんがツイートしてたやつ
競プロ全然やったことない人でも、業務でやってるならこれくらいは書けてほしいな、と思う問題がこの辺なんだけど、ちょっとハードル高いかもなあ、とは思ってる。https://t.co/yxKa9oIwUM
— chokudai(高橋 直大) (@chokudai) 2017年6月30日
7x7ピクセルで定義されたA,B,Cの文字(正の整数で等倍拡大したもの、90度刻みで回転したものを含む)の出現回数を数える問題。
Codeforces Round #421 (Div. 2)
http://codeforces.com/contest/820
今日もC→B→A(→D)の順で。2完 (oox--)。
(C問題(Div1だとA)のごたごたでunratedになった模様)
拡張ユークリッド互除法の話
先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)
拡張ユークリッド互除法というのは、 を満たす を求める方法。
を で割れば (a'とb'は互いに素)という形になる。
Crayfish Scrivener (IOI 2012, day 1)
6月は永続データ構造強化月間(そういうことにしました)、ということで
qnighy先生の
Re永続データ構造が分からない人のためのスライド
で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。
連分数 (continued fraction)
こないだの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) をするときに、篩と同時に一番小さい素因数のテーブルを作ってしまえば素因数分解が簡単、っていう話。
続きを読む