学習の栞

学びたいことと、学ぶべきことと、学べることの区別がついてない人間の進捗管理

Harekaze Advent Calendar 2017 day3

あどべ3日目です

adventar.org

機関室の幽霊と化したTeam:Harekazeの黒木洋美です.最近CTFに参加しておらず申し訳ないということで,アドベントカレンダー書こうとしたんですがネタが無いのでコードを書きました.

Miller-Rabinの素数判定アルゴリズム(167バイト,python3)です.バグってない保証はありませんが使いたい方はお使いください.

import random as r
def M(n,s):
 m,f=n-1,0
 while s:
  o=m&-m;y=pow(r.randint(1,m),m//o,n);s-=1
  while o:x,y=y,y*y%n;o//=2;f|=(y==1)*(x-1)*(x-m)
  f|=x-1
 return f==0

CLRSの整数論アルゴリズムの章の疑似コードを元に実装しています.CLRSの鈍器版を買うと精選トピックスとして整数論アルゴリズムの章を読むことができます.さすが世界標準MIT教科書ですね(は?

ゴルフ前の実装はこちら.

import random, math

def ModularExponentiation(x,p,n) :
	return pow(x,p,n)

def MillerRabin(n,s):
	for j in range(0,s) :
		a = random.randint(1,n-1)
		if Witness(a,n) :
			return False
	return True

def Witness(a,n) :
	u = (n-1)//((n-1)&-(n-1))
	t = 0
	tmp=((n-1)&-(n-1))//2
	while tmp :
		t += 1
		tmp //= 2
	x = [ModularExponentiation(a,u,n)]
	for i in range(0,t) :
		x.append(x[-1]*x[-1]%n)
		if x[-1] == 1 and x[-2] != 1 and x[-2] != n-1 :
			return True
	if x[t] != 1 :
		return True
	return False

def test() :
	def Naive(n) :
		i = 2
		while i*i <= n :
			if n % i == 0 :
				return False
			i += 1
		return True

	# OEIS-A002997
	Carmichael = [561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633,62745,63973,75361,101101,115921,126217,162401,172081,188461,252601,278545,294409,314821,334153,340561,399001,410041,449065,488881,512461]
	for n in Carmichael :
		assert(MillerRabin(n,100) == Naive(n))
	# random
	Random = [random.randint(1<<1,1<<32) for i in range(100)]
	for n in Random :
		print(n, Naive(n))
		assert(MillerRabin(n,100) == Naive(n))

if __name__ == '__main__' :
	test()

関数testに実装したテストを通過する状態を保ちながらゴルフしました.(関数名の変更に伴ったテストの書き換えはしていますが,それ以外は変更していません)テストはカーマイケル数とランダムに生成した数について試し割りと結果を比較しています.

プログラミング言語と採用

雑記です.

twitterで「Haskell書ける人探してる会社受けてみたら,Haskell業務で書くわけじゃなかったー」という話を見かけて,とある会社の人事担当者との会話を思い出したので書き留めておく.

インターンの説明会での会話
私「御社XX言語使ってるんですねー興味ありますー.」
人事「でも言語はツールなので用途に合わせて習得して貰わないとですね.今使ってる言語使えるからという理由でXX言語使ってる会社に行きたいって選択はあんまりよろしくないかな.」
私「そうですねー(棒」

という会話があった.私は「今使ってるのがXX言語だからXX言語使ってる御社に興味がある」とは一言も言っていないのだが先読みしてそう言ったらしい.XX言語を使ってる会社に興味がある理由として,「自分がXX言語使っている」というのはあり得そうな理由の一つだが,他にも「言語を適切に選択できているという前提においてXX言語での実装が必要になるような問題が転がっているためそれに取り組みたい」だとか理由はあるのだからもっと視野を広く持って欲しいなーと人事担当者に思った話でした.

ARC084 D : Small Multiple 解説(お気持ちだけ)

はじめに

AtCoder公式の解説が天才の解法だったので,凡人の解法を書いておく.ふわっとした解法のお気持ちだけ書いておく.はじめに言っておくが,詳解というよりは考察メモに近い.

正確に言葉に表すのが難しい解法なのでお気持ち解説と思ってゆるして.

解法

グラフ作ってダイクストラをやる.

考察

筆算をしてみると,K*m の下位 i桁目は,mの下位i桁で決まることがわかる.筆算は逐次計算することができて,それを踏まえた筆算をやってみると下図の赤字で書いた部分を状態に持ってDPをやりたい衝動に襲われる.

f:id:konjo_p:20171107003633j:plain

さらに状態遷移を考えてみると,下図のような状態遷移でグラフを作れることがわかり,0から出発してまた0に戻ってくるまでの最短経路が答えになることがわかる.

f:id:konjo_p:20171107003615j:plain

コーディングすると通るので書く.

#include <iostream>
#include <utility>
#include <queue>
#include <algorithm>

using namespace std;

#define fi first
#define se second
#define rep(i,n) for(ll i=0; i < (n); ++i)

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int dist[100010];
const int INF = 100;

int main() {
	ll K;
	cin >> K;
	rep(i,100010) dist[i] = INF;

	bool src = true;
	priority_queue<pii> q;
	q.push(pii(0,0));
	while(q.size()) {
		pii a = q.top(); q.pop();
		a.fi = -a.fi;
		if(a.fi > dist[a.se])
			continue;

		for(int i = src ? 1 : 0; i < 10; i++) {
			int nex_stat = (a.se + i*K)/10;
			int weight   = (a.se + i*K)%10;
			if(dist[nex_stat] > a.fi + weight) {
				dist[nex_stat] = a.fi + weight;
				q.push(pii(-dist[nex_stat], nex_stat));
			}
		}
		src = false;
	}

	cout << dist[0] << endl;
	return 0;
}

CODE FESTIVAL 2017 予選通過記

例年はCode Festivalの本戦参加記だけを書いているのだけれど,今年は予選が激戦だったので書き残すことにした.技術的な内容は含まない所謂ポエムである.

今年のCode Festivalの情報が出たのは7月末.過去3年間日本人学生上位200名がCodeFestivalの参加対象だったのだが,今年の日本人学生の参加枠は80名に減っていた.上位200名の通過枠であれば,過去の例から言ってTopCoderのDiv1で戦っている競技プログラマであればほぼ確実に通過できる難易度なのだが,上位80名が通過ラインとなると通過には相応の実力が求められる.日本人順位80位のレートはTopCoderでは1600強であり,AtCoderでは2300強である.この参加枠減少の発表を受け,競技プログラマの一大交流サイトであるtwitter上では大変な騒ぎとなっていた.なお,昨年より追加されていた海外学生の出場枠は20枠と昨年と同様の数が維持されていた.ただし海外学生枠については地域的な多様性を考慮した選抜方法に変更されており,強豪国の参加枠が実質的に数枠減ったことになる.

予選A,配点から4問目の700点問題を早解きが通過ラインとなることが予想される配点であり,事実そのようになった.私は4問目を時間内に解くことすらできず通過は叶わなかった.昨年までであれば予選Aでの通過枠が100名前後に設定されていたため,予選Aで通過を決め気楽に予選B,昨年からは加えて予選Cに出場することができていたのだが今年はそうはならなかった.私の実力と通過枠の狭さから順当と言えば順当なのだが,3問目までをそれなりの速さで解いていただけに悔しかった.

予選B,配点は予選Aと同様に4問目の700点問題が通過ラインとなるような設定であった.結果を見ると700点を解いて4問正解していた参加者は予選通過,3問目を落としたものの700点問題を正解し早い段階で3問正解していた参加者も予選通過したようだ.この予選で通過し予選Cに賭けることは避けたかったのだが,そう甘くはなく結果は3問正解.しかも正解した時間もかなり遅くコンテスト終了時点で全く期待できないとわかる順位を取ってしまった.4問目も正解を導くのに必要な考察自体はできていたのだが,動的計画法に落とし込む最後の段階で失敗してしまい,挙句貪欲法を考え始めるという有様であった.

予選C,やはり4問目の700点問題が通過ラインとなる設定だった.予選Cの実際の通過ラインは1-3問目までを高速に(おそらく10分以内で)正解するところにあったようだ.私はこの予選で無事4問目に正解し,本選進出を決めることができた.4問目正解時点での日本人順位は20位で,残りの問題は高難度問題であったからその時点で予選C通過は殆ど確定であった.40分弱で4問正解した後は落ち着いて順位表を眺めたり,高難度問題を考察してみたりすることができた.

予選を通して,Code Festival,また日本人学生の競技プログラミングのレベルが上がっていることを実感した.最初のCode FestivalはTopCoderの緑コーダーレベルでも十分に通過が可能なコンテストであった.それが今年はAtCoderでいうところの橙並のパフォーマンスを出さねば予選通過できないコンテストとなってしまった.今年は参加枠の半減という大きな変化があったものの,それを差し引いても日本人学生の(あるいは日本に限らず世界全体の)競技プログラミングレベルは上がっている.初心者から上級者まで楽しめる十人十色のプログラミングコンテストを謳い,200名の参加枠を設定した最初の Code Festival,200名の設定では本当の初心者を本選に呼ぶことができなかったという理由で行われた最初のCode Thanks Festival,あの頃からするとCode Festivalの色は随分と変わってしまったと感じる.あれだけの規模のイベントを開くのだから予算的な問題があることは承知しているし,むしろ昨年まであの規模で,そして縮小したとはいえ今年もこの規模でオンサイトコンテストが開かれること自体素晴らしい事だと思う.そうはいっても一抹の寂しさを感じずには居られないのだ.

何はともあれ,これまでの3回のCode Festivalでもそうだったように,来るCode Festivalでもそこで夢のような時間が流れることは疑いない.私にとっては最後となるCode Festivalで少しだけ夢の時間に浸ってこようと思う.


これは蛇足だが,(おそらく)今年から「本プログラミングコンテストの結果は、リクルートホールディングスインターンシップ並びに採用選考とは一切関係ありません。」の文言がCode Festival公式サイトに追加されている.あれだけ競技プログラマを食い散らかしていればそう書かざるを得なくなったのも頷けるが.

Tokyo Westerns CTF 3rd 2017 WriteUp

team Harekaze で参加しました.

チームとしては940pts,33rd.
個人的には自明Crypto一問を通して64ptsを入れました.

BabyDLP

解法:1bitづつ特定できるのでやる.

最後はwhileの終了条件で格好よく抜けたかったけどなぜか上手くいかないのでbreakとか書き足したり,途中まで取れた結果をコード中に書いてみたりした.

#!/usr/bin/env python3

import socket
import time
import Crypto.Util.number

soc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
soc.connect(("ppc2.chal.ctf.westerns.tokyo", 28459))

flg = 0
p = 160634950613302858781995506902938412625377360249559915379491492274326359260806831823821711441204122060415286351711411013883400510041411782176467940678464161205204391247137689678794367049197824119717278923753940984084059450704378828123780678883777306239500480793044460796256306557893061457956479624163771194201
g = 2

soc.send("0\n".encode('ascii'))
time.sleep(0.1)
prev = int(soc.recv(300).decode('ascii').rstrip(), 16)
print(prev)

add = 1
it = 0
while prev != g :
	soc.send((hex(flg + add)[2:]+'\n').encode('ascii'))
	time.sleep(0.1)
	tmp = int(soc.recv(300).decode('ascii').rstrip(), 16)

	print("iter : ", it, " ,recv : ", tmp)

	if tmp == (prev*pow(2,add,p)) % p :
		# 0 -> 1
		pass
	elif tmp == (prev*pow(pow(2,add,p),p-2,p)) % p:
		# 1 -> 0
		flg = flg + add
		prev = tmp
	else :
		break
#		assert(0)

	add *= 2
	it += 1

#flg = 50708000582382096636610604573295443076056584710334161094159154216560653240031124059562811961899120099043361370237
print(flg)
print(Crypto.Util.number.long_to_bytes(flg).decode('ascii'))

2の補数表現について

「2の補数表現で負の数を作るには,正の数の表現のビットを反転して1カウントアップする」という2の補数表現の解説に対する補足です.なぜこの方法で負の数を表現できるのかを補足します.

a : 32bitの整数
~a : aの反転


a + \tilde{} a = 2^{32}-1 \\
a + \tilde{} a \equiv -1 (\mod 2^{32}) \\
 -a \equiv \tilde{} a + 1 (\mod 2^{32})

というわけです.
あとはどの範囲を表現させるか決めればok.

第三回ドワンゴからの挑戦状(dwacon)参加記

予選

Aやるだけ,B問題に手間取った.B問題に手間取ったときはもうだめかと思ったが,C問題D問題が得意な感じの問題だったので助かった.E問題の部分点確定で18卒パワーを使って予選通過が決まると思ったでEの部分点を取りに行った.方針は比較的早く立ったが,苦手な感じのDPで部分点を確定させるのに手間取ってしまった.

結局32位に食い込むことができ,非18卒が上に11人以上居れば通過が確定.後日予選通過メールが届いた.

本戦

前日

オープンコンテストの告知で公開された500-1100-1200(25)-1300という配点を見て凍りつく.Acで525ptsとった後は座るだけになることが見える.変な貪欲が想定解法の500ptsだと最悪0完もあり得るなと絶望するなどしていた.

本戦開始前

集合時刻の4時間前に宿泊先のホテルを出て,部屋は清掃中の時間だし行くあて無いなーとか言いつつ歌舞伎座周辺をぶらぶら.

15時頃にドワンゴのオフィスに上がる.

集合時刻が15時というドワンゴ的かつ人道的な時間.さすがドワンゴ

受付が終わった後,控え室でTシャツを着たりニコ生用のアンケートを記入するなどする.Tシャツにタグがついていたのだけれど,はさみを持っていなかったので噛み切ろうと試みるも失敗.思いっきり引っ張ってみたらタグの糸が切れてタグを外すことができた.

準急さんやtozangezanさんが,「自己紹介書けないんだけど」と言いながら競プロerのいつものノリで会話をしていた.

コンテスト

A問題を500点と思って舐めてかかったら痛い目を見た.30分経ってもA問題の方針が見えない.辛い.正しい式にできるかどうかの判定は式が破綻した部分を数える感じで判定できることが分かったが,式の計算結果の最大化の方法が全くわからない.DPできる感じに見えなかったので必死になって貪欲を考える.

A解けないことが有り得ると思い,先にCの部分点を確保しに行く.Cの部分点は自明に二重ループ回すだけだった.35分ちょっとで25ptsを確定させる.

再びA.頭を冷やして考える.段々とDPが見えてくるが状態の持ち方がわからない.スタックの状態どうやって持つのとか言っていた.このあたりでは貪欲の可能性は完全に捨てていたが状態の持ち方が見えない.

続A.さらに冷静になって考える.O(|S|^3 * K^2)の区間DPがようやく見える.区間DPだと気付いた後の遷移のさせ方は単純なので迷わなかった.実装量はDPにしては多いと思ったが,そんなにバグる要素は無かったので落ち着いて実装.しかし答えを出力する部分で謎のbool値を出力する痛恨のミスを犯し10分ほど溶かす.死.82分ちょっとでAC.これ500ptsとは思えない.

C問題は考察しやすそうだったが,残り時間であの手の問題の実装をするのは無理だと判断し,順位表を見てBに着手する.問題設定からして「これ平方分割だよな〜」という感じの問題.いい感じの平方分割を思いついたと思ったが,実装を進めているとMLEしてしまうことに気づき無事死亡.MLE防ぐにはTLEする方法しか見えないしこれなんなんだーって言っていたらコンテストが終わった.

Acで19位.DDCCの順位も19位だったのでこの数には何かと縁がある模様.

解説

A問題の解説でchokudaiさんが「ここに居る人はこんなのサクッと通しましたよね〜」と18卒パワーで通った弱小コーダーを煽る.つらい.

B問題ついに逃げ続けてきたMo's Algorithmと向き合う日が来たのかと思った.ちゃんと勉強しようね.うん.

C問題は「なるほどね」って感じだった.コンテストが終わって実装したい感じの問題ではない.

D問題は読んで無いので解説もよくわからなかったが面白そうな雰囲気を感じたので後で解いておこうと思います.

表彰式

yutaka1999さんの名前が間違えられたのがハイライト

会社見学

社内を見せてもらえる機会があった.詳しくは書かないが,ドワンゴなるほどドワンゴという感じだった.

懇親会

タダ酒とタダ飯にありつく.人の金で飲み食いするのは楽しかった.

kobaさんやkimiyukiさんとお話しする.競プロな人とお話し.もるさんとお話ししたり,江添さんとお話ししたり,どわんごな人とお話し.

余興のぷよぷよ大会でchokudaiさんが優勝する.完全にプロ.ぷよぷよ大会の後 chokudaiさんを捕まえて,「A問題本当にあれ500ptsですか?」と聞いたところ「典型典型〜」とのこと.

あとケーキ


帰路

おひらきになったあと,ホテルまで戻る電車ではかみぺさんと一緒だった.Mo's algorithmのお話しとか「SRMのd1m埋めは効くぞ」という話しをしてもらう.「今日のA問題あれ500ptsじゃなくて800ptsぐらいあると思うんですけど」と言ったところ「800ptsも無くて多分600ptsぐらい.典型と言えば典型だし.」という意見をもらう.僕がDP苦手なだけだった.

その後,かみぺさんとお別れしホテルに戻りドワコン終了.

感想

コンテストは辛かったが,社内見学と懇親会は楽しかった.タダ飯はうまい.ドワコンのレベル的に自分が本戦に来れるとは思っていなかったので,本戦に出れたこと自体嬉しかった.