学習の栞

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

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苦手なだけだった.

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

感想

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

DDCC2016参加記

要約

切る削る磨くのコンテストで19位でした.

予選

A,Bやるだけ.Cは大根2に出といて助かったなという感じだった.Dはマージテクを疑いつつも解けず.18卒パワーで予選通過した.

本戦

コンテスト

配点を確認してできて3完だなーと思う.席が自由席で近くにヘクトさんゆらふなさんしょらーさんが居たので雑談してた.

A問題はやるだけだったのでやる.

B問題は冷静になって考えると,貪欲で良いことが分かるので貪欲にやると通った.27分でAC.

C問題はさすが700ptsという感じだったが,落ち着いて考察を詰めると普通に探索でとけるのでまあ700pts.61分でAC.

D問題は途中まで貪欲で詳細をDPで詰めるタイプの問題だなーと思ったのでそういう考察を詰めて実装したがWAだった.考察の方針は合ってそうだがよくわからん.

DDCC特別ビュッフェ

Discoの飯は旨い.高そうなご飯が並んでいた.チョコレートフォンデュを食べたり,t9qmib各位とお話ししたり,その他18卒の知り合いとお話ししていた.
さてさんを闇討ちするため「ドーモ,サテサン.コンジョウデス.」と挨拶する.結局闇討ちには失敗した.

厚切り.json

厚切りジェイソン氏の講演があった.芸人としての講演ではなく,IT企業役員としての講演だった.

会社見学

福利厚生施設すごい.あと,B問題の答え合わせ(物理)がDisco社によって行われた.

懇親会

1回のコンテストで2回も旨い飯が食べられるとは思ってなかった.お酒も出た.あとケーキ.

懇親会にて順位表の凍結が解除され,表彰式が行われるなどする.順位表凍結前にantaさんが全完して1位を確定させていたので完全に茶番.最終結果19位でした.

らて君やasiさんと初対面するなどする.中二双子やまるーんさんも居たが,声をかける勇気なし.らて君が久留米の人でよかった.多少声がかけやすかった.

感想

Disco含めプロコンを開いてくれる企業は良い企業です.最終結果19位はなかなかパフォーマンス出ていたと思う.ratedでなかったのが残念.コンテストの成績はまあ良いほうだったし,ご飯は美味しいしで大満足でした.

参加者の皆様,スタッフの皆様,ありがとうございました.

CODE FESTIVAL 2016 参加記

予選

予選A

インターン中だったので,インターンの滞在先から出ていた.早解きしてどうにか通過できた.10分前後で勝負が決まってしまうのってどうなの...理想を言えば予選Aでは800ptsが解けるかどうかぐらいが通過ラインになって欲しいんだけどな...

予選B

予選B通過できなかった.

予選C

予選C通過できなかった.

本戦

0日目

昨年,当日に福岡出発だと間に合わないということが実測で分かっていたので今年は前泊を申請.前泊が認められ確率統計のテストが終わった(オワタ)後東京へ飛んだ.B787に乗ってみようと思って便を取っていたのだが機材変更でB777になった.1WA.


東京に到着し,ホテルへ向かう.
京急線から大江戸線へ乗り入れている電車に乗ったのだけど「会社違うんだから当然乗り換えやろ〜〜」と言って電車を降りてしまう.同じ電車でよかったことはその電車が出発した後で気づきました.2WA.

大江戸線人形町駅日本橋駅を間違えて降りる.3WA.
東京の終電って恐ろしいですね.文字通りすし詰めで体が当たるとか荷物引っかかって人の迷惑とかそんなこと考えてたら電車から降りることができないなんて.

そうして人形町駅を降りて宿泊先のホテルへ.



宿泊先のホテルをGoogleさん勘違いしてる4WA.ちなみに,4WA目にはペナルティとしてタクシー代が1200円つきました.電車終わってたし仕方なし.

さすがにタクシーがホテルの場所を間違えることはなかった.無事にホテル到着.

1日目

本戦

105位.Ω\ζ゜)チーン

A-Dまでは割とすんなり溶けたがEが難しかった.難しかったけどパーカーがかかっていたので Convex hull で殴りにいってパーカーを獲得した.暴力的に得点を取ってしまったので反省.

tourist トーク

7歳から始める競技プログラミング
英語力が低いので内容の理解は通訳任せ.プログラミング用語含めて訳していて本業の通訳の恐るべく実力を知った.

山本一成さん講演

山本さん「みんなご飯食べてきなよ.なくなっちゃうよ.」
との計らいで開始が15分ずれ込む.寿司・肉・ピザおいしかったです.山本さんが「みんなkaggleやろうよ.なんでやってないの.」と発言したことによりTODOにkaggleが積まれた.

書道コーディング

「数弱黄色」と書いておいた.

エキシビジョン

国内プロ,海外プロ,indeedプロが3人で組んでICPC形式のエキシビジョン.海外のプロ集団の優勝不可避だと思っていた.まさかの2/3チーム0完でindeedチームの勝ちという番狂わせが起こる.たしかにindeedチームのメンバー真っ赤だけどさ,海外チームはtarget2人ですよ......完全にプロ企業.

飲み会

ホテルにチェックインしようとするとロビーでツカサさんにやざてんさんにうどんさんにほかにも知ってる競技勢と会う.みんなでお酒飲みに行こうという話をしていたところらしく,集団に加わりお酒を飲みに行った.お酒を飲みに行こうとしたところ,ホテルのロビーでtuboさんに会いさらに人数が増える.うちの大学は来年ICPCがどうとか,コンパイルコンパイラがどうとかで盛り上がった.翌日の朝プロで全滅しないように気をつけないとねなどと冗談もとぶ.

2日目

会場まで

会場まで歩いているとバタ子さんと合う.「本戦F問題1000ptsも無いですよ.さっさと解きましょ.」と煽られる.(後日解いたけど確かに1000ptsもなさそう)

トーナメント

asa!

今年はレベル別に30分,30分,40分のコンテスト3本でトーナメントをやるらしい.

トーナメント1回戦
0完.満点解が見えたので取りに行ったら実装が間に合わなかった.MSTとLCAを使う結構重めの実装だったのに満点を狙いに行ったのがだめだったらしい.

トーナメント2回戦オープン
部分点だけ.普通にDPすればよかったらしいが,DPの方針を間違えてて死.やっぱり自分は青なのだなあ.

トーナメント3回戦オープン
1完!.やったね.ついに1完できたよ.スライド最小値を実装したことはなかったのだけど,hadroriさんの書いた記事を見ながら実装したらどうにかなった.しかし,3回戦が40分だったので救われたというところがあって辛い.

お昼ご飯

あまり見ない鳥の肉のお弁当を食べた(雉?鴨?どっちだっけ).鶏肉とそんなに歯ごたえは変わらない.

体力測定

前屈をしたら腹筋を攣った.あとは右利きのはずなのに左手の方が10kg握力が強かったりとか.

りんごさんクイズ

例によって例のごとくあのノリで競プロのプロたちにクイズを出していた.地図を使ったゲームで「これ自明に勝てる手が存在するんですけど」とか言われていたのが面白かった.

リレー

gcdやるだけ問題の担当だった.
リレーにて,よすぽさんは天才ということを再確認した.

感想

こどふぇはやはりこどふぇだった.今年も面白かった.

参加者の皆様,スタッフの皆様,ありがとうございました.