AtCoder Beginner Contest 139 参戦記
ABC139A - Tenki
2分半で突破. 書くだけ.
s = input()
t = input()
print(sum(1 for i in range(3) if s[i] == t[i]))
ABC139B - Power Socket
9分半で突破. 時間かかりすぎな上に、WA1.
最初は2行で書いてたんだけど、入出力例3でコケて、日和って while 文が登場しました.
そして1個も買わないことは想定してなかったので WA を食らう.
a, b = map(int, input().split())
n = 0
t = 1
while t < b:
t += a - 1
n += 1
print(n)
終わった後に書いた while 無し版
a, b = map(int, input().split())
print(((b - 1) + (a - 2)) // (a - 1))
ABC139C - Lower
4分半で突破. 書くだけ. 最近、C問題が簡単な気がする.
n = int(input())
h = list(map(int, input().split()))
t = 0
result = 0
for i in range(n - 1):
if h[i + 1] <= h[i]:
t += 1
else:
result = max(t, result)
t = 0
result = max(t, result)
print(result)
ABC139D - ModSum
5分で突破. n = 3 と n = 4 を手でやって、あまりの簡単さに困惑した. 前回のDも簡単だったけど、今回のは輪をかけて簡単でおかしい.
n = int(input())
print((n + 1) * n // 2 - n)
これ、どう考えても
n = int(input())
print(n * (n - 1) // 2)
でいいのにそうなっていないのは、1～n の合計を (n + 1) * n // 2 として覚えていて、1～n-1 の合計の式に自信がなかった日和である. (今回日和が多いですね)
ABC139E - League
TLE 1個を消せずに敗退.
コンテスト後に通した Python 版のコード. 概ね解説動画のコード通りだけど以下の違いがある.
- ノードの接続向きは逆にしてない (というか、何のために逆にしてるんですかね)
- visited, calculated は dp テーブルの値で表現しているので存在しない. (-1 が visited=false で、0 が calculated=true)
- 全ノード回しはせず、各選手の初戦ノードだけを dfs の開始ポイントとしている)
後は細かく最適化が入っている(id 生成するところの if 文 + continue が無くなっていたり). 中々 TLE が無くならなくて難儀したけど、一番効いたのが max を if 文にすることだったのでげっそり.
from sys import exit, setrecursionlimit
def get_node_id(i, j, node_id_db):
if i < j:
return node_id_db[i][j]
else:
return node_id_db[j][i]
def dfs(node_id, edges, dp):
t = dp[node_id]
if t >= 0:
return t
dp[node_id] = 0
result = 0
for n in edges[node_id]:
t = dfs(n, edges, dp)
if t == 0: # looped
print(-1)
exit()
if t > result:
result = t
result += 1
dp[node_id] = result
return result
def main():
N = int(input())
A = [[int(e) - 1 for e in input().split()] for _ in range(N)]
node_id_db = [[0] * N for _ in range(N)]
v = 0
for i in range(N):
for j in range(i + 1, N):
node_id_db[i][j] = v
v += 1
start_nodes = []
edges = [[] for _ in range(N * (N - 1) // 2)]
for i in range(N):
Ai = A[i]
from_id = get_node_id(i, Ai[0], node_id_db)
if i < Ai[0]:
start_nodes.append(from_id)
for j in range(1, N - 1):
to_id = get_node_id(i, Ai[j], node_id_db)
edges[from_id].append(to_id)
from_id = to_id
dp = [-1] * (N * (N - 1) // 2)
print(max(dfs(n, edges, dp) for n in start_nodes))
setrecursionlimit(1000000)
main()
もう一つの解法版. こちらは前日に試合のあった人(とその対戦相手)だけ試合がありうるという知識でループの無駄を減らしている. Youtube でも説明されているけど、それを見た人の TL の書き込みで考え方を知って書いたので、すぬけさんのソースコードには影響されていない. コンテスト中に書いたナイーブなコードを元にしているので実装もすぐ終わった. この方式の Python 版も書いてみたけど、TLE が消えなかったので Go 言語版で掲載.
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
func main() {
N := readInt()
a := make([][]int, N)
for i := 0; i < N; i++ {
a[i] = make([]int, N-1)
for j := 0; j < N-1; j++ {
a[i][j] = readInt() - 1
}
}
nextIndex := make([]int, N)
nextQueue := make([]int, 0, N)
for i := 0; i < N; i++ {
nextQueue = append(nextQueue, i)
}
result := 0
finished := 0
for len(nextQueue) > 0 {
result++
queue := nextQueue
nextQueue = nil
booked := make([]bool, N)
for i := 0; i < len(queue); i++ {
player := queue[i]
if booked[player] {
continue
}
opponent := a[player][nextIndex[player]]
if booked[opponent] {
continue
}
if a[opponent][nextIndex[opponent]] != player {
continue
}
booked[player] = true
booked[opponent] = true
nextIndex[player]++
nextIndex[opponent]++
if nextIndex[player] == N-1 {
finished++
} else {
nextQueue = append(nextQueue, player)
}
if nextIndex[opponent] == N-1 {
finished++
} else {
nextQueue = append(nextQueue, opponent)
}
}
}
if finished == N {
fmt.Println(result)
} else {
fmt.Println(-1)
}
}
const (
ioBufferSize = 1 * 1024 * 1024 // 1 MB
)
var stdinScanner = func() *bufio.Scanner {
result := bufio.NewScanner(os.Stdin)
result.Buffer(make([]byte, ioBufferSize), ioBufferSize)
result.Split(bufio.ScanWords)
return result
}()
func readString() string {
stdinScanner.Scan()
return stdinScanner.Text()
}
func readInt() int {
result, err := strconv.Atoi(readString())
if err != nil {
panic(err)
}
return result
}
ABC139F - Engines
ナイーブに書いたら TLE 食らいまくって、計算量減らしたら後半半分くらい WA になって敗退.