学習の栞

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

勝負しない競技プログラミング

twitterを眺めているとこういうことを書いたほうが良いのかなと思ったので書きます。いわゆるポエムで、内容は競わない競技プログラミングの楽しみ方です。

私はkonjoというハンドルでやっている週末競技プログラマです。最近はAtCoderのレート2000-2200くらいをふらふらしています。競技歴も5年を超えて、競技歴的にもレート的にも老人とか引退とか老害とかいう立ち位置が相応しくなってきたかなという頃です。競技プログラミングを「競技」として楽しんでいる人も多いのですが、私は競技プログラミングの「競技」という側面に惹かれて続けているというわけではないので、立ち位置を書き記しておこうと思います。

私が競技プログラミングを始めた頃というのは、AtCoderが始まって間もない頃で、AGCは勿論のことABCも無く、ARCの一桁台のコンテストが開催されている頃でした。当時、日本語競技プログラミングサイトと言えば会津大学が運営する Aizu Online Judge が第一に挙がりました。私もAOJから競技プログラミングに入門することになります。Aizu Online Judge では高校生向けのPCK、JOIや大学生向けのICPC、その他模擬コンテストなどがコンテストごとに100問単位で1つのVolumeとして纏められています。つまりVolumeの順序は問題の難易度とは無関係なので正答者数の降順に解いていく人も居るのですが、私はVolume0から順に問題を解いていこうとしました。

Volume0はPCKの問題が纏められているVolumeなのですが、昔の高校生向けコンテストということで頭を捻るような問題よりも実装を問う問題が多くなっています。当時、プログラミング自体の初心者だった私にとって、これを解くことは面白く、さらに問題に正解すると問題リストの横に正答済みのチェックマークが付き、いわゆる「プチプチ」を潰していくような快感がありました。高校生向けとはいえ、時代が進みPCKの決勝の最終問題などになると論文案件と表現されるような問題も登場するほど難しくなります。さすがにそのような問題になるとノーヒントでは解けないのですが、適度に難しい程度の問題であれば数日考えこめば解法が分かったりします。私にとっては競技プログラミングの問題はパズルのようなもので、解けないからといって解法を見て解いた時点で喜びが生まれるというものでもなかったので、難しくてすぐには解けなかった問題を数週間考えこんで解いたりしていました。AOJ埋めの過程で似非クラスカル法を発明して、その後クラスカル法の存在を知った日には自分の生まれた時代を悔いたものです。問題リストにチェックマークが付いていくのを眺める楽しさに加えて、機転を利かせてプログラムの効率を改善することの面白さに気付き、競技プログラミングにのめり込んで行くことになります。

その後、TopCoderやらICPCやらに出場して、「レートは命よりも重い」という一昔前の表現に代表されるような競技としての競技プログラミングにもそれなりに順応していくことになるわけです。競技としての競技プログラミングにもそれなりの面白さはあるのですが、やはり自分としてはパズルとしての面白さや、埋めるべきチェックリストとしての面白さのほうを強く感じるようです。

とはいえ、競技プログラミングのコンテストに出る以上多少の競技とは無縁では居られません。やはり高い順位を取れば興奮しますし、低い順位を取れば落ち込みます。しかし幸いにして多くの競技性の競技プログラミングサイトにはレートというシステムがあり、最近のパフォーマンスをある程度平均化して示してくれます。いくら競技に熱心ではないとはいえ、毎週末のコンテストに出続けていれば嫌でもレートは上がるものですから、競技としての成績で落ち込んだ時は年単位でのレートの増加を見て満足するようにしています。競技プログラミングの競技性に疲れを感じ始めている方の参考となれば幸いです。

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.