無矛盾な単位系

概要

  • 無向グラフが与えられるので、誤った閉路がないかどうか判定せよ。なお点は文字列として与えられる。

方法

  • まだ訪れていない点を調べる。
    • には深さ優先探索とありますが、実装が適切であれば幅優先探索でも大丈夫っぽいです。ただ、2倍ほど遅くなります。
    • memoに加えるのは、深さ優先探索では入れる時出す時のいずれでも良いですが、幅優先探索だと入れる時に加える必要があります。
    • 訪れていたら、最初に訪れた時の値と同じかどうか確認します。
  • なお、独立な単位系が複数存在するかもしれない(連結成分が1個ではないかもしれない)ので、グラフが空になるまで取り出し続ける実装にする必要がある。

  • コード(深さ優先探索と幅優先探索をベンチマークするためにdequeにしていますが、深さ優先探索だけで良いならvectorの方が速いです)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <string>
#include <cstdio>
#include <unordered_map>
#include <deque>
#include <algorithm>
using namespace std;
typedef string key;

char b1[99],b2[99];
void main2(int n){
  unordered_map<key,deque<pair<key,long long>>>m;
  for(;n;n--){
      int d;
      scanf(" 1 %s = 10^%d %s",b1,&d,b2);
      string s1=b1,s2=b2;
      m[s1].emplace_back(s2,d);
      m[s2].emplace_back(s1,-d);
  }
  for(;!m.empty();){
      auto s=m.begin()->first;
      deque<pair<key,long long>>st={ {s,0} };
      unordered_map<key,long long>memo={ {s,0} };
      for(;!st.empty();){
          auto p=*st.rbegin();st.pop_back();
          auto cur=p.first;long long d=p.second;
          for(auto &e:m[cur]){
              if(memo.find(e.first)==memo.end()){
                  st.emplace_back(e.first,d+e.second);
                  memo[e.first]=d+e.second;
              }else if(memo[e.first]!=d+e.second){
                  puts("No");
                  return;
              }
          }
      }
      for(auto &e:memo)m.erase(m.find(e.first));
  }
  puts("Yes");
}
int main(){int n;for(;~scanf("%d",&n)&&n;)main2(n);}

マス目と整数

  • 入力を変更し、連結成分重み判定を加えるだけで、マス目と整数の解答に変更することができる。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
--- utpc2010_10125(aizu2207)_stack.cpp    2016-10-13 04:19:40.000000000 +0900
+++ atcodercodefestival2016qualaD.cpp 2016-10-13 04:42:46.000000000 +0900
@@ -1,22 +1,22 @@
-#include <string>
 #include <cstdio>
 #include <unordered_map>
 #include <deque>
 #include <algorithm>
 using namespace std;
-typedef string key;
+typedef int key;

-char b1[99],b2[99];
-void main2(int n){
+int main(){
+  int r,c,n;
+  scanf("%d%d%d",&r,&c,&n);
  unordered_map<key,deque<pair<key,long long>>>m;
  for(;n;n--){
-      int d;
-      scanf(" 1 %s = 10^%d %s",b1,&d,b2);
-      string s1=b1,s2=b2;
-      m[s1].emplace_back(s2,d);
-      m[s2].emplace_back(s1,-d);
+      int s1,s2,d;
+      scanf("%d%d%d",&s1,&s2,&d);
+      m[s1].emplace_back(s2+r,d);
+      m[s2+r].emplace_back(s1,-d);
  }
  for(;!m.empty();){
+      long long a=-1LL<<61,b=1LL<<61;
      auto s=m.begin()->first;
      deque<pair<key,long long>>st={ {s,0} };
      unordered_map<key,long long>memo={ {s,0} };
@@ -29,12 +29,17 @@
                  memo[e.first]=d+e.second;
              }else if(memo[e.first]!=d+e.second){
                  puts("No");
-                  return;
+                  return 0;
              }
          }
+          if(cur<=r)a=max(a,d);
+          else b=min(b,d);
      }
+      if(a>b){
+          puts("No");
+          return 0;
+      }
      for(auto &e:memo)m.erase(m.find(e.first));
  }
  puts("Yes");
 }
-int main(){int n;for(;~scanf("%d",&n)&&n;)main2(n);}

あとがき

  • Code Festival 予選中、無矛盾な単位系が類似問題として頭に浮かんだのですが、当時書いていたコードが 一行入力するごとにグラフを全走査する くそコードだったため、どうしようもできませんでした。
  • 結果的には復習になってよかったです。
  • ただ、連結成分重み判定はやはり本番中に思いつかなかったと思います…

URL

結果

  • ---ox△△◎oo-oo△-ooo△△--△- 1752.66点で2位でした。

A:BonusMondai

  • 解いたらあかんやつやこれ
  • てか負の配点って設定できちゃだめやろ

B:NA RI KI RI knapsack

  • よくある問題だけど得点が謎。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <vector>
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
  int N,W;
  scanf("%d%d",&N,&W);
  vector<pair<int,long long>>v(N);
  for(int i=0;i<N;i++)scanf("%d%lld",&v[i].first,&v[i].second);
  vector<long long>bag(W+1);bag[0]=1;
  for(auto &e:v){
      for(int j=W;j>=e.first;j--){
          if(bag[j-e.first]&&bag[j]<bag[j-e.first]+e.second)bag[j]=bag[j-e.first]+e.second;
      }
  }
  printf("%lld\n",*max_element(bag.begin(),bag.end())-1);
}

C:Number Guessing Master

  • 8桁の数値の当該桁がヒットならACになるかと思ったけどそうでもなかった
  • 最初の4ケースがhit、後ろの4ケースがblowだそうです…

D:ポッポカウント(AC)

  • 素直に解いて良い。なおNの最大は100であるようだ。
1
2
3
4
5
6
7
#include <stdio.h>
int main(){
  long long N,i,j,R=0;
  scanf("%lld",&N);
  for(i=1;i<N;i++)for(j=i+1;j<=N;j++)R+=__builtin_popcountll(i*j);
  printf("%lld\n",R);
}

E:Hedgehog(TLE)

  • 入力拾うだけでTLEになる のでどうしたもんだろう。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <algorithm>
#include <cstdio>
using namespace std;
int main(){
  long long v[1000];
  long long R=0;
  int N,M;
  scanf("%d",&N);
  for(int i=0;i<N;i++){
      scanf("%d",&M);
      for(int j=0;j<M;j++)scanf("%lld",&v[j]);
      std::sort(v,v+M);
      for(int j=1;j<M;j++)R^=v[j]*j;
  }
  printf("%lld\n",R);
}

F:ライツアウト(部分点)

  • 5x5を反転させるのでは満点にならないらしい。サイズ、いくらなんだろう。
  • 解説読んだけどあれはひどい–;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
15
0 0
0 1
1 0
1 1
1 3
1 4
2 2
2 3
2 4
3 1
3 2
3 3
4 1
4 2
4 4

G:Surprising Language(部分点)

  • Perlで解いたものをBashに埋め込んで210/300点。300点は難読言語専用かな?
  • Whitespaceで解くと満点なの?テストケース埋め込みが必要やん…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/perl
use feature qw(say);
use strict;
my($x,$y)=split(/ /,<>);
my $M=10**9+7;
my @I=(1,1);
my @F=(1,1);
my @R=(1,1);
for(my $i=2;$i<=$x;$i++){
  my $z=($M-($M/$i^0))*$I[$M%$i]%$M;
  $I[$i]=$z;
  $F[$i]=$i*$F[-1]%$M;
  $R[$i]=$z*$R[-1]%$M;
}
say $F[$x]*$R[$x-$y]%$M*$R[$y]%$M;

H:OCR Killer(AC)

  • FAです。やった^ω^
  • http://kjjk.weblio.jp/ の手書きに頑張って書く。途中から疲れてiPadになった(twitter 自分宛DMでPCに転送)。タッチパネル最強^^
  • 問題文(一部おかしいけど、まあ。これでもGoogle翻訳結果見ながら手直しした方ですよ?)
1
2
3
4
5
6
7
8
9
10
11
달의 구면 상의 러리를 구하심시모
달의 구면 상의 점은 두 실수
(a,b) 로 주어진다 이건 지구의
"동겸a 도, 북왼 b도", 와 같다
서경, 남위는 음수를 사용 찬다
단, 이 몬세에서는 달을 위키백라
기사에 쓰이는 직경의 구라고
가정해야 찬다
(出力)
주머신 두 점의 거리를 츨력한다
오차는 적담히
  • 要約
  • 東経aと北緯bが2組入力される。月における2点間の距離を求めよ。月の半径はWikiにあるものを使え。

  • 答案

  • 北緯と東経が(慣習と)逆に入力されることにさえ注意すれば、難しくはない。
1
2
3
4
5
6
7
8
9
#!/usr/bin/python
import sys,math
def calcdist(a):
  lat1,lon1,lat2,lon2=map(lambda e:e*math.pi/180,a)
  return 3474.3/2*math.acos( (math.sin(lat1)*math.sin(lat2)+math.cos(lat1)*math.cos(lat2)*math.cos(lon1-lon2)) )

b1,a1=map(float,sys.stdin.readline().split())
b2,a2=map(float,sys.stdin.readline().split())
print(calcdist([a1,b1,a2,b2]))

I:雑な問題(AC)

  • piyo

J:雑な問題2(AC)

  • 問題IDが「the-answer-is-to2ange2an」である。
  • to2ange2an

K:Classical Cipher

  • もういいや
  • 鍵がT,Z,Nであることからエニグマだと思ったんですけどね、 ローターの選択とプラグボード配線もエニグマの鍵に含まれますよね??

  • 問題文

1
2
3
4
5
6
7
8
YOUAREGIVENASTRING
WRITEAPROGRAMTODECODETHESTRING
THESTRINGISENCODEDINFOLLOWINGWAY
FIRSTCONVERTEACHCHARACTERBYTHETABLE
THETABLEISGIVENRIGHTBELOW
KSYWQJDRZUIPGOLMXEBTVAFNHC
NEXTCHANGEKTHCHARACTERTOITSKTHNEXTALPHABET
FOREXAMPLEIFAFOURTHCHARACTERISYTHENCHANGEITTOC
  • 答案
1
2
#!/usr/bin/ruby
puts gets.chomp.bytes.map.with_index{|b,i|((b-65-i)%26+65).chr}.join.tr('KSYWQJDRZUIPGOLMXEBTVAFNHC','A-Z')

L:洞窟(AC)

  • Googleフォームを開いたらソースを開くと答えを見つけることができる。
  • SNUKEGORM_BY_DARUDE

M:Matryoshka(AC)

(1)

  • CPUに 10時間ほど 頑張って頂きました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#!/usr/bin/ruby
s=DATA.gets
314161.times{|i|p i
  s=IO.popen('php','r+b'){|io|
      io.puts s
      io.close_write
      io.read
  }
  puts s if i%1000==0
}
puts s
# <?printf($a=($b=0)?'<?printf($a=($b=%d)?%c%s%c:"%s-%s",$b-1,39,$a,39,dechex($x=%d),dechex($y=%d),$x+$x+$y,-$x);':"bf-cbc",$b-1,39,$a,39,dechex($x=3642),dechex($y=-191),$x+$x+$y,-$x);
# bf-cbc
__END__
<?printf($a='<?printf($a=($b=%d)?%c%s%c:"%s-%s",$b-1,39,$a,39,dechex($x=%d),dechex($y=%d),$x+$x+$y,-$x);',314159,39,$a,39,'','',-1084159067,1084162518);

(2)

  • こちらもCPUに10分ほど頑張って頂き、後半戦には入れたのですが、そこで死にました。
  • funzip、こういう目的には割と良いツール。
1
2
3
4
5
6
#!/usr/bin/ruby
loop{
  system("<data.zip funzip -bf-cbc >data.bin")
  break if File.binread('data.bin',2)!='PK'
  File.rename('data.bin','data.zip')
}
  • ヒントに助けられました。
1
2
3
4
5
6
7
8
9
10
#!/usr/bin/php
<?php
$s='';
for(;;){
  $stdin=trim(fgets(STDIN));
  if(!$stdin)break;
  $s.=$stdin;
}
for($i=0;$i<39;$i++)$s=openssl_decrypt($s,'bf-cbc','bf-cbc');
echo $s;

(3)

  • これもヒントに助けられました。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#!/usr/bin/ruby
require 'net/http'
s=''.dup
Net::HTTP.start('goo.gl'){|http|
  key='xFnLDH'
  location=''
  loop{
      resp=http.get('/'+key)
      h=Hash[*resp]
      break if !h.has_key?('location')
      location=h['location'][0]
      domain,key=location.split('/')[-2..-1]
      s<<domain.scan(/\d/).join
      sleep(1)
  }
  puts location
}
puts s.tr('10','ls')
  • Herbert Online Judgeに流し込む。

  • 答案

1
2
3
bf-cbc
xFnLDH
SHRIFT

N:Answer the Number(部分点)

  • (1)だけです
1
2
def f(n) r=1.0;(1..1/0.0).find{|i|(r=r*(n-i)/n)<=0.5}+1 end
p f(10000)

O:THE EMPTY

  • 問題文は透過pngになっているのですが、画像中の暗号を解読できず。
  • 0,6,8,9の輪っかでπを表現するとか…うーむ。
1
2
3
#!/usr/bin/ruby
s=Math::PI.to_s.tr('.','')
puts s[gets.to_i-1]

P:THE EMPTY 2(AC)

  • 解答言語としてWhitespaceを選択すると問題文が現れます。
1
2
3
4
#!/usr/bin/ruby
require 'prime'
a,b=`dd`.split.map(&:to_i)
p Prime.each(b).drop_while{|e|e<a}.size

Q:THE EMPTY 3(AC)

  • Download sample test casesすると、output00.txtに問題文があります。
1
2
3
4
5
6
#!/usr/bin/ruby
require 'prime'
class Integer
  def divisornum() self.prime_division.reduce(1){|s,(n,p)|s*(p+1)} end
end
p (gets.to_i**2).divisornum

R:正しいダジャレギュレーション(AC)

  • 落ち着いて問題文を読みましょう。sの種類数と同じ意味です(ただしsが1文字の場合は無効)。
1
2
3
4
5
6
7
#!/usr/bin/ruby
n,a=gets.split.map(&:to_i)
if n<2
  p 0
elsif
  p a**n%100000007
end

S:健康計算機(部分点)

  • こういう問題の相場として、複雑な字句解析ってのがあるんですが、どうにもならなかった感じがします。ぐぬぬ。
  • まじめ版の字句解析器が通らなかったのは「x'y」という入力のせいですかあーあーそこまで考えてなかったわ
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def bmi(kg,m)
  kg/m/m
end
a,b,c,d=gets.downcase.scan(/([\d'"\.]+)|([a-zA-Z]+)/).map{|e|e.compact[0]}
if a.scan(/\d/).empty?
  a,b=b,a
end
if c.scan(/\d/).empty?
  c,d=d,c
end
if b.end_with?('g')
  a,c=c,a
  b,d=d,b
end
a=a.to_f
a*=0.3048/12 if b=='in'
a*=0.3048 if b=='ft'
a*=0.9144 if b=='yd'
a*=1000 if b=='km'
a/=100 if b=='cm'
a/=1000 if b=='mm'
c=c.to_f
c*=1000 if d=='t'
c/=1000 if d=='g'
c/=1000000 if d=='mg'
c*=0.45359237 if d=='lb' || d=='lbs'
p bmi(c,a)

T:明日使えない英単語(部分点)

  • 知るかいな
  • 本番中は2,4に正解。
  • alopecoidという単語は「プログレッシブ英和・和英中辞典」「ウィズダム英和・和英辞典」「New Oxford American Dictionary」「Oxford Dictionary of English」のいずれにも載っていない単語ですよ
    • OSXの辞書ってこんなにくそでしたっけ(んなわけはない) ^ω^#
1
2
3
#!/usr/bin/ruby
T=%w(eaglet camaraderie oblast thesaurus alopecoid)
puts T[gets.to_i-1]

U:うんちくビ〜ム

  • 解説すら読めない。

V:Side Story of WolfHockeyTeamEasy/Hard

  • 問題、読めず。私の国語力も地に落ちたもの。
  • jpg埋め込みかよ
  • HOUSTON COSMONAUTS

W:Shiritori(部分点)

  • 知るかいな(2回目)
  • 本番中は1,2,3,4,5,7,8,9に正解できました。
  • ウルフサザ?なんですかそれGoogle検索結果0件なんですが…?「sothe」は不正解だしねぇ。
1
2
3
#!/usr/bin/ruby
T=%w(ke-ki ki kitune nezi zi ziyu-nomegami idou u uruhusaza huryoku kuku donou)
puts T[gets.to_i-1]

X:Please ignore.

  • 解いたらあかんやつ(2回目)
  • 先日iPad Air 9.3.2を脱獄してから久しぶりにいろいろ遊んでます。
  • ech0chrome iPhone Repo on Cydia (昔私がビルドしたソフト群)も一部使えました。ncompressとか(tar.Zとか今は使われてるんでしょうか…)
  • しかし、nkfやPuTTY、OpenHSPは「Illegal Instruction: 4」と出て動かない。
  • 少し調べたところ、http://theiostream.tumblr.com/post/63923259800/patching-iphone-gcc-binaries-to-armv7s に行き当たりました。ldr r3, [r3]命令がarmv6/v7専用命令になっていて、armv7sで解釈できないのが原因とのこと。armv7sで解釈できるように手直しすればよいそうです。crt1.oだけがおかしく、原因は不明とのこと。
#!/bin/sh
for file in "$@";do
sed -i'' 's/\x00\x30\x93\xe4/\x00\x30\x93\xe5/g;s/\x00\x30\xd3\xe4/\x00\x30\xd3\xe5/g;' $file
ldid -S $file
done
  • まあ、当時はiPhone 3GSやiPhone 4の時代だったので、v7sのことなんて頭になかったですからねぇ…
  • ビルドスクリプト、もしあったら、パッケージ化しようと思います。バックアップは今何処^^;(開発機のiPod Touch 3rdはヒューズが飛んだ状態)
  • てか、私の出してるiOS gccは間違いなく壊れたバイナリを出力するんですが、どうしたもんか。3.1.2用のtoolchainをセルフコンパイル用にポートしただけなので、新たにtoolchainを作る能力は私にはない^^;

  • ちなみに、Illegal Instruction: 4はこのパッチで直せますが、mmap error 22は直せません。

  • https://forums.developer.apple.com/thread/7524 によると、32bit dylibを読み込むにはMach-Oのヘッダがどうこうという話っぽいです。

  • 話は変わりますが、アプリ領域にアクセスするのが不便なのでapplinkなるソフトを作ってましたが、これもiOS8で使えなくなってた模様。com.apple.mobile.installation.plistがなくなったため。
  • 突貫工事で新たに作りました。Pythonが必要ではありますが。しかもリンク名がアプリ識別子になる制限付き。
  • https://gist.github.com/cielavenir/089ae47301458db8e2e04a67f72132b3

http://abc042.contest.atcoder.jp/tasks/arc058_a http://arc058.contest.atcoder.jp/tasks/arc058_a

概要

  • N以上の数値で、与えられた数字を使わずに作れる最小のものを答える。

高速解法

  • 使って良い数字の集合(入力の補集合)Aを求めておく。
  • まず、与えられた数値の文字列表記Sの前から後ろに向かって、使って良い数字以外が含まれる桁jを求める。
    • もし見つからないなら、Sを出力して終了する。
  • 桁jから前側に向かって、Siよりも大きい数字がAに含まれるような桁kを求める。見つからなければ-1とする。
    • 大きい数字がAに含まれるとは、繰り上がりを受け切れるという意味である。
  • kが-1ならばAの先頭(ただし先頭が0ならば次の要素)を出力。0以上ならばSの先頭からk文字とSkよりも大きい数字のうち最小のものを出力。
  • Aの先頭要素を(Sの文字数-k-1)だけつなげて出力。
    • kを-1にしておくとこの部分での場合分けが不要になるというわけ。
  • 2回Sを走査するので、計算量はO(S)あるいはO(logN)となる。

まとめ

  • 土曜日、帰宅後に問題ページを開いて最初に思いついた解法がこれです。O(NlogN)解法の方が明らかに実装が楽なので、コンテストとしては負け。
  • 復習コンテストのストックにしなかったのは、テストデータ作成が面倒だったからです。

http://abc042.contest.atcoder.jp/submissions/818591

  • 1/3、何を思ったか研究室から貸与されたiPadにインストール。まあ、共有物ではないし…
  • ULC、面白いシステムだと思う。(最後までプレイすることで完了させられるようになったのは最近らしいけど、それを差し置けば)難しい譜面も繰り返しプレイすることでクリアできるようになる点は良い。
  • 節分キャンペーンを進める。所持していない楽曲はフレンド募集スレッドからプレイさせていただくことを学習する。シェアソングはソーシャル要素の答えの1つだと思った。
  • 1/15、Break down獲得(RP600突破)。しかし、節分キャンペーンを進めた結果、同時期開催の個人戦報酬を落とす。まあ、ソシャゲを始めた時のイベント報酬が厳しいのと近いので、しかたがない。個人戦の課題曲が全て未所持であることも理由。
  • ランダムセレクト祭。ランダム選曲すると過去の曲が常駐するかもしれないというイベント。とりあえずフルコンボ譜面を増やす。
  • 1/24、Azitate獲得。条件は難しい難易度であるMASTER譜面をULTIMATEで5曲クリアということで、当時はかなりきつい条件だった。ランダムセレクト祭で引き当てたEternallyが5曲目だった。
  • 期間限定RP曲、未確認XX生命体を購入すれば5曲とも所持することになるので、購入。結果、2/8、RP1000突破。NEXT FRONTIER獲得。簡単な難易度であるSTANDARD譜面の難易度値がかなり高いんですが、慣れれば自然と指が動く面白い譜面。
  • 2/17、RP1100突破。期間限定RP曲+上位20曲のため、いろいろ埋めないと上がらない。あと、Lobi入れた。
  • 2/18、バレンタインキャンペーン完走。きつかったのがMake It Fresh HARDフルゲージと最後の1ページ MASTER Sランク。まあ、クリア出来てよかった(節分キャンペーンリバイバルの最後の報酬を諦めた理由がMASTERフルゲージで、それよりは簡単ですし…)。
  • 2/28、RP1200突破。Touch of Goldと雨の音が虹を呼ぶでMASTER ULTできたのが大きい。
  • 3/1、期間限定RP曲のうち4曲しか所持していないため、RP1200を割る。
  • この進行がハイペースかどうかを訊くのは愚問とのこと。落ち着いて考えればそうなのですが…。ごめんなさい。
  • まあ、個人個人自由に楽しむのが第一ですよね。
  • あとは、アンロックゲージが溜まったからといってすぐにアンロックチャレンジを開始すべきかという質問も愚問のよう。チケットの消費に慎重な人もいるかもしれないので。
  • CROSS X BEATSを始めて2ヶ月、42曲となりました。(RP以外の)ミッション曲を全部回収したこともあり、今後曲がどんどん増えていくということはないでしょう。
  • というわけで、時系列でまとめておきます。
  • 緑鍵
  • 黄鍵
  • 祭曲をラ祭以外の方法で入手
曲数 日時 取得楽曲
10 1 / 3 Wanna Be Your Special / Touch Of Gold / 雨の音が虹を呼ぶ / DIAMOND SKIN / Wasteland
When You Call My Name / キミとMUSIC / Aqualight / Wanyo Wanyo / Lotus Love
13 1 / 5 Loveless / Landing on the moon / Jahacid
16 1 / 6 Freak With Me / ホントのワタシ / Dirty Mouth
18 1 / 8 Hi / Binary Overdrive
19 1 / 9 Anomie
20 1 / 12 Otherside
21 1 / 13 What is Wrong With The World
23 1 / 15 Break down / エアリアル
24 1 / 20 DAZZLING♡SEASON
25 1 / 22 Eternally
26 1 / 23 Giant Killing
28 1 / 24 Azitate / Cross + Angel
29 1 / 26 everKrack
30 1 / 28 Winter, again
31 2 / 7 未確認XX生命体
32 2 / 8 NEXT FRONTIER
33 2 / 11 The Epic
34 2 / 14 How True Is Your Love
36 2 / 15 nightmares / default affinity
37 2 / 19 JUSTICE from GUILTY
38 2 / 20 Re:Milky way
41 2 / 21 エール / 誘惑 / オーバーラップ
42 2 / 22 Nu Heat
44 3 / 10 BASS ANTICS / Doki Blaster
45 3 / 12 BRAND NEW
46 3 / 22 最後の1ページ
48 4 / 8 boule de berlin / cloudstepping
50 4 / 9 残響のアカーシャ / Impact
51 4 / 11 the Last Missile Man
53 4 / 23 光年 / Human Nature
55 5 / 5 Azitate (Prologue Edition) / Touch Of Gold (Bongo Mango Remix)
56 5 / 6 HEADPHONE PARTY
58 5 / 10 イルミナレガロ / Deep Outside
60 5 / 23 Harmony / Flame Up
61 5 / 27 ツカイステ・デッドワールド
62 5 / 28 最終回STORY
63 5 / 29 Landing on the moon (Inst)
64 6 / 1 Into the Cave
65 6 / 6 Wonderful
67 6 / 16 Indigo Isle / Free
78 6 / 21 killy killy JOKER / 海色 / 白鳥の湖 / トルコ行進曲 / イジメダメゼッタイ
Hopes Bright / いいね! / Flowerwall / ギミチョコ / サバイバル
ヘドバンギャー
80 6 / 24 Sunny day / Vespero
81 6 / 28 Anomie (Axiom Style)
82 6 / 29 NEXT FRONTIER -TRUE RISE-
83 7 / 4 Murasame
85 7 / 5 ソンザイキョウドウタイ / 妄想全開
86 7 / 8 tokyo
88 7 / 21 Bi-Zon Zon Zombi (More) / 光年 Remix
91 7 / 22 Reseed / メギツネ / Dreaming Girl
97 7 / 23 Make It Fresh / 逆転裁判 / Raise Your Handz / チルドレン・オートマトン / Designed World
What is Wrong With The World (Cross)
98 7 / 24 Sundrop (Remix)
101 7 / 25 RIDE ON NOW / ロマンシングゲーム / ロックマン
103 7 / 26 MERCURY / some day (instrumental)
105 7 / 27 Voice Of House / Z[i]
106 7 / 29 戦国BASARA
107 7 / 30 Virtual Reality Controller
109 7 / 31 ピコラセテ (Inst) / Sapphire
110 8 / 2 Reuniverse
111 8 / 5 VOHリミ
113 8 / 17 Always Thinkg Of You / Machine
114 8 / 18 Timeless encode
115 8 / 20 Moonrise
116 8 / 21 OKOKUNIKOD
117 8 / 23 ホコロビシロガールズ
118 8 / 28 Wanna Be Your Special (Remix)
121 9 / 10 ストレンジ・ディーヴァ / Don’t Walk Away / All U Need
132 9 / 13 シュガーソングとビターステップ / Inner Urge / D.O.B. / ViViD / unfinished
Break a spell / メモリーズ / WE GO / X-encounter / Light My Fire
show
140 9 / 16 電脳少女 / I.D. / Sundrop / some day see you again / 甘い言葉
Driving story / 覚醒awake / NIGHT FEELIN
143 9 / 17 大殺界 / 現実幻覚スピードスター / サマ★ラブ /
145 9 / 18 Addicted / Break Your World
150 9 / 19 Aqualight (Remix) / 魔界村 / ピコラセテ / Reanimation / Omniverse
153 9 / 20 CrossShooter / Rebellion / Underworld
154 9 / 21 SUNDAY リベンジ
155 9 / 22 DREAMIN' OF YOU
157 10 / 8 Assign / Flame Up (Remix)
159 10 / 19 FUNKYBABY EVOLUTION / SuperLuminalGirl Rebirth
160 10 / 24 Bi-Zon Zon Zombi
162 11 / 10 Burning Inside / Resonance
163 11 / 12 BUZZ Ketos
164 11 / 14 DYNAMITE SENSATION
165 11 / 19 Break down (2nd Edition)
166 11 / 20 ASTAROTH
167 11 / 21 Another Chance
168 11 / 23 Hisui
169 11 / 24 Designed World (Remix)
170 11 / 28 Crystal Ribbon
172 11 / 29 Soda Machine / Grand Arc (Club Remix)
174 12 / 7 Interstellar Plazma / Sangeyasya
175 12 / 21 フォルテシモ
177 12 / 25 Metro Night / ULTRiX
178 1 / 13 Filament Flow
179 1 / 14 The Epic Introduction
180 1 / 23 DAZZLING♡SEASON Darwin Remix
181 1 / 24 EverWhite
182 1 / 26 Isinglass
183 1 / 27 GARNET HOWL
185 1 / 28 starting station / SPLASH
186 2 / 16 Faraway
187 2 / 26 Perfectionism
188 3 / 14 only L
189 3 / 29 Take It Back
191 4 / 26 Chip Notch Educ@tion / ネコふんじゃった
192 4 / 28 STARDUST
193 4 / 29 Over The Blue
194 5 / 8 Frgmnts
196 5 / 19 Adverse Effect / Planet Calling
200 5 / 25 流星デモクラシー / South wind / The Blade Master / たゆたい
201 5 / 26 IONIZATION
203 6 / 13 Milky Way Trip / Cash
207 6 / 26 Epiphany of Hardcore / Grand Arc / Ariel / Phoenix
208 6 / 30 KING STUN
212 7 / 16 HDM / Pyromania / 最終列車 / 星達のメロディ
217 7 / 27 YUKARI / Days / 勇敢 i tout / Code Paradiso / FarthestEnd
218 7 / 28 Curse of Doll
219 8 / 5 Into the Cave Another
220 8 / 8 Come Around
221 8 / 10 Silbury Sign
223 8 / 22 カウンターストップ / 未来へのプレリュード
224 8 / 24 Silverd
225 8 / 28 Sempai Slam
228 9 / 1 S.T.E / Orbital Velocity / Regeneration ray
230 9 / 4 kaminoko / Hypersphere
232 9 / 15 君と野獣 / アジテーター
234 9 / 20 Life In A Video Game / Lose Your Mind
236 9 / 22 Never Sleep Again / 彼女のModern
237 9 / 28 Distantmemory
239 10 / 10 Hallucination XXX / BRAVE
243 10 / 13 14th Clock / Hervor / Dark Parashu / Nu Era
  • 月別獲得数
  • 30,12,4,7,10,19,27,9,37,5,12,5
  • 8,2,2,5,8,7,10,7,12,

http://abc032.contest.atcoder.jp/tasks/abc032_b

概要

  • sからk文字取り出して、その部分文字列を連想配列に突っ込んで、重複しない数を答える。

高速解法

  • ローリングハッシュを生成する。ローリングハッシュには、hash[a:c] = (hash[a:b]*B**(c-b) + hash[b:c]) % Pという性質がある。
  • 今回はhash[i:i+k]が得られれば良いので、この式をhash[b:c] = ...と変形すれば良い。
  • 部分ハッシュを得るのは、B**(c-b)を事前に計算しておくことでO(1)とできる。
  • また、連想配列がハッシュテーブルならば重複判定もO(1)なので、トータルでO(s)となる。
  • http://abc032.contest.atcoder.jp/submissions/608838
    • ※C++98互換のためunordered_setではなくsetを使っているためこの実装はO(slogs)

まとめ

  • 今回の制約では全くの無駄ですので、解法は賢く選びましょう。
  • なぜyukicoder復習コンテストのストックにしなかったし。提出後に気づいたので後の祭り。
  • P,Qがどちらも0の場合はX==0とY==0だけを数えます。
  • 簡単のため、P,Qの最大公約数を単位とする座標系に変換します。X,Yが変換できなければ弾きます。
  • ここで、各方向に進む回数をa,b,c,dと置くと、
1
2
(a+b)P+(c+d)Q==X - (1)
(c-d)P+(a-b)Q==Y - (2)
  • となります。
  • α=a+b、β=c+dとおきます。
  • αP+βQ==1を満たす(α,β)を拡張ユークリッド互除法で求めます。
    • 代表値を(z1,z2)とすると、式(1)を満たすのは、α=z1X+Qn、β=z2X-Pnとなります。
  • 式(2)を(β-2d)P+(α-2b)Q==Yと変形し、αとβを代入して、整理します。2*P*d+2*Q*b==(Q*Q-P*P)*n+z2*X*P+z1*X*Q-Yとなります。
  • この不定方程式において、 整数解(d,b)を持つようなnが存在する ことが問題が求める条件となります。
    • ここで、上で媒介変数表示により変数を一個減らしたことが効いてきます。
  • (Q*Q-P*P)*n+z2*X*P+z1*X*Q-Ygcd(2*P,2*Q)の倍数であることが条件ですので、-(z2*X*P+z1*X*Q-Y)%gcd(Q*Q-P*P,gcd(2*P,2*Q))==0を判定します。
  • なお、このnを用いてd,bを拡張ユークリッド互除法から求めることで、a,cも求まりますので、原点から何回で目標に到達するかを実際に計算することも可能です。
    • プログラムにおいてeとfが可変。abs(a)+abs(b)+abs©+abs(d)が最小となるようなe,fを求めるのもまた一興かと(やってませんが)。

http://yukicoder.me/submissions/65751

参加記、書く予定なかったけど、私のことがコンテストレポートに載る可能性が濃厚なので、書くことにする。

  • CodeIQパーカー。Code Festivalでパーカー獲得が叶ったので、今日も願掛けです。
  • orisano氏とjmc.miz-miz.bizの話とか(jmc、A問題であふあふなんですが…)。kcs/koj復活お願いします(開発頑張ってください)。
    • てか、yukicoderもkojも、Docker-Builder部分は公開してはどうでしょうか。
    • セキュリティの問題があるので公開はあれですが、問い合わせは可とするのは。どうしてもサイトを作りたい人には、みたく。
時間 コメント
0:00 問題のリンクが違う、昨年に続き。大丈夫ですか。 game.coderunner.jpは開いたので、一番上に書いてあるAPIを叩きまくって負債を抱える大事故。 問題読まないの、絶対ダメ。
0:25 正の得点が取れるプログラムを書くことができた。 仕事を請けて、全割当。納期に収まるかどうかとか考えてません。 コメント変更「今回、今までの全6問で初の、誰でも正の点数を取れるわけではない問題。」
0:40 点数の推移がおかしいのが注目されたらしく、インタビューを受けることに。実はこの時点でほぼ万策尽きていたので、考え中というのは半分取り繕い。ただ、得点が半分になるルールをこの時知った(0:30の時点で負債が半分になっていた)ので、ラッキーでした。 でも…解説放送聞きたかったなぁ。
1:30 仕事量と報酬から計算される仮想乱数値が75以上(外注元の利益を考え80にはしてない。ただ、これ以上下げると安請け合いと判断した)、仕事量が1250以上(報酬は2乗で計算されるため)、得意な仕事(仕事Xに対する全社員の速度の和が90以上)について、外注から請ける処理を実装した。
2:10 0:50〜1:40まで10位をキープしていたが、この辺りで20位ほどに。コメント変更「 闘え、堕ちるまで。
3:00 論文を読みながら過ごし、終了。33位。
  • 10位以内のパーカーはないんですね。願掛けはあくまでパーカーに対するものと考えれば前提が(略)
  • 懇親会、時間中に3ブースかつ先着でトートバッグとかいろいろひどくないですか。
    • 私は特別に頂けましたが。kenkoooo氏からもらったようなものなので、使うことにします。。
  • 食事はあまり摂れませんでした。昼食のサンドイッチを食べたのがコンテスト開始後2時間だったので、まあよかった(サンドイッチ食べたの遅すぎたかなと心配していましたが杞憂に終わった(よくない))。

  • 帰り、レジャーランドでmusecaやった。となりにsnuke氏がいた。対戦とかはしてませんが。twitterで募集かけてればまた違ったかも。そういえばmusecaって現在は対戦機能ないんだった。

  • そういえばインタビューでシエルについて訊かれたんだっけ。スカイガンナー、機会があったらやってみてください。キャラは可愛いのにゲーム内容がかなりガチだったりするので^^;

http://yukicoder.me/problems/896

  • まず、union-findで島の大きさを列挙し、その列挙されたものに対し、bag[0]=-1として、最小値版0-1ナップザックを行えばよいです。
  • しかし、これでは、島の個数をXとすると、O(NX)であり、Xの最大値はNなので、島が多数あった場合に最悪O(N2)となり、TLEになってしまいます。
  • そこで、ダブリングを行います。例えば、大きさ2の島が10個ある場合、「大きさ2コスト1」を10回並べるのではなく、「大きさ2コスト1」「大きさ4コスト2」「大きさ8コスト4」「大きさ6コスト3」の4つを並べれば良いことになります。

    • 最後の3は10-1-2-4のように求められます。
  • http://yukicoder.me/submissions/64709

  • この考え方はtails氏の答案( http://yukicoder.me/submissions/64600 )を参考にしました。ありがとうございます。

追伸

  • 蟻本302ページに普通に書いてありました。まだ読み終わっていないため、勉強不足ということが露呈しました…
  • deque解法が多いのはスライド最小値の考え方で解けるかららしいですね。ダブリング解法は(計算量が少し増えることもあって)少数派のようです。