ごりちゃんがゆく

競プロをするゴリラの精進記録

CODE FESTIVAL 2017 qual B

結果

A,Bの2完。タイム06:25。549位。
パフォーマンス1598、レート1259→1303(+44)

C,D問題、むずかった。。
そして全然できなかったのにレート上がっちゃった。
少し腑に落ちないと思ったけど、結局どちらも自力でできる内容じゃなかったので、ある意味実力通りか。
どうやったら、あの問題から、2部グラフなんて思いつくようになるんだろう。。。
というか、2部グラフってものは蟻本でさらっと出てきただけで存在を忘れてたし、使ったこともなかった。
次は絶対に解けるようにしとこう。

A XXFESTIVAL

A: XXFESTIVAL - CODE FESTIVAL 2017 qual B | AtCoder

末尾の8文字を除いてprint。

S = input()
print(S[:-8])

B Problem Set

B: Problem Set - CODE FESTIVAL 2017 qual B | AtCoder

N問の問題セットがあって、その中にM問の指定された難易度の問題が含まれているか。
以下、私の回答

import sys
from collections import Counter
 
N = int(input())
s1 = list(map(int,input().split()))
M = int(input())
s2 = list(map(int,input().split()))
 
c1 = Counter(s1)
c2 = Counter(s2)
 
for k,v in c2.items():
    if k in c1:
        if v > c1[k]:
            print('NO')
            sys.exit()
    else:
        print('NO')
        sys.exit()
print('YES')

pythonCounterモジュールを使った。(個人的によく使う)
l = [10,20,30,20] みたいなリストを、Counter(l)とかやると、
{10:1, 20:2, 30:1} みたいなdict型に集計してくれるすごいやつ。
key:valueのうち、keyの方がもともとの要素で、valueの方が集計した個数。(たまに、どっちか混乱する。)

c2.items() でM問の必要な方をループして、N問の用意してある問題セットに1つもないか、問題セットが足りなければNOを出力。
ループが最後まで行けばYESを出力。
こんな感じでしたー。

DISCO presents ディスカバリーチャンネル コードコンテスト 2017 予選

概要

2019卒枠が100人と、その他の100人が本戦に進めるコンテスト。
本戦の告知(DDCC | ディスカバリーチャンネル)を見たら、イベントがすごく豪華。
特に対談のメンバーがすごい。皆憧れの人ばかり。
(将棋界と将棋プログラムのトピックは、ここ何年か、個人的に追いかけているので)
厳しいだろうけど、何としても本戦出たい!って思いで参加しました。

結果

A,B,C の3完。タイム10:20。222位。
C問題までは自分的にベストなパフォーマンスだった。
D問題は1submitしたけど、考察力が足りずWA+TLE。
その他枠の人、100人ぐらい辞退してくれないかな〜??。。
まあ、そんな訳ないので、来年までに力をつけてリベンジするか。。

A,B問題

特に難しいポイントがないので省略。
ダースの12倍がグロス、その12倍がグレートグロスという単位があるのを初めて知った。

以下、 私の回答
A - DDCC型文字列
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656175

B 鉛筆
http://ddcc2017-qual.contest.atcoder.jp/submissions/1656644

C 収納

C: 収納 - DISCO presents ディスカバリーチャンネル コードコンテスト2017 予選 | AtCoder

N <= 100000 本の棒があって、長さCのケースに収納していくとき、ケースの最小数を求める。
ケースには1本か2本入れられて、2本入れる場合は[2本の和 + 1]の長さが必要。

以下、私の回答

N,C = map(int,input().split())
src = [int(input()) for i in range(N)]
src.sort()
 
l = 0
r = N-1
ans = 0
while l <= r:
    if src[l] + src[r] + 1 <= C:
        l += 1
    ans += 1
    r -= 1
print(ans)

ソートして左右から貪欲でいけた。
一番長いのを一番短いのと一緒に詰めることができれば、2本しまう。
そうでなければ、一番長いのを1本しまう。

例として、入力例1の C=10, L=[2,8,4,5]の場合。

  • ソートする。L=[2,4,5,8]
  • 2+8+1 > 10 で、8は単独で入れるしかないので、8をしまう。ans=1, L=[2,4,5]
  • 2+5+1 <= 10で、2と5が両方入るので、両方しまう。ans=2, L=[4]
  • 最後に4をしまう。ans=3

こんな感じ。

実際は、lとrの2つのインデックスを操作すれば、配列の要素を消すことなく、シミュレーションできる!
計算量は、

  • ソートにO(NlogN)
  • 貪欲なシミュレーションがO(N)

O(NlogN) なので大丈夫!

最後にちょっと脱線

このブログについて、本当は勉強したことをまとめていって自分用のノートにするつもりだったけど、気づいたら競プロの参加記になってた件。

まとめたいネタはいくつかあるんだけど、どうも、人が見て分かるような体裁にまとめるのが苦手というか、意外と骨が折れることが分かった。
記事にまとめるのより、過去問にチャレンジした方が楽しい ^^;。

まあ、無理せず、自分のペースでやればいっか。

Kyoto University Programming Contest 2017

結果

A,B の2完。タイム08:06。165位。
初の5時間越えのコンテストに参加するので、お菓子に飲み物と万全の体制で臨んだ。
なのに、C問題以降が難しすぎて、早々にダレてしまった。
これだけ時間があったら、せめてC問題は解きたかった...。
おのれ、京都大学ぅ〜。
後で解説きたら勉強させてもらおう...。


A Credits

A: Credits - Kyoto University Programming Contest 2017 | AtCoder

できるだけ少ない科目数で必要単位を取る場合の科目数を答える問題。

需要あるか分からないけど、コードペタペタしていく。

N,K = map(int,input().split())
src = list(map(int,input().split()))
src.sort(reverse=True)
ans = c = 0
for i in range(N):
    c += src[i]
    ans += 1
    if c >= K:
        print(ans)
        break
else:
    print(-1)

降順にソートして、貪欲に単位数を足していって、必要単位Kに達したらbreak。
全部足してもKに達しなかったら、-1。
Nは50までなので、計算量も余裕。


B Camphor Tree

B: Camphor Tree - Kyoto University Programming Contest 2017 | AtCoder

完全二分木の形のくすのきがあって、ある分岐Sからある分岐Tに登れるか。 登れる場合は距離を出力。登れない場合は-1。

N,S,T = map(int,input().split())
 
n = T
ans = 0
while(n >= S):
    if n == S:
        print(ans)
        break
    ans += 1
    n //= 2
else:
    print(-1)

完全二分木の性質を知っていれば楽勝でした。
2で割れば、1つ親のノードに行けるので、Sを2で割っていってTにたどり着けるかどうか。
木の高さN=25なので、計算量も余裕。

天下一プログラマーコンテスト2017

結果

C,Dの2完。タイム85:20、264位。
レート上がる気がしたけど、Unratedの模様。
まあ、楽しかったので気にしない。

C: 4/N

C: 4/N - Tenka1 Programmer Contest | AtCoder

4⁄N = 1⁄h + 1⁄n + 1⁄w
式を満たす正整数h, n, w を求めよ、って問題。 (h, n, wって何の意味だろう...)


h,n,w <= 3500 を満たす解が存在するとのことだけど、
組み合わせを全部試すのはO(M3)でもちろん無理。M=3500。

よく考えたら3つの変数のうち2つが決まれば、残り1つが計算で求まるので、
ループするのは2つでおk。
求めた結果が正の整数だったらそれが答え。

M2 だと107 ループ位だから、イケる、、
いや、Pythonだと非常に際どいなー。どうかなー。
と思いながらも、下のようなコードを書いた。

import sys
N = int(input())

def is_int(a):
    return (abs(a - int(a)) < 0.1**8)

for a in range(1, 3501):
    for b in range(a, 3501):
        tmp = 4/N - 1/a - 1/b
        if tmp <= 0: continue
        if is_int(1/tmp):
            c = int(1/tmp)
            print(a, b, c)
            sys.exit()

is_int() は整数判定のために書いたコード。
浮動小数==で比較するのって誤差ありそうでマズかった気がした。
許容誤差10-8 ってのも適切なのか全然分からないけど、もう、エイッと8(エイト)を書いた。

それで、サンプルケース動かしてみたら、
やっぱり、明らかに3つ目のケースで3秒以上かかったのでダメ。
内側のbのループを、1じゃなくaから始めて、ループを半分にする工夫をしてもダメ。

これ以上考えてもしょうがないと思い、上のコードはsubmitせず、Javaで書き直し。
メインPythonなので、TLE対策で最近この手口を使っている。
(最初からそっちで書けよ、と言われそうだけど、いろいろメンドくさいのよ。。。)

というわけで無事にAC。やったね!

Submission #1638385 - Tenka1 Programmer Contest | AtCoder

D: IntegerotS

D: IntegerotS - Tenka1 Programmer Contest | AtCoder

整数A と その価値B の組み合わせが N個与えられて、
そこからいくつか選んで、価値の総和を最大化する問題。
ただし、選んだ整数を全てbitwise OR したときに、Kを超えちゃいけない。


下のコードでACできた!

N,K = map(int,input().split())
masks = [K]

bs = str(bin(K))[2:]
for i in range(len(bs) - 1):
    if bs[i] == '1':
        a = len(bs) - 1 - i
        mask = K - (1 << a)
        mask |= ((1 << a) - 1)
        masks.append(mask)

anss = [0 for i in range(len(masks))]
for i in range(N):
    a,b = map(int,input().split())
    for i,m in enumerate(masks):
        if (m | a) == m:
            anss[i] += b

print(max(anss))

Kが 1010010(2) だとしたら、調べるべき、使えるビット(mask) のパターンは

  • 1010010 (K自身)
  • 0111111 (Kの1番目の1を0にして、あと全部1)
  • 1001111 (Kの2番目の1を0にして、あと全部1)
  • 1010001 (Kの3番目の1を0にして、あと全部1)

の4通りで十分。
なぜなら、例えば0111111(2) の他に、0111110(2)もK以下の数だけど、
最下位のビットを使っていいのと、いけないのでは、使っていい方が価値の総和が高いに決まってる。(価値は正の値)

ちなみに、こういうビットのパターンのこと、マスクって呼び方であってるのか、ちょっと不安。
まあ誰も気にしないか。

ビットを扱うのは慣れてないので、いつも考察に時間がかかっちゃうのが課題。
最初、上の例でいう0111111 しか見えてなかったので、
その方針で解けなかったときはちょっと絶望した。
でも、なんとか時間内に解けたのは、僥倖!

Submission #1640474 - Tenka1 Programmer Contest | AtCoder

競プロと出会うまで(前編)

ブログを始めました。

prd_xxx です。

 

人生初のブログなので分からないことだらけですが、

少しずつ覚えていきたいです。

よろしくお願いします。

 

競プロ(競技プログラミング) を4ヶ月前に始めました。

そこに至るまでの話をします。

 

プログラミング自体は、15年くらい前、

高校の時に選択授業で習ったのが最初でした。

 

高2のころ、選択授業でプログラミングをとりました。

C言語で、九九の表か何かを作って喜んでいました。

わーい! たのしーと思いました。

 

高3でも選択授業でプログラミングをとりました。

Javaで、Swingか何かで 、グラフィカルでインタラクティブな何かをやりました。

正直、ダメかも、、と思いました。

 

教材のソースコードが長すぎるうえ、

何をどうすればどうなるか、を

全然理解しないまま授業は終わりました。

 

年度の終わりに、自由な作品を作る機会があったのですが、

超できる人が凝った作りのビリヤードゲームを作ってたのが印象的でした。

私はというと、やはり九九の表に毛が生えたレベルの何かでした(笑)

この時点でセンスのなさを悟りました。

未だにあのクオリティのは作れる気がしません

 

そうは言っても、大学では特にやりたいこともなく、

消去法のような決め方でCS学科(情報科学)に進みました。  

そこでは当然、苦難の連続で、挫折 and 挫折の繰り返しでした。

 

まず当時はオブジェクト指向が理解できませんでした(笑)

カプセル化?継承? なにそれおいしいの的な。

 

結果として、必修科目のプログラミングをN年連続で落とし、卒業にN+3年かかりました。

もう、CS学科の最底辺だったかもしれません。

他の科目も壊滅的にダメでした。

でも変なプライドだけは一人前で、大学では孤高のぼっちを極めてました。

 

それでも、中退か?卒業を目指すか?を真剣に考えたときは、

やっぱり大卒の資格を諦めきれませんでした。

その頃から、本気を出して、頑張りだしたようにおもいます。

ただし、そこからは単位を稼ぐことを最優先にしたため、

ほとんどが付け焼刃の、試験翌日には忘れてるタイプの勉強になってしまいました。

 

というわけで私の最終学歴は学部卒ですが、

1つ後悔してることがあります。

それは、学ぶのに最適な環境、最適な立場であったにもかかわらず、

学業に対して真摯に取り組めなかったことです。

 

......今ではその後悔を払拭するかのように、競プロにのめり込んでいます!

という話をしたいのですが、 

思ったより長くなってしまったので後編に続きます。