Tozangezanお誕生日コンテスト

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回目)