米田氏が企画した「競プロ典型90問」を解いていきます。

ここでは私の試行錯誤やら解説の理解やら気づきやらをメモしていこうと思います。 競プロ初心者なのでどうか温かい目で見守ってください。

なお、本記事中のPythonコードはブラウザ上で実行可能です。 よろしければ遊んでいってください。

問題

kyopro_educational_90/004.jpg at main · E869120/kyopro_educational_90


004 - Cross Sum（★2）

やってみよう！

テストデータ・テスト関数定義　↓

# 縮小表示 test_data = [ { "in":[3, 3, [[1, 1, 1], [1, 1, 1], [1, 1, 1]]], "out": '''5 5 5 5 5 5 5 5 5 ''' },{ "in":[4, 4, [[3, 1, 4, 1], [5, 9, 2, 6], [5, 3, 5, 8], [9, 7, 9, 3]]], "out": '''28 28 25 26 39 33 40 34 38 38 36 31 41 41 39 43 ''' },{ "in":[2, 10, [[31, 41, 59, 26, 53, 58, 97, 93, 23, 84], [62, 64, 33, 83, 27, 95, 2, 88, 41, 97]]], "out": '''627 629 598 648 592 660 567 653 606 662 623 633 651 618 645 650 689 685 615 676 ''' },{ "in":[10, 10, [[83, 86, 77, 65, 93, 85, 86, 92, 99, 71], [62, 77, 90, 59, 63, 76, 90, 76, 72, 86], [61, 68, 67, 79, 82, 80, 62, 73, 67, 85], [79, 52, 72, 58, 69, 67, 93, 56, 61, 92], [79, 73, 71, 69, 84, 87, 98, 74, 65, 70], [63, 76, 91, 80, 56, 73, 62, 70, 96, 81], [55, 75, 84, 77, 86, 55, 96, 79, 63, 57], [74, 95, 82, 95, 64, 67, 84, 64, 93, 50], [87, 58, 76, 78, 88, 84, 53, 51, 54, 99], [82, 60, 76, 68, 89, 62, 76, 86, 94, 89]]], "out": '''1479 1471 1546 1500 1518 1488 1551 1466 1502 1546 1414 1394 1447 1420 1462 1411 1461 1396 1443 1445 1388 1376 1443 1373 1416 1380 1462 1372 1421 1419 1345 1367 1413 1369 1404 1368 1406 1364 1402 1387 1416 1417 1485 1429 1460 1419 1472 1417 1469 1480 1410 1392 1443 1396 1466 1411 1486 1399 1416 1447 1397 1372 1429 1378 1415 1408 1431 1369 1428 1450 1419 1393 1472 1401 1478 1437 1484 1425 1439 1498 1366 1390 1438 1378 1414 1380 1475 1398 1438 1409 1425 1442 1492 1442 1467 1456 1506 1417 1452 1473 ''' }, ] def test_all(f): for i, data in enumerate(test_data): exp = data["out"] ans = f(*data["in"]) result = "AC" if exp == ans else "WA" print(f"{i+1} {result}")

下のmain0関数を完成させて「Run」ボタンをクリックしよう！

def main0(H, W, A): pass test_all(main0)

自由欄

try(1st.)

このような単純に計算する問題はnumpyでサクッと解きたいところです。
AtCoderのPythonでは以下ライブラリが使用可能です。(ref. Language Test 202001 - AtCoder)

  • numba
  • numpy
  • scipy
  • scikit-learn
  • networkx
import numpy as np def main(H, W, A): data = np.array(A) rows = data.sum(axis=1) cols = data.sum(axis=0) ans = np.add(*np.meshgrid(rows, cols, indexing="ij")) - data ret = "" for l in ans: ret += f'{" ".join(l.astype(str))}\n' return ret test_all(main)

結果(1st.)

一発AC！

提出 #32460167 - 競プロ典型 90 問

他の人のコードを見てみる

せっかくなのでPythonで実装された他のコードを短いものから見てみましょう。
※類似するコードは提出の古いものだけ紹介します

"Python, 短い順" | すべての提出 - 競プロ典型 90 問

kotatsugameさん

提出 #21938944 - 競プロ典型 90 問

_,*e=[[*map(int,s.split())]for s in open(0)]
*w,=map(sum,zip(*e))
for a in e:h=sum(a);print(*[h+w-a for a,w in zip(a,w)])

open(0)について

初見です。
pythonに慣れてくるほど思考停止してwith open()と書いてしまいがちですが、結局with構文は前処理と後処理を自動化してくれるだけなので、仕組みを理解していれば必ずしも必要ありません。

そしてopen関数の場合の後処理は、f.close()です。(ref. 7. 入力と出力 — Python 3.9.12 ドキュメント

もし with キーワードを使用しない場合は、ファイルを閉じ、このファイルのために利用されたシステムのリソースを直ちに解放するために f.close() を呼び出してください。

警告 　f.write() を with キーワードや f.close() を使わずに呼び出した場合、プログラムが正常に終了した場合でも、 f.write() の実引数がディスクに完全に 書き込まれないことがあります 。

しかも上の引用の通り、問題が生じる可能性が高いのは書き込みの場合です。
もちろん実プロダクトであれば"安全な"コーディングをするに越したことはありませんが、競プロで使い捨てるレベルであればあまり神経質にならずともよさそうです。

本題の引数について、open関数はpath-like objectだけでなくファイルディスクリプタの整数も取ることができます。
そしてSTDINのファイルディスクリプタは0です。(Man page of STDIN)
従ってopen(0)で、標準入力からEOFまで読み込んでファイルオブジェクトとして返してくれるという訳です。

1行目：入力データの読み込み

読み込んだ標準入力の最初の行を読み捨て、2行目以降をeに代入しています。

# データの準備 # _,*e=[[*map(int,s.split())]for s in open(0)] に相当 e = test_data[1]["in"][2] e

2行目：列ごとの合計を計算

まずzip(*e)で2次元の配列を転置することができます。(すごい！)

list(zip(*e))

列の配列にしたところで、列ごとに合計を計算します。
ここでmap関数が返すのはイテレーターですが、アンパックして代入することでコーディング量を減らしています。(すごい！)

# mapが返すのはイテレーター w = map(sum,zip(*e)) print(w) # イテレーターからリストにする print(list(w)) # アンパックでリスト化 *w, = map(sum,zip(*e)) w # カンマが無いとエラー *w = map(sum,zip(*e)) w

3行目：行の合計を計算しつつ、「行の合計」+「列の合計」を出力

for a in e:h=sum(a);print(*[h+w-a for a,w in zip(a,w)])

同じ変数名を使いまわしているのでこんがらがりそうですが、以下のことをやっています。
printに複数引数を渡すとスペース区切りで出力されることをうまく利用しています。(天才か！)

col_sums = w for row in e: row_sum = sum(row) print(*[row_sum + col_sum - r for r, col_sum in zip(row, col_sums)])

Rssll_Krkgrdさん

提出 #22302875 - 競プロ典型 90 問

h,w,*A=map(int,open(0).read().split())
C=[sum(A[i::w])for i in range(w)]
for i in range(h*w):
 if i%w<1:r=sum(A[i:i+w])
 print(r+C[i%w]-A[i])

1行目

こちらでは入力を1次元の配列として受け取っています。

# データの準備 from itertools import chain # h,w,*A=map(int,open(0).read().split()) に相当 h,w,A = test_data[1]["in"] *A, = chain.from_iterable(A) h, w, A

2, 4行目

スライスを巧みに駆使して行と列の合計を計算しています。
(出力が指定と異なるのになぜかAC…)

C=[sum(A[i::w])for i in range(w)] for i in range(h*w): if i%w<1:r=sum(A[i:i+w]) print(r+C[i%w]-A[i])

c_r_5さん

提出 #24216523 - 競プロ典型 90 問

from numpy import*
print(*(sum(a:=int_([int_(t.split())for t in[*open(0)][1:]]),0)+vstack(sum(a,1))-a).flatten().tolist())

まさかのワンライナー！
やってることは以下と同等です。

A = test_data[1]["in"][2] A rows = np.sum(A, 1).reshape(-1, 1) cols = np.sum(A, 0) from pprint import * pp(rows) pp(cols) pp(rows + cols - A)

行ベクトルと列ベクトルを普通に足したら行列を作れるんですね。
わざわざmeshgrid使わなくてよかったんや…

まとめ

別にnumpy使わずともサクッと書ける人は書ける😓

自由欄